On the hardness of approximating vertex cover


We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of $1.3606$, extending on previous PCP and hardness of approximation technique. To that end, one needs to develop a new proof framework, and to borrow and extend ideas from several fields.


Irit Dinur

The Selim and Rachel Benin School of Computer Science and Engineering, The Hebrew University of Jerusalem, 91904 Jerusalem, Israel

Samuel Safra

School of Computer Sciences, Tel Aviv University, 69978 Tel Aviv, Israel