On the hardness of approximating vertex cover

Abstract

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.

Authors

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