A 2-Approximation for Vertex Cover

A vertex cover of an undirected graph $G = (V, E)$ is a subset $C \subseteq V$ such that every edge $(u, v) \in E$ has at least one endpoint in $C$: that is, $u \in C$ or $v \in C$ (or both). The Vertex Cover problem asks for a vertex cover of minimum size, denoted $\mathrm{OPT}(G)$. Deciding whether a graph has a vertex cover of size $\le k$ is one of Karp's original 21 NP-complete problems, so no polynomial-time algorithm is known (or expected) to compute $\mathrm{OPT}(G)$ exactly on all inputs. A matching $M \subseteq E$ is a set of edges no two of which share an endpoint. A matching is maximal if no edge can be added to it without breaking this property — equivalently, every edge of $G$ shares at least one endpoint with some edge in $M$. Note the distinction from a maximum matching (largest possible matching size): a maximal matching is only "locally" un-extendable, and can be computed by a simple greedy sweep, whereas a maximum matching in general graphs requires the far more intricate blossom algorithm. The beauty of the vertex cover approximation is that it needs only a maximal matching — cheap to build — not a maximum one. The algorithm's central object is the vertex set $C = \bigcup_{(u,v) \in M} \{u, v\}$, the set of endpoints of a maximal matching $M$. We will show two facts: (1) $C$ is always a valid vertex cover, and (2) $|C| \le 2 \cdot \mathrm{OPT}(G)$. Together these establish that the algorithm computes, in polynomial time, a vertex cover at most twice the size of the smallest one — a 2-approximation algorithm in the formal sense used throughout Approximation Algorithms and the Approximation Ratio.

The algorithm processes edges one at a time, greedily growing a matching, and collects both endpoints of every matching edge into the cover. ``` VERTEX-COVER-APPROX(G = (V, E)): C ← ∅ // vertex cover under construction E' ← E // edges not yet "handled" while E' ≠ ∅: pick an arbitrary edge (u, v) ∈ E' C ← C ∪ {u, v} remove from E' every edge incident to u or to v return C ``` Each iteration picks an edge whose endpoints are not yet touched by the cover under construction — because any edge sharing an endpoint with a previously chosen edge was already deleted from $E'$. The set of edges actually chosen across the run,

is therefore a matching: no two chosen edges share an endpoint, by construction (choosing $(u,v)$ immediately purges every edge touching $u$ or $v$, including any future candidate that would collide). Moreover $M$ is maximal: the loop only terminates when $E' = \emptyset$, meaning every remaining edge of $G$ was deleted because it touched some already-chosen edge's endpoint — so no edge of $G$ can be added to $M$ without creating a shared endpoint. The algorithm is intentionally agnostic about which edge is picked at each step — correctness and the approximation ratio hold no matter what selection rule is used, as long as it is some uncovered edge. This robustness is part of why the algorithm is so simple to implement and reason about.

Implementation detail. To run in linear time, maintain an adjacency-list representation and a boolean array `covered[v]` marking whether vertex $v$ is already in $C$. Iterate over the edge list once; for each edge $(u,v)$ with neither endpoint covered, add both to $C$ and mark them covered. This single pass replaces the "remove incident edges" step — an edge with a covered endpoint is implicitly skipped, without ever physically deleting it: ``` VERTEX-COVER-APPROX-LINEAR(G = (V, E)): C ← ∅ covered[v] ← false for all v ∈ V for each edge (u, v) ∈ E: // any fixed order works if covered[u] = false and covered[v] = false: C ← C ∪ {u, v} covered[u] ← true covered[v] ← true return C ```

Running time. The linear-pass version examines each of the $|E|$ edges exactly once, doing $O(1)$ work per edge (two array lookups, possibly two array writes and two set insertions). Building the adjacency structure takes $O(V + E)$. Total running time is

which is optimal up to constants, since simply reading the input graph already takes $\Omega(V + E)$ time. Space usage is $O(V + E)$ for the graph plus $O(V)$ for the `covered` array and the output set — no auxiliary data structure grows superlinearly.

Correctness — $C$ is a valid vertex cover. Consider any edge $(x, y) \in E$. If neither endpoint was ever marked covered by the time the loop reaches $(x,y)$, the algorithm selects it, adding both $x$ and $y$ to $C$ — so $(x,y)$ is covered. If instead the loop skips $(x,y)$, it is because at least one of $x, y$ was already marked covered by an earlier iteration — so again $(x,y)$ has an endpoint in $C$. Either way every edge has an endpoint in $C$; hence $C$ is a vertex cover of $G$. This argument only used that the loop examines every edge and never un-marks a vertex, so it holds regardless of edge processing order.

The approximation guarantee — $|C| \le 2 \cdot \mathrm{OPT}(G)$. Let $M$ be the matching consisting of exactly the edges chosen during the run (one edge per iteration of the abstract version), and let $C$ be the set of their endpoints, so $|C| = 2|M|$ since matching edges are pairwise vertex-disjoint. Claim: $\mathrm{OPT}(G) \ge |M|$. Let $C^*$ be any vertex cover of $G$, in particular a minimum one with $|C^*| = \mathrm{OPT}(G)$. Since $M$ is a matching, its edges are pairwise disjoint — no vertex belongs to two edges of $M$. Because $C^*$ is a vertex cover, every edge of $M$ (being an edge of $G$) must have at least one endpoint in $C^*$. Assign to each edge $e \in M$ one endpoint that lies in $C^*$ — call this a witness for $e$. Because the edges of $M$ share no vertices, distinct edges of $M$ must receive distinct witnesses (the witness for $e$ is a vertex of $e$, and no vertex belongs to two different matching edges). This gives an injective map from $M$ into $C^*$, so

Combining the two facts:

This is exactly the definition of a 2-approximation: the algorithm's output size is at most twice the true optimum, for every input graph, not merely on average. Note the proof never needed $M$ to be a maximum matching — only maximal (un-extendable) — which is why the cheap greedy construction suffices; using a true maximum matching would not improve the worst-case ratio (see the tight example below) and would cost much more to compute.

Tightness of the factor 2. The bound is not an artifact of a loose proof — there are graphs on which $|C|$ is exactly $2 \cdot \mathrm{OPT}(G)$. Take the complete bipartite graph $K_{n,n}$ with parts $\{u_1,\dots,u_n\}$ and $\{v_1,\dots,v_n\}$. A single side, say $\{u_1,\dots,u_n\}$, is already a vertex cover of size $n$, so $\mathrm{OPT}(K_{n,n}) = n$. But a maximal matching in $K_{n,n}$ can be the perfect matching $\{(u_i, v_i)\}_{i=1}^n$, giving $|M| = n$ and $|C| = 2n = 2\,\mathrm{OPT}$. So the analysis is asymptotically tight for this algorithm — no smarter argument will squeeze a better constant out of the maximal-matching approach itself (better ratios require fundamentally different techniques, and no polynomial algorithm with ratio strictly better than $2 - \epsilon$ for any constant $\epsilon>0$ is known, with strong evidence — resting on the Unique Games Conjecture — that none exists).

Honesty about limitations. This is a worst-case guarantee, and it can be loose in practice: on many real graphs the algorithm's output is far closer to optimal than the factor-2 bound suggests, but the algorithm offers no way to know this at runtime without also computing (or bounding) the true optimum. It also gives no control over which twice-optimal cover you get — different edge orderings can produce different $C$ of different sizes, all still within the factor-2 envelope. Practitioners often run several random orderings and keep the smallest resulting cover, or layer local-search improvements on top, a theme picked up in Heuristics and Local Search.

Consider the 7-vertex graph drawn in the figure above, with vertex set $\{a,b,c,d,e,f,g\}$ and edge set

Run `VERTEX-COVER-APPROX-LINEAR` processing edges in the listed order.

The algorithm returns $C = \{a, b, c, d, f, g\}$, size $6$. (This differs from the figure's illustrative matching $\{(a,b),(d,e)\}$ only because of edge-processing order — both are valid maximal matchings, and both yield legitimate 2-approximate covers; here the matching realized is $\{(a,b),(c,d),(f,g)\}$.)

Check it is a valid cover. Every edge has an endpoint in $C$: $(a,b)$✓, $(b,c)$✓ via $b,c$, $(a,c)$✓, $(c,d)$✓, $(d,e)$✓ via $d$, $(d,f)$✓, $(f,g)$✓, $(g,e)$✓ via $g$. All 8 edges are covered.

Compare to the true optimum. Inspecting the graph directly: $\{c, d, g\}$ is a vertex cover — check each edge: $(a,b)$ needs... actually $(a,b)$ touches neither $c$, $d$, nor $g$, so this fails. Trying again: the triangle $\{a,b,c\}$ forces at least 2 of its 3 vertices into any cover (a triangle's minimum cover size is 2), and separately $d,e,f,g$ form a 4-cycle, whose minimum cover size is 2 (e.g. $\{d, g\}$, checking: $(d,e)$✓, $(d,f)$✓, $(f,g)$✓, $(g,e)$✓). Since the triangle and the 4-cycle share only the vertex $d/c$ connection edge $(c,d)$, we need a cover of the triangle, a cover of the 4-cycle, and coverage of the bridge edge $(c,d)$. Taking $\{b, c, d, g\}$: $(a,b)$✓, $(b,c)$✓, $(a,c)$✓, $(c,d)$✓, $(d,e)$✓, $(d,f)$✓, $(f,g)$✓, $(g,e)$✓ — a valid cover of size 4. One can verify (by trying all size-3 subsets, or arguing the triangle alone needs 2 and the 4-cycle needs 2, and no vertex is shared between "the 2 triangle picks" and "the 2 cycle picks" except possibly $c$ or $d$) that $\mathrm{OPT}(G) = 4$. So here the algorithm returned $6$ against an optimum of $4$ — a ratio of $1.5$, comfortably inside the guaranteed factor of $2$, illustrating that the worst case ($K_{n,n}$-like tightness) is not always hit but is always respected as an upper bound.

The theory of NP-completeness that makes exact vertex cover intractable, and the theory of approximation that makes this algorithm meaningful, were built by a small set of foundational figures in complexity theory in the early 1970s. Vertex Cover itself appears among Richard Karp's 1972 list of 21 problems shown NP-complete by reduction, cementing it as a canonical hard problem alongside SAT and clique.

Vertex cover and its 2-approximation appear wherever a system must place a minimum set of "watchers," "hitters," or "testers" that touch every pairwise interaction in a network. In network security and monitoring, the algorithm models placing intrusion-detection probes on routers so every communication link passes through at least one monitored router — exactly the motivating scenario for this article. In bioinformatics, vertex cover formulations arise in phylogenetic footprinting and in finding minimal sets of genes/proteins whose removal disrupts all pairwise interactions in a protein-interaction network. In VLSI design and testing, minimum test-point placement to detect all possible faults on a circuit's connections reduces to covering problems closely related to vertex cover. The algorithm is also a standard teaching and benchmarking baseline in the theory of approximation: it is often the very first constructive 2-approximation students see with a complete, checkable proof, making it a template that recurs in the analysis of other covering and packing problems, including Metric TSP Approximation, where a different combinatorial witness (a minimum spanning tree) plays the analogous lower-bounding role. In production settings where exact solvers (integer programming, branch-and-bound) are too slow on large graphs, engineers frequently use the maximal-matching cover as a fast initial feasible solution, then refine it with local-search moves — connecting directly to the ideas in Heuristics and Local Search — while retaining the provable factor-2 ceiling as a safety guarantee if refinement runs out of time.

Ask the tutor: How does the weighted vertex cover LP-rounding algorithm achieve the same factor-2 guarantee when vertex costs differ?