# Hardness of approximating |V|+(size of vertex cover)

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

-
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