<p>In 2016–2018, in a series of papers, Dinur, Khot, Kindler, Minzer and Safra show that Vertex Cover is NP-hard to approximate to any factor better than <span class="math-container">$\sqrt{2}$</span>, thus improving Dinur and Safra's earlier 1.36 hardness. See <a href="https://eccc.weizmann.ac.il/report/2018/006/" rel="nofollow noreferrer">Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion</a>, the last paper in the series.</p>

CC BY-SA 4.0
2019-03-15T20:59:58.593Z
2019-03-15T20:59:58.593Z
Yuval Filmus
<p>Cormen, Leiserson, Rivest and Stein say that <em>this</em> algorithm that achieves ratio of 2 is tight. They did not exclude the possibility of <em>another</em> algorithm achieving better.</p>

<p>Vertex Cover is NP-hard to approximate with a factor better than 1.36:
<a href="http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf" rel="noreferrer">http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf</a></p>

<p>Also check the following paper which give a 2-epsilon inapproximability result based on unique games hardness:
<a href="http://www.sciencedirect.com/science/article/pii/S0022000007000864" rel="noreferrer">http://www.sciencedirect.com/science/article/pii/S0022000007000864</a></p>

<p>For approximation algorithms, see the wiki article for Vertex Cover and in particular the paper of Karakostas 2009: <a href="https://eccc.weizmann.ac.il/report/2004/084/" rel="noreferrer">https://eccc.weizmann.ac.il/report/2004/084/</a></p>

CC BY-SA 3.0
2017-03-06T16:54:17.367Z
Thank you so much for your references. I would like to ask you; why they call ratio of 2 is tight, even though there could be an algorithm which achieves better ratio? They should say something like "to improve the ratio is an open problem" don't agree with me!
YOUSEFY
CC BY-SA 3.0
2017-03-06T17:07:58.553Z
They say so because _that particular_ algorithm is tight: By using that particular algorithm, you cannot hope to achieve better than 2 approximate solution in the worst case. In other words, they give _at the same time_ upper bounds on its performance (cannot be higher than 2) and lower bounds (there are example which cannot be lower than 2) on the performance of the algorithm, and these two bounds are _the same_. Thus, this particular algorithm is tight.
PsySp
CC BY-SA 3.0
2017-03-06T17:13:17.220Z
Thank you I understand now. So, the algorithm is tight, but the approximation ratio is not tight.
YOUSEFY
CC BY-SA 3.0
2017-03-06T17:17:31.840Z
The approximation ratio _is not know to be_ tight.
PsySp
CC BY-SA 3.0
2017-03-06T17:28:00.737Z
It is an open problem to find a new approximation algorithm with better ratio or even to find a tight bound for approximation ratio or even a new lower bound for approximation ratio but we know that the upper bound for approximation ratio is 2.
YOUSEFY
CC BY-SA 3.0
2017-03-06T18:06:56.817Z
It is an open problem to (1) either find an algorithm that achieves approximation ratio better (i.e., less) than 2 or (2) improve the lower bound of 1.3606. Both directions are considered extremely difficult.
PsySp
CC BY-SA 3.0
2017-03-06T18:41:59.993Z
To be a bit more precise, they show that their *analysis* of this particular algorithm is tight.
Sasho Nikolov
CC BY-SA 3.0
2017-03-06T15:31:29.440Z
2017-03-06T15:31:29.440Z
PsySp
<p>In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we cannot improve better than 2. However, there is an old paper by Johan Hastad <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf" rel="nofollow noreferrer">here</a> he shows that by using PCP technique we cannot do better than 7/6=1.16 which is an NP-complete. So, we have a gap between 2 and 7/6 which tells us that whether we have a better approximation algorithm is still open problem. Is that right?! or suppose that Hastad is wrong, then there must be a new analysis about the hardness of vector cover in terms of approximation algorithm. </p>

<p>*As I understand who argues that we cannot do better than the approximation ratio which is 2, the reason is that to give tight example (nontrivial example) which is a complete bipartite graph (K_{n,n}) and since the algorithm choose n number of edges, therefore we have 2n number of vertices, and the vertex cover is only n in this case. Their claim is that if you find 2(n-1) edges, then you have n-1 vertices, and there is a contradiction since we are not covering all vertices which is n. (this is how I understand it so it could be wrong) (Of course there is no polynomial algorithm to find n vertices, and the best approximation algorithm is to find 2n in polynomial time, and they say that it is tight bound) I also read this <a href="http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/wan-ba-scribe.pdf" rel="nofollow noreferrer">lecture notes</a> </p>

<p>Also, Is there any new results about the hardness of vertex cover in terms of approximation. </p>

<approximation-algorithms><approximation-hardness>
Is the current best approximation ratio for Vertex Cover problem also a lower bound?
YOUSEFY
# Is the current best approximation ratio for Vertex Cover problem also a lower bound?

(Asked by: username_0 on 2017-03-06)

In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we cannot improve better than 2. However, there is an old paper by Johan Hastad [here](http://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf) he shows that by using PCP technique we cannot do better than 7/6=1.16 which is an NP-complete. So, we have a gap between 2 and 7/6 which tells us that whether we have a better approximation algorithm is still open problem. Is that right?! or suppose that Hastad is wrong, then there must be a new analysis about the hardness of vector cover in terms of approximation algorithm.

\*As I understand who argues that we cannot do better than the approximation ratio which is 2, the reason is that to give tight example (nontrivial example) which is a complete bipartite graph (K\_{n,n}) and since the algorithm choose n number of edges, therefore we have 2n number of vertices, and the vertex cover is only n in this case. Their claim is that if you find 2(n-1) edges, then you have n-1 vertices, and there is a contradiction since we are not covering all vertices which is n. (this is how I understand it so it could be wrong) (Of course there is no polynomial algorithm to find n vertices, and the best approximation algorithm is to find 2n in polynomial time, and they say that it is tight bound) I also read this [lecture notes](http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/wan-ba-scribe.pdf)

Also, Is there any new results about the hardness of vertex cover in terms of approximation.

**Tags:** approximation-algorithms, approximation-hardness

---

## 2 answers

### Answer by username_2 on 2017-03-06. Score: 10 | Accepted answer

Cormen, Leiserson, Rivest and Stein say that *this* algorithm that achieves ratio of 2 is tight. They did not exclude the possibility of *another* algorithm achieving better.

Vertex Cover is NP-hard to approximate with a factor better than 1.36:
<http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf>

Also check the following paper which give a 2-epsilon inapproximability result based on unique games hardness:
<http://www.sciencedirect.com/science/article/pii/S0022000007000864>

For approximation algorithms, see the wiki article for Vertex Cover and in particular the paper of Karakostas 2009: <https://eccc.weizmann.ac.il/report/2004/084/>

> **Comments:**
> **username_0**: Thank you so much for your references. I would like to ask you; why they call ratio of 2 is tight, even though there could be an algorithm which achieves better ratio? They should say something like "to improve the ratio is an open problem" don't agree with me!  
> **username_2**: They say so because _that particular_ algorithm is tight: By using that particular algorithm, you cannot hope to achieve better than 2 approximate solution in the worst case. In other words, they give _at the same time_ upper bounds on its performance (cannot be higher than 2) and lower bounds (there are example which cannot be lower than 2) on the performance of the algorithm, and these two bounds are _the same_. Thus, this particular algorithm is tight.  
> **username_0**: Thank you I understand now. So, the algorithm is tight, but the approximation ratio is not tight.  
> **username_2**: The approximation ratio _is not know to be_ tight.  
> **username_0**: It is an open problem to find a new approximation algorithm with better ratio or even to find a tight bound for approximation ratio or even a new lower bound for approximation ratio but we know that the upper bound for approximation ratio is 2.  
> **username_2**: It is an open problem to (1) either find an algorithm that achieves approximation ratio better (i.e., less) than 2 or (2) improve the lower bound of 1.3606. Both directions are considered extremely difficult.  
> **username_3**: To be a bit more precise, they show that their *analysis* of this particular algorithm is tight.  

---

### Answer by username_1 on 2019-03-15. Score: 3

In 2016–2018, in a series of papers, Dinur, Khot, Kindler, Minzer and Safra show that Vertex Cover is NP-hard to approximate to any factor better than $\sqrt{2}$, thus improving Dinur and Safra's earlier 1.36 hardness. See [Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion](https://eccc.weizmann.ac.il/report/2018/006/), the last paper in the series.


---

