pdf icon
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
Download article from ToC site:
[PDF (239K)] [PS (892K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
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.