Volume 7 (2011)
Article 3 pp. 27-43
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
Received: September 30, 2009
Published: March 15, 2011
Published: March 15, 2011
Keywords: vertex cover, independent set, bounded degree, hardness, approximation, Unique Games Conjecture
Categories: approximation algorithms, inapproximability, PCP, probabilistically checkable proofs, Unique Games, UG-hardness, graphs
ACM Classification: F.2
AMS Classification: 68Q17
Abstract: [Plain Text Version]
We study the inapproximability of Vertex Cover and Independent Set on degree-$d$ graphs. We prove that:
- Vertex Cover is Unique Games-hard to approximate within a factor $2 - (2+o_d(1)) \frac{ \log\log d}{ \log d}$. This exactly matches the algorithmic result of Halperin (SICOMP 2002) up to the $o_d(1)$ term.
- Independent Set is Unique Games-hard to approximate within a factor $O (d/\log^2 d)$. This improves the $d/\log^{O(1)}(d)$ Unique Games hardness result of Samorodnitsky and Trevisan (STOC'06). Additionally, our proof does not rely on the construction of a query-efficient PCP.