A new multilayered {PCP} and the hardness of hypergraph vertex cover

DOI10.1145/780542.780629MaRDI QIDQ3581279zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Subhash Khot, Venkatesan Guruswami, Oded Regev

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/780542.780629

Mathematics Subject Classification ID

Hypergraphs (05C65) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• scientific article; zbMATH DE number 2086690
• Nearly optimal NP-hardness of vertex cover on k-uniform k-partite hypergraphs
• Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(18)

• On the minimum hitting set of bundles problem
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Partitioning a graph into small pieces with applications to path transversal
• Approximation of the quadratic set covering problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Disjoint bases in a polymatroid
• Nearly optimal NP-hardness of vertex cover on k-uniform k-partite hypergraphs
• Is constraint satisfaction over two variables always easy?
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• On the Minimum Hitting Set of Bundles Problem
• Approximating Single Machine Scheduling with Scenarios
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• On the approximability and hardness of minimum topic connected overlay and its special instances
• scientific article; zbMATH DE number 2086690 (Why is no real title available?)
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Gap MCSP is not (Levin) NP-complete in obfustopia
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• Approximation hardness of dominating set problems in bounded degree graphs

This page was built for publication: A new multilayered {PCP} and the hardness of hypergraph vertex cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581279)