0
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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/

$\endgroup$
  • 3
    $\begingroup$ They say so because that particular algorithm is tight: By using that particular algorithm, you cannot hope to achieve better than 2 approximate solution in the worst case. In other words, they give at the same time upper bounds on its performance (cannot be higher than 2) and lower bounds (there are example which cannot be lower than 2) on the performance of the algorithm, and these two bounds are the same. Thus, this particular algorithm is tight. $\endgroup$ – PsySp Mar 6 '17 at 17:07
  • 1
    $\begingroup$ Thank you I understand now. So, the algorithm is tight, but the approximation ratio is not tight. $\endgroup$ – YOUSEFY Mar 6 '17 at 17:13
  • 2
    $\begingroup$ The approximation ratio is not know to be tight. $\endgroup$ – PsySp Mar 6 '17 at 17:17
  • 2
    $\begingroup$ It is an open problem to (1) either find an algorithm that achieves approximation ratio better (i.e., less) than 2 or (2) improve the lower bound of 1.3606. Both directions are considered extremely difficult. $\endgroup$ – PsySp Mar 6 '17 at 18:06
  • 5
    $\begingroup$ To be a bit more precise, they show that their analysis of this particular algorithm is tight. $\endgroup$ – Sasho Nikolov Mar 6 '17 at 18:41
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.