Article

A new multilayered PCP and the hardness of hypergraph vertex cover

Authors:

Venkatesan Guruswami,

Oded RegevAuthors Info & Claims

STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

Pages 595 - 601

https://doi.org/10.1145/780542.780629

Published: 09 June 2003 Publication History

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.

References

[1]

S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3) : 501--555, 1998.

Digital Library

[2]

S. Arora and S. Safra. Probabilistic checking of proofs : A new characterization of NP. Journal of the ACM, 45(1) : 70--122, 1998.

Digital Library

[3]

M. Bellare, O. Goldreich and M. Sudan. Free bits, PCPs and non-approximability. SIAM Journal on Computing, 27(3):804--915, June 1998.

Digital Library

[4]

H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics, 23:493--507, 1952.

[5]

I. Dinur, V. Guruswami and S. Khot. Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k-3-ε). Electronic Colloquium on Computational Complexity, Technical Report TR02-027, 2002.

[6]

I. Dinur, O. Regev and C. Smyth. The hardness of 3-uniform hypergraph coloring. In Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 33--42.

Digital Library

[7]

I. Dinur and S. Safra. The importance of being biased. Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 33--42, May 2002.

Digital Library

[8]

U. Feige. A threshold of ln n for approximating set cover. JACM: Journal of the ACM, 45, 1998.

Digital Library

[9]

U. Feige, S. Goldwasser, L. Lovász, S. Safra and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268--292, March 1996.

Digital Library

[10]

O. Goldreich. Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs. ECCC Technical Report TR01-102, December 2001.

[11]

V. Guruswami, J. Håstad and M. Sudan. Hardness of approximate hypergraph coloring. Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 149--158, November 2000.

Digital Library

[12]

E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 329--337, January 2000.

Digital Library

[13]

R. L. Graham, M. Grötschel, and L. Lovász, editors. Handbook of combinatorics. Vol. 1, 2. Elsevier Science B.V., Amsterdam, 1995.

Digital Library

[14]

J. Håstad. Clique is hard to approximate within n1-ε. Acta Mathematica, 182(1):105--142, 1999.

[15]

J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798--859, July 2001.

Digital Library

[16]

J. Holmerin. Vertex cover on 4-uniform hypergraphs is hard to approximate within 2 - ε. Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 544--552, May 2002.

Digital Library

[17]

J. Holmerin. Improved inapproximability results for vertex cover on k-uniform hypergraphs. Proc. of the 29th International Colloquium on Automata, Languages and Programming (ICALP), pages 1005--1016, July 2002.

Digital Library

[18]

D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256--278, 1974.

Digital Library

[19]

S. Khot. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 23--32, November 2002.

Digital Library

[20]

L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383--390, 1975.

Digital Library

[21]

R. Raz. A parallel repetition theorem. SIAM J. of Computing, vol 27(3), 763--803, 1998.

Digital Library

[22]

A. Samorodnitsky and L. Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proc. of the 32nd Annual ACM Symposium on Theory of Computing, pages 191--199, 2000.

Digital Library

[23]

L. Trevisan. Non-approximability results for optimization problems on bounded degree instances. In Proc. of the Annual ACM 33rd Symposium on Theory of Computing, pages 453--461, July 2001.

Digital Library

Cited By

Chen HConte AGrossi RLoukides GPissis SSweering M(2024)On Breaking Truss-Based and Core-Based CommunitiesACM Transactions on Knowledge Discovery from Data10.1145/3644077Online publication date: 14-Feb-2024
https://doi.org/10.1145/3644077
Lee E(2019)Partitioning a graph into small pieces with applications to path transversalMathematical Programming: Series A and B10.1007/s10107-018-1255-7177:1-2(1-19)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s10107-018-1255-7
Lee EKlein P(2017)Partitioning a graph into small pieces with applications to path transversalProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039787(1546-1558)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039787
Show More Cited By

Index Terms

A new multilayered PCP and the hardness of hypergraph vertex cover
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

Given a k-uniform hypergraph, the E k-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 ...
Strong hardness of approximation for tree transversals
Abstract
Let H be a fixed graph. The H-Transversal problem, given a graph G, asks to remove the smallest number of vertices from G so that G does not contain H as a subgraph. While a simple | V ( H ) |-approximation algorithm exists and is believed to be ...
Highlights
- T-Transversal asks to remove a small number of vertices from G to make it T-free.
- T-Transversal for some tree T is NP-hard to approximate within a factor | V ( T ) | / 2 − 1.
- The previous best hardness for any tree T was O ( l o ...
On the hardness of approximating label-cover

The LABEL-COVER problem, defined by S. Arora, L. Babai, J. Stem, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724-733], serves as a starting point for numerous hardness of approximation reductions. It is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

June 2003

740 pages

ISBN:1581136749

DOI:10.1145/780542

Conference Chair:
Lawrence L. Larmore
University of Nevada Las Vegas, Las Vegas, NV
,
Program Chair:
Michel X. Goemans
Massachusetts Institute of Technology, Cambridge, MA

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC03

Sponsor:

STOC03: The 35th Annual ACM Symposium on Theory of Computing

June 9 - 11, 2003

CA, San Diego, USA

Acceptance Rates

STOC '03 Paper Acceptance Rate 80 of 270 submissions, 30%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
563
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen HConte AGrossi RLoukides GPissis SSweering M(2024)On Breaking Truss-Based and Core-Based CommunitiesACM Transactions on Knowledge Discovery from Data10.1145/3644077Online publication date: 14-Feb-2024
https://doi.org/10.1145/3644077
Lee E(2019)Partitioning a graph into small pieces with applications to path transversalMathematical Programming: Series A and B10.1007/s10107-018-1255-7177:1-2(1-19)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s10107-018-1255-7
Lee EKlein P(2017)Partitioning a graph into small pieces with applications to path transversalProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039787(1546-1558)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039787
Khot SSaket RChekuri C(2014)Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphsProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634191(1607-1625)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634191
Sachdeva SSaket R(2013)Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover2013 IEEE Conference on Computational Complexity10.1109/CCC.2013.30(219-229)Online publication date: Jun-2013
https://doi.org/10.1109/CCC.2013.30
Mastrolilli MMutsanas NSvensson O(2013)Single machine scheduling with scenariosTheoretical Computer Science10.1016/j.tcs.2012.12.006477(57-66)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.tcs.2012.12.006
Trevisan L(2013)Inapproximability of Combinatorial Optimization ProblemsParadigms of Combinatorial Optimization10.1002/9781118600207.ch13(381-434)Online publication date: 13-Feb-2013
https://doi.org/10.1002/9781118600207.ch13
Kumar AManokaran RTulsiani MVishnoi NRandall D(2011)On LP-based approximability for strict CSPsProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133157(1560-1573)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133157
Hosoda JHromkovič JIzumi TOno HSteinová MWada K(2011)On the approximability of minimum topic connected overlay and its special instancesProceedings of the 36th international conference on Mathematical foundations of computer science10.5555/2034006.2034043(376-387)Online publication date: 22-Aug-2011
https://dl.acm.org/doi/10.5555/2034006.2034043
Calinescu GLi M(2011)Register loading via linear programmingProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033205(171-182)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.5555/2033190.2033205
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents