A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

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.