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

Research output: Contribution to journalConference article

Abstract

The general problem of vertex cover on k-uniform hypergraphs is considered. The Ek-Vertex-Cover problem is the problem of finding a minimum size vertex cover in a k-uniform hypergraph. The hypergraph contains no independent set of size δ. It is concluded that vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.

Original languageEnglish (US)
Pages (from-to)379-386
Number of pages8
JournalProceedings of the Annual IEEE Conference on Computational Complexity
StatePublished - 2003
Event18th Annual IEEE Conference on Computational Complexity - Aarhus, Denmark
Duration: Jul 7 2003Jul 10 2003

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational 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