On the hardness of approximating vertex cover

2005/07/01 by Irit Dinur, Samuel Safra · 14 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Cover (algebra) #Discrete mathematics #Engineering #Graph #Mathematics #Vertex (graph theory) #Vertex cover

paper · pdf · doi:10.4007/annals.2005.162.439

openalex publication_date 2005/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of 1.3606, extending on previous PCP and hardness of approximation technique.To that end, one needs to develop a new proof framework, and to borrow and extend ideas from several fields.

Citations

• Probabilistic checking of proofs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complexity of theorem-proving procedures
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• On the hardness of approximating minimization problems
• Clique is hard to approximate within n1−ε
• Probabilistic checking of proofs; a new characterization of NP
• Vertex cover might be hard to approximate to within2−ε
• Factoring polynomials with rational coefficients
• Approximating clique is almost NP-complete
• A threshold of ln n for approximating set cover
• Noise sensitivity of boolean functions and applications to percolation
• A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
• Optimization, approximation, and complexity classes
• On the power of unique 2-prover 1-round games
• Reducibility among Combinatorial Problems

Cited by

• Intersecting Families are Essentially Contained in Juntas
• Kernelization: Theory of Parameterized Preprocessing
• A better approximation ratio for the vertex cover problem
• Exact Localisations of Feedback Sets
• Tight Upper Bounds for Minimum Feedback Arc Sets of Regular Graphs
• Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion
• A new point of NP-hardness for unique games
• Parameterized complexity and approximation issues for the colorful components problems
• Vertex cover might be hard to approximate to within2−ε
• Improved bounds for the sunflower lemma
• Feedback arc set [wikipedia]
• Feedback vertex set [wikipedia]
• Unique games conjecture [wikipedia]
• Vertex cover [wikipedia]