Articles · Algorithms
Can Vertex Cover Be Approximated Better Than 2×?
A one-line algorithm has stood unbeaten for decades — and beating it would resolve one of complexity theory's biggest open conjectures.
A vertex cover of a graph is a set of vertices that touches every edge. Finding the smallest one is NP-hard, but a startlingly simple algorithm gets within a factor of two of optimal: take any maximal matching — a set of edges that share no endpoints and can’t be extended — and include both endpoints of every matched edge. Since the optimal cover must include at least one endpoint from each matching edge (they share no vertices, so no single vertex can cover two of them), and this construction uses both endpoints of each, the result is at most twice the true optimum. The vertex-cover approximation record tracks whether that factor of two can ever be beaten.
A bound nobody has improved on
The 2-approximation for vertex cover has been known since the early days of approximation algorithms, and despite it being one of the most studied problems in the field, no polynomial-time algorithm with a better worst-case guarantee — 1.99, say, or anything below 2 — has ever been found for general graphs.
Tied to a bigger open conjecture
In 2008, Subhash Khot and Oded Regev showed that if the Unique Games Conjecture (UGC) is true, then no polynomial-time algorithm can approximate vertex cover to better than a factor of 2 − ε for any ε > 0 — meaning 2 would be provably optimal. UGC is itself a major unresolved conjecture in complexity theory, believed by many researchers but unproven either way. So the fate of the vertex-cover approximation frontier is now tied directly to the fate of a separate, actively studied open problem.
Why this matters beyond one problem
The Unique Games Conjecture has this same relationship to the best-known approximation ratio for a whole family of problems, not just vertex cover — it’s become a kind of master key for proving inapproximability results. Resolving UGC either way would immediately settle several open approximation frontiers at once, vertex cover among them.
Why it’s here
Vertex cover is a case where the achievable side of the frontier (2, via a one-line algorithm) hasn’t moved in decades, and the impossibility side is conditional on a conjecture that itself has no proof either way — a genuinely open two-sided gap, just built out of a chain of open problems rather than a single one.
Primary source
Reach people exploring this research with a visible sponsor panel for your organisation.
Sponsor this research Paid placement for an agreed term. Subject to independent review.