Vertex Cover, in depth: the maximal-matching 2-approximation, LP rounding and local ratio for weights, kernels for small k, and the hardness limits

The problem and its twin

Write the graph as G = (V, E) with n vertices and m edges. A set C is a cover if every edge has an endpoint in C. The complement of a cover is an independent set (no edge has both endpoints outside C), so minimum vertex cover and maximum independent set are the same problem seen from opposite sides: |min cover| + |max independent set| = n. The identity is exact but does not transfer approximation guarantees: a near-optimal cover can leave a very poor independent set.

The decision version (is there a cover of size at most k?) was on Karp's original list of 21 NP-complete problems; the reduction chain and what NP-completeness means are covered in NP-completeness. In practice the question is never whether to give up but which guarantee to buy: a provable factor of 2 in linear time, an exact answer when the cover is small, or an exact answer from an integer programming solver with a gap you can read off.

The maximal-matching 2-approximation

A matching is a set of edges with no shared endpoint. A maximal matching is one you cannot extend: every edge of the graph shares an endpoint with some matched edge. Note the word maximal, not maximum. A maximal matching is found greedily in one pass over the edges; a maximum matching needs the blossom algorithm and is not required here.

The algorithm: build any maximal matching M and return both endpoints of every matched edge.

def vertex_cover_2approx(edges):
    """edges: iterable of (u, v). Returns (cover, matching)."""
    cover, matching = set(), []
    for u, v in edges:
        if u == v:                    # a self-loop forces u into every cover
            cover.add(u)
        elif u not in cover and v not in cover:
            matching.append((u, v))   # edge not yet covered: match it
            cover.add(u)
            cover.add(v)
    return cover, matching

Two short arguments prove it. Feasibility: if some edge were uncovered, neither endpoint is in the cover, so neither is matched, and the edge could be added to M, contradicting maximality. Quality: the matched edges share no endpoints, so any cover, including the optimal one, must contain a distinct vertex for each of them. Hence OPT ≥ |M|, and the algorithm returns 2|M| ≤ 2·OPT vertices.

The second argument is worth more than the bound. |M| is a lower bound computed on your actual input, so every run reports its own quality: if the cover has 1,840 vertices and the matching has 1,200 edges, the true optimum lies between 1,200 and 1,840 and you are within 1.53 of it on this instance, not merely within 2 in theory. The factor 2 is tight: on the complete bipartite graph with n vertices per side, any perfect matching yields all 2n vertices while one side alone, n vertices, is a cover.

Worked example and the pruning pass

Take eight vertices and ten edges: ab, ac, bc, bd, ce, de, df, eg, fg, gh. Scanning edges in that order, the algorithm matches ab (both uncovered), skips ac and bc, skips bd (b is taken), matches ce, skips de, matches df, skips eg and fg, and matches gh. The matching has four edges, so the cover is all eight vertices and the certificate says OPT ≥ 4.

Brute force over all subsets confirms the optimum is exactly 4, for example {a, c, d, g} or {b, c, d, g}. This instance hits the worst case, which is why a clean-up pass follows: a cover vertex whose neighbours are all in the cover is redundant. Visiting vertices from lowest degree upwards, the pass removes h (its only neighbour g stays), then a, then f, then e, and leaves {b, c, d, g}: four vertices, equal to the lower bound, so this run has proved its own optimality. Pruning never breaks feasibility, never increases the size, and costs O(n + m).

def prune(cover, adj):
    """Remove redundant vertices; adj maps vertex -> set of neighbours."""
    for v in sorted(cover, key=lambda x: len(adj[x])):
        if all(w in cover for w in adj[v]):
            cover.discard(v)
    return cover

Why greedy by degree is not enough

The obvious alternative, repeatedly taking the vertex that covers the most uncovered edges, is the greedy algorithm for set cover applied to this problem. On the example graph, breaking ties alphabetically, it picks b, then e, f, a and g: five vertices, one more than optimal. In the worst case it is much worse, a factor that grows like the logarithm of the maximum degree. The standard bad instance is bipartite: put n vertices on the left, and for every i from 2 to n add a group of about n/i right-hand vertices, each joined to i left vertices so that every left vertex gets roughly one edge per group. The left side, n vertices, is a cover, but greedy keeps finding a right-hand vertex of the current highest degree and ends up taking the whole right side, about n·ln n vertices.

Greedy still often beats the raw matching cover on real sparse graphs. Run both, prune each, keep the smaller, and report the ratio against the matching lower bound.

Weighted covers: LP rounding and local ratio

With vertex costs w(v), such as monitor prices that vary by site, the matching argument breaks: a cheap and an expensive endpoint count the same. The weighted problem is handled through its linear programming relaxation. Give each vertex a variable x_v, require x_u + x_v ≥ 1 for every edge, 0 ≤ x_v ≤ 1, and minimise the sum of w(v)·x_v. The LP optimum is a lower bound on the integer optimum, and rounding every x_v ≥ 1/2 up to 1 gives a feasible cover, because each edge constraint forces at least one of its two variables to 1/2 or more, at cost at most twice the LP value. Nemhauser and Trotter showed more: some optimal LP solution is half-integral (every x_v is 0, 1/2 or 1), and there is an optimal integer cover containing every vertex the LP sets to 1 and none it sets to 0. That makes the LP a reduction rule as well as an approximation. The duality behind it is in LP duality and the general modelling pattern in integer and linear programming.

You do not need an LP solver to get the factor 2. The local-ratio algorithm of Bar-Yehuda and Even runs in linear time: for each edge, subtract the smaller remaining weight of its two endpoints from both, and take every vertex whose remaining weight reaches zero.

def weighted_cover_local_ratio(edges, weight):
    """weight: dict vertex -> non-negative cost. 2-approximation in O(n + m)."""
    residual = dict(weight)
    for u, v in edges:
        delta = min(residual[u], residual[v])
        residual[u] -= delta          # charge both endpoints the same amount;
        residual[v] -= delta          # the optimum pays at least delta for this edge
    return {v for v, r in residual.items() if r == 0}

Every edge drives at least one endpoint to zero, so the result is a cover. The amounts subtracted form a feasible dual solution (a fractional packing of edge payments that no vertex overpays), so their sum is a lower bound on the optimum, and each edge's payment is counted at most twice, once per endpoint. With float weights, test zero against a tolerance, or a residual of 1e-17 leaves an edge uncovered.

Exact answers when k is small

When the optimum k is small relative to n, exact search is practical because the problem is fixed-parameter tractable. Two ideas carry it. A kernel shrinks the instance: Buss's rule says any vertex of degree greater than k must be in every cover of size k (otherwise all its more than k neighbours would be), so take it and decrease k; afterwards a yes-instance has at most k² edges. The LP relaxation gives a stronger kernel of at most 2k vertices via Nemhauser–Trotter. Then a bounded search tree finishes: pick any uncovered edge (u, v); one of the two must be in the cover, so branch on both.

def has_cover(adj, k):
    """adj: dict vertex -> set(neighbours), modified copy per branch. O(2^k * (n + m))."""
    edge = next(((u, v) for u in adj for v in adj[u]), None)
    if edge is None:
        return True                   # no edges left: covered
    if k == 0:
        return False
    for pick in edge:                 # u or v must be in the cover
        rest = {x: ns - {pick} for x, ns in adj.items() if x != pick}
        if has_cover(rest, k - 1):
            return True
    return False

This plain version is 2^k branches; refined branching on degree patterns brings the best published bound to about O(1.2738^k + kn) (Chen, Kanj and Xia). In production, apply degree-1, degree-2 folding and LP reductions, then hand the rest to an integer programming solver, which reports a bound gap when it cannot finish.

What hardness rules out

Better than 2 is the question that has driven decades of work, and the answer so far is that it seems out of reach. The best known polynomial algorithms achieve 2 − Θ(1/√log n), which tends to 2. On the lower side: Dinur and Safra proved that approximating within 1.3606 is NP-hard; the 2018 proof of the 2-to-2 games theorem by Khot, Minzer and Safra raised the NP-hardness threshold to √2 − ε (about 1.414); and Khot and Regev showed that, if the Unique Games Conjecture is true, no polynomial algorithm achieves 2 − ε for any fixed ε > 0. The conjecture is unproven, so the honest summary is: factor 2 is optimal assuming UGC, and anything below 1.414 is ruled out unless P = NP. See NP-completeness for the base reductions.

These are worst-case statements: bipartite graphs are exact via matching, planar graphs have a polynomial-time approximation scheme, and bounded-treewidth graphs are exact by dynamic programming.

Running it at scale

At scale the matching algorithm has properties that matter more than its ratio. It is one pass and constant extra memory per vertex, so it runs over an edge stream that does not fit in memory. It is online for edge arrivals: when a new edge arrives uncovered, match it and add both endpoints, keeping the guarantee without recomputation. And maximal matching parallelises; distributed algorithms compute one in a logarithmic number of rounds, which is how the cover is built in graph-processing frameworks.

Store the matching alongside the cover. It is the certificate that lets a later job, or an auditor, verify feasibility and the ratio without trusting the code that produced them. On edge deletion, re-scan the neighbourhoods of a removed matched edge's endpoints.

Failure modes

Trade-offs

Matching plus pruning is linear, streaming, simple and self-certifying, at the price of a guarantee that is only 2. LP rounding gives the same guarantee for weights, plus a kernel, but needs a solver; local ratio gives the guarantee for weights in linear time with no solver. Exact methods give the optimum when k is small or the graph is friendly, with runtimes that are unpredictable on adversarial inputs. The pragmatic stack is: approximate fast, prune, measure the gap, and only pay for exactness where the gap is costly. The neighbouring problem of matching itself is covered in bipartite matching and maximum matching in general graphs.

What to do next

1. Model your problem as a graph and check whether it is bipartite; if so, solve it exactly with Kőnig's theorem.
2. Implement the maximal-matching cover and the pruning pass, and log |C|, |M| and the ratio |C|/|M| on every run.
3. Add a feasibility check that scans every edge, and fail the job if it does not pass.
4. If vertices have costs, switch to local ratio, using integer weights or an explicit tolerance.
5. Try greedy and two edge orders as alternatives, prune each, and keep the smallest cover.
6. Where the gap is expensive, apply the reduction rules and run an ILP solver with a time limit.
7. Store the matching with the cover so later jobs can verify the result without rerunning the algorithm.