A new multilayered PCP and the hardness of hypergraph vertex cover

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev

Research output: Contribution to journalArticlepeer-review

Abstract

Given a k-uniform hypergraph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyperedge. We present a new multilayered probabilistically checkable proof (PCP) construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within a factor of (k - 1 - ε) for arbitrary constants ε > 0 and k ≥ 3. The result is nearly tight as this problem can be easily approximated within factor k. Our construction makes use of the biased long-code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets. We also give a different proof that shows an inapproximability factor of [k/2] - ε. In addition to being simpler, this proof also works for superconstant values of k up to (log N) 1/c, where c > 1 is a fixed constant and N is the number of hyperedges.

Original languageEnglish (US)
Pages (from-to)1129-1146
Number of pages18
JournalSIAM Journal on Computing
Volume34
Issue number5
DOIs
StatePublished - 2005

Keywords

  • Hardness of approximation
  • Hypergraph vertex cover
  • Long-code
  • Multilayered outer verifier
  • Probabilistically checkable proof

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A new multilayered PCP and the hardness of hypergraph vertex cover'. Together they form a unique fingerprint.

Cite this