Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}|$?

share|cite|improve this question
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. – Yury Feb 24 '13 at 19:29
That's great. Thanks. I should have looked at the result more carefully. – Nima Feb 25 '13 at 7:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.