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.”

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