Vertex cover might be hard to approximate to within 2 - ε

Research output: Contribution to journalArticle

Abstract

Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th ACM Symp. on Theory of Computing, STOC, May 2002, pp. 767-775], we show that vertex cover is hard to approximate within any constant factor better than 2. We actually show a stronger result, namely, based on the same conjecture, vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.

Original languageEnglish (US)
Pages (from-to)335-349
Number of pages15
JournalJournal of Computer and System Sciences
Volume74
Issue number3
DOIs
StatePublished - May 2008

Keywords

  • Hardness of approximation
  • Unique games conjecture
  • Vertex cover

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Vertex cover might be hard to approximate to within 2 - ε'. Together they form a unique fingerprint.

  • Cite this