Is the current best approximation ratio for Vertex Cover problem also a lower bound?

Question

In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we cannot improve better than 2. However, there is an old paper by Johan Hastad here he shows that by using PCP technique we cannot do better than 7/6=1.16 which is an NP-complete. So, we have a gap between 2 and 7/6 which tells us that whether we have a better approximation algorithm is still open problem. Is that right?! or suppose that Hastad is wrong, then there must be a new analysis about the hardness of vector cover in terms of approximation algorithm.

*As I understand who argues that we cannot do better than the approximation ratio which is 2, the reason is that to give tight example (nontrivial example) which is a complete bipartite graph (K_{n,n}) and since the algorithm choose n number of edges, therefore we have 2n number of vertices, and the vertex cover is only n in this case. Their claim is that if you find 2(n-1) edges, then you have n-1 vertices, and there is a contradiction since we are not covering all vertices which is n. (this is how I understand it so it could be wrong) (Of course there is no polynomial algorithm to find n vertices, and the best approximation algorithm is to find 2n in polynomial time, and they say that it is tight bound) I also read this lecture notes

Also, Is there any new results about the hardness of vertex cover in terms of approximation.

Answer 1

Cormen, Leiserson, Rivest and Stein say that this algorithm that achieves ratio of 2 is tight. They did not exclude the possibility of another algorithm achieving better.

Vertex Cover is NP-hard to approximate with a factor better than 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf

Also check the following paper which give a 2-epsilon inapproximability result based on unique games hardness: http://www.sciencedirect.com/science/article/pii/S0022000007000864

For approximation algorithms, see the wiki article for Vertex Cover and in particular the paper of Karakostas 2009: https://eccc.weizmann.ac.il/report/2004/084/

Answer 2

In 2016–2018, in a series of papers, Dinur, Khot, Kindler, Minzer and Safra show that Vertex Cover is NP-hard to approximate to any factor better than $\sqrt{2}$, thus improving Dinur and Safra's earlier 1.36 hardness. See Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion, the last paper in the series.