Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs

DOI10.1007/978-3-642-22670-0_11zbMath1343.68094OpenAlexW1572712645MaRDI QIDQ3088179

Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_11

zbMATH Keywords

combinatorial optimization problemsvertex coverPCPregular hypergraphscomplexity of approximation

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cites Work

• Modern cryptography, probabilistic proofs and pseudo-randomness
• The hardness of approximation: Gap location
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Proof verification and the hardness of approximation problems
• The importance of being biased
• Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Non-approximability results for optimization problems on bounded degree instances
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover