Take the 2-minute tour ×
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.

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|improve this question
1  
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

 
discard

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

Browse other questions tagged or ask your own question.