Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
Per Austrin, Subhash Khot, Muli Safra · 2009
We study the inapproximability of Vertex Cover and Independent Set on degree d graphs. We prove that: (1) Vertex Cover is Unique Games-hard to approximate to within a factor 2 - (2 + od(1)) log log d/log d. This exactly matches the algorithmic result of Halperin up to the od(1) term. (2) Independent Set is Unique Games-hard to approximate to within a factor O(d/log2d). This improves the d/logO(1)(d)) Unique Games hardness result of Samorodnitsky and Trevisan. Additionally, our result does not rely on the construction of a query efficient PCP as in.