Inapproximability of vertex cover and independent set in bounded degree graphs

Per Austrin, Subhash Khot, Muli Safra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 to within a factor 2-(2+od(1))/log log d/log d . This exactly matches the algorithmic result of Halperin [1] up to the o d(1) term. • Independent Set is Unique Games-hard to approximate to within a factor O/( d/log2 d ). This improves the d/log O(1)(d) Unique Games hardness result of Samorodnitsky and Trevisan [2]. Additionally, our result does not rely on the construction of a query efficient PCP as in [2].

Original languageEnglish (US)
Title of host publicationProceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
Pages74-80
Number of pages7
DOIs
StatePublished - 2009
Event2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 - Paris, France
Duration: Jul 15 2009Jul 18 2009

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
CountryFrance
CityParis
Period7/15/097/18/09

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Inapproximability of vertex cover and independent set in bounded degree graphs'. Together they form a unique fingerprint.

Cite this