Minimum vertex cover is NP-hard to approximate within any factor c < 1.3606…

You need to know: Class P, class NP, NP-hard problems, graph, vertices, edges.

Background: A vertex cover of graph G is the set S of vertices of G such that for each edge $(u,v)$ of G either $u \in S$ or $v\in S$ (or both). Let $\tau(G)$ be the size of the smallest vertex cover of G. The minimum vertex cover problem is: given graph G, compute $\tau(G)$ . Its approximation with factor $c>1$ is: given graph G, compute number k such that $\tau(G) \leq k \leq c\tau(G)$ .

The Theorem: On 7th October 2002, Irit Dinur and Samuel Safra submitted to the Annals of Mathematics a paper in which they proved that the minimum vertex cover problem is NP-hard to approximate to within any constant factor smaller than $10\sqrt{5}-21 = 1.3606...$

Short context: Because the minimum vertex cover problem is well-known to be NP-hard to solve exactly, it is natural to look for approximate algorithms. A simple algorithm, discovered independently by Gavril and Yannakakis, gives approximation with factor $c=2$ , and this is the best known. In the opposite direction, Håstad proved in 2001 that the problem is NP-hard to approximate to within any factor $c<\frac{7}{6} = 1.1666...$ . The Theorem proves the same result with better factor $10\sqrt{5}-21 = 1.3606...$ in place of $\frac{7}{6}$ . See here for further progress in a later work.