Vertex Cover: NP-hardness of approximation within a factor above √2, without the Unique Games Conjecture
Difficulty 67: going beyond √2 unconditionally needs PCP technology between the 2-to-2 theorem and UGC (70), which took a decade and several groups to reach √2; slightly below UGC because a constant above √2, not 2 − ε, suffices, and above planted clique (64). Application value 6.2: it would certify (or overturn) the optimality of the 2-approximation, with little practical change, just above deterministic primes (6). Leverage 36: hardness thresholds for many covering problems run through the same label-cover machinery, but the conditional literature sits on UGC (79), not on this problem.
The problem
Pin down how well a simple covering problem can be approximated: proven hard below 1.41, doable only up to 2.
- 1Cover every street with few cameras
- 2Simple method gets within factor 2
- 3Proven: below 1.41 is NP-hard
- 4Unique Games would make 2 the truth
- 5Open: unconditional hardness above 1.41
Background. Minimum Vertex Cover (smallest set of vertices touching every edge) has a simple polynomial-time 2-approximation, and the best known ratio is (Karakostas). So essentially is the best algorithm known.
Built from
earlier problems → this oneThe problems this one is built from: progress or tools it needs (builds on), special cases that come first (generalizes), and weaker results on the way (implies). On the right, what builds on it.
- Start with
- Vertex Cover: NP-hardness of approximation within a factor above √2, without the Unique Games ConjectureThis problem
- Then
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- The PCP theorem and hardness of approximationTheory · host
- Then
- Vertex Cover: NP-hardness of approximation within a factor above √2, without the Unique Games ConjectureThe problem
State of the art
Dinur and Safra (Annals 2005) proved 1.3606-hardness. Khot, Minzer and Safra (STOC 2017; Theory of Computing 21, 2025) gave a reduction producing graphs with an independent set of size (1 − 1/√2)n − o(n) in the YES case and none of size Ω(n) in the NO case, which yields √2 − o(1) hardness for Vertex Cover, conditional on a Grassmann-graph expansion hypothesis. The hypothesis was proved through Dinur–Khot–Kindler–Minzer–Safra (STOC 2018), Barak–Kothari–Steurer (ITCS 2019) and Khot–Minzer–Safra (ECCC TR18-006; Annals of Mathematics 198, 2023), completing the 2-to-2 Games theorem with imperfect completeness and making the √2 − ε hardness unconditional. Under UGC the hardness is 2 − ε (Khot–Regev, JCSS 2008), matching the trivial algorithm; the best algorithm achieves 2 − Θ(1/√log n) (Karakostas). No refereed result in 2024–2026 improves the unconditional factor beyond √2; a few unrefereed preprints claim better algorithms and have not been accepted.
Realistic applications
Vertex Cover approximation underlies network monitoring, bioinformatics and scheduling formulations; resolving the threshold would settle whether LP/SDP-based 2-approximations are optimal, informing which approximation algorithms are worth engineering.
What counts as solved
A proof, accepted by experts, that for some constant c > √2 it is NP-hard to approximate Vertex Cover within factor c; or a polynomial-time algorithm with approximation ratio 2 − ε for a fixed constant ε > 0 (which would refute UGC unless P = NP).
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
The result is a proof that approximating Vertex Cover within some constant c > sqrt(2) is NP-hard (without UGC), or a (2 - eps)-approximation, which would refute UGC unless P = NP. PCP-based hardness proofs are not formalised in Mathlib, so experts review the argument.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Needs new PCP and hardness-of-approximation reductions or a new algorithm; computation plays no role beyond small experiments.
Bottlenecks
ranked by votes- #1TheoryGrassmann-based reductions give √2 and no more
The 2-to-2 reduction has imperfect completeness, and its YES-case independent set of size (1 − 1/√2)n is exactly what gives the √2 factor; going further needs PCP constructions with stronger completeness (towards Unique Games) or a different gadget.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Jan 1, 2023Annals of Mathematics publicationsource
Full proof published in Annals of Mathematics 198(1) (year given as first of year).
- Jan 10, 20182-to-2 Games theorem (imperfect completeness) provedsource
The Grassmann-graph expansion result completes the proof, yielding unconditional NP-hardness of sqrt(2) for Vertex Cover.
- Jan 1, 2016Candidate reduction to sqrt(2) hardness proposedsource
Khot, Minzer and Safra propose a 3-Lin to 2-to-2 Games reduction conditional on a Grassmann hypothesis (preliminary version STOC 2017; year given as first of year).