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

CC BY-SA 3.0
2013-02-24T19:29:51.057Z
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
CC BY-SA 3.0
2013-02-25T07:03:09.440Z
That's great. Thanks. I should have looked at the result more carefully.
Nima
<approximation-hardness>
Hardness of approximating |V|+(size of vertex cover)
Nima
# Hardness of approximating |V|+(size of vertex cover)

(Asked by: username_0 on 2013-02-23)

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

**Tags:** approximation-hardness
> **Comments:**
> **username_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.  
> **username_0**: That's great. Thanks. I should have looked at the result more carefully.  

---

## 0 answers

