Vertex cover might be hard to approximate to within2−ε

2007/06/14 by Subhash Khot, Oded Regev · 12 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Conjecture #Constant (computer programming) #Cover (algebra) #Discrete mathematics #Gas meter prover #Geometry #Mathematics #Programming language #Vertex (graph theory) #Vertex cover

paper · pdf · doi:10.1016/j.jcss.2007.06.019

openalex publication_date 2007/06/14 · crossref created 2007/06/14 · crossref issued 2008/05/01 · crossref published 2008/05/01 · crossref published-print 2008/05/01 · crossref deposited 2025/01/17 · openalex created_date 2025/10/10 · crossref indexed 2026/07/11 · openalex updated_date 2026/07/31

Citations

• Probabilistic checking of proofs
• Clique is hard to approximate within n1−ε
• Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
• Approximating clique is almost NP-complete
• Proof verification and the hardness of approximation problems
• Clique is hard to approximate within n/sup 1-ε/
• The importance of being biased
• On the power of unique 2-prover 1-round games
• On the hardness of approximating vertex cover

Cited by

• On the hardness of approximating vertex cover
• Kernelization: Theory of Parameterized Preprocessing
• A better approximation ratio for the vertex cover problem
• Every Permutation CSP of arity 3 is Approximation Resistant
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph
• Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion
• Subexponential Algorithms for Unique Games and Related Problems
• Optimal algorithms and inapproximability results for every CSP?
• Graph expansion and the unique games conjecture
• On the Unique Games Conjecture (Invited Survey)
• Parameterized complexity and approximation issues for the colorful components problems
• Vertex cover [wikipedia]