4
$\begingroup$

I know that UGC implies a hardness of 2 for vertex cover, but is there a way to have this hardness on instances where the size of the vertex cover is at least $(1-\epsilon)\frac{|V|}2$? More generally is anything known on the hardness of approximating $|V|+|\mbox{Minimum Vertex Cover}|$?

$\endgroup$
2
  • 1
    $\begingroup$ Khot and Regev proved, assuming UGC, that for every constant $\varepsilon >0$ it is NP-hard to distinguish between the cases: (1) the size of the minimum vertex cover is at most $(1+\varepsilon)|V|/2$ and (2) the size of the minimum vertex cover is at least $(1-\varepsilon)|V|$. The size of the minimum vertex in [KR] instances is at least $(1-\varepsilon)|V|/2$, as otherwise we would be able to efficiently certify that there is a vertex cover with fewer than $(1-\varepsilon)|V|$ vertices. $\endgroup$ – Yury Feb 24 '13 at 19:29
  • $\begingroup$ That's great. Thanks. I should have looked at the result more carefully. $\endgroup$ – Nima Feb 25 '13 at 7:03

Your Answer

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

Browse other questions tagged or ask your own question.