Abstract
Given a k-uniform hyper-graph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within factor (k -1 - ε) for any k ≥ 3 and any ε > 0. The result is essentially 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.
Original language | English (US) |
---|---|
Title of host publication | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
Pages | 595-601 |
Number of pages | 7 |
State | Published - 2003 |
Event | 35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003 |
Other
Other | 35th Annual ACM Symposium on Theory of Computing |
---|---|
Country/Territory | United States |
City | San Diego, CA |
Period | 6/9/03 → 6/11/03 |
Keywords
- Hardness of Approximation
- Hypergraph Vertex Cover
- Long Code
- Multilayered PCP
ASJC Scopus subject areas
- Software