# 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