Volume 7 (2011) Article 3 pp. 27-43
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
by
Published: March 15, 2011
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.