# zbMATH — the first resource for mathematics

Inapproximability of vertex cover and independent set in bounded degree graphs. (English) Zbl 1243.68183
Authors’ abstract: “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))\log\log d/\log d$$. This exactly matches the algorithmic result of E. Halperin [SIAM J. Comput. 31, No. 5, 1608–1623 (2002; Zbl 1041.68130)] 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 A. Samorodnitsky and L. Trevisan [“Gowers uniformity, influence of variables, and PCPs”, in: Proceedings of the 38th symposium on the theory of computing (STOC) 2006, 11–20 (2006)]. Additionally, our proof does not rely on the construction of a query-efficient PCP.”

##### MSC:
 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68R10 Graph theory (including graph drawing) in computer science
Full Text: