Vertex Cover Might be Hard to Approximate to within 2-\varepsilon

Subhash Khot; Oded Regev

doi:10.1109/CCC.2003.1214437

18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings.

Vertex Cover Might be Hard to Approximate to within 2-\varepsilon

Year: 2003, Pages: 379

DOI Bookmark: 10.1109/CCC.2003.1214437

Authors

Subhash Khot, Princeton University
Oded Regev, Institute for Advanced Study

Abstract

Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [15], we show that vertex cover is hard to approximate within any constant factor better than 2. We actually show a stronger result, namely, based on the same conjecture, vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.

Like what you’re reading?

Already a member?

Get this article FREE with a new membership!

Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
2009 24th Annual IEEE Conference on Computational Complexity
On Vertex Cover with Fractional Fan-Out Bound
2014 Second International Symposium on Computing and Networking (CANDAR)
Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover
2013 IEEE Conference on Computational Complexity (CCC)
An Improved DNA Solution to the Vertex Cover Problem
2008 Fourth International Conference on Natural Computation
An Improved Greedy Heuristic for Unweighted Minimum Vertex Cover
2014 International Conference on Computational Intelligence and Communication Networks (CICN)
No Small Linear Program Approximates Vertex Cover within a Factor 2 -- e
2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)
Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - \epsilon
Proceedings 17th IEEE Annual Conference on Computational Complexity
Improved approximation algorithm for vertex cover problem using articulation points
2014 5th International Conference on Computing, Communication and Networking Technologies (ICCCNT)
New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy
21st Annual IEEE Conference on Computational Complexity (CCC'06)
Parallel Vertex Cover Algorithms on GPUs
2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)

Vertex Cover Might be Hard to Approximate to within 2-\varepsilon

Authors

Abstract

Related Articles