## 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 language | English (US) |
---|---|

Pages (from-to) | 1129-1146 |

Number of pages | 18 |

Journal | SIAM Journal on Computing |

Volume | 34 |

Issue number | 5 |

DOIs | |

State | Published - 2005 |

## Keywords

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

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics