Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs

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 + o_d(1)) log log d/log d. This exactly matches the algorithmic result of Halperin up to the o_d(1) term. (2) Independent Set is Unique Games-hard to approximate to within a factor O(d/log²d). This improves the d/log^O(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.