Approximation ratios & the vertex-cover 2-approximation

When optimal is out of reach

In Module 9 you proved problems like VERTEX-COVER are NP-complete: no known polynomial-time *exact* algorithm exists, and one almost certainly does not unless $P = NP$. But these problems do not go away — we still need *some* answer. An approximation algorithm runs in polynomial time and returns a solution provably close to optimal.

We measure "close" with the approximation ratio $\rho(n)$. For any input of size $n$, let $C$ be the cost of the algorithm's solution and $C^*$ the optimal cost. The algorithm is a $\rho(n)$-approximation if

$$\max\!\left(\frac{C}{C^*},\, \frac{C^*}{C}\right) \le \rho(n).$$

The $\max$ handles both directions uniformly: for a minimization problem $C \ge C^*$, so the ratio is $C/C^*$; for a maximization problem $C \le C^*$, so it is $C^*/C$. Either way $\rho(n) \ge 1$, and $\rho = 1$ means *exact*.

Two stronger guarantees come as *schemes* parameterized by an accuracy knob $\varepsilon > 0$:

- A PTAS (polynomial-time approximation scheme) is a family of $(1+\varepsilon)$-approximation algorithms, polynomial in $n$ for each *fixed* $\varepsilon$ — but the running time may blow up as $\varepsilon \to 0$ (e.g. $O(n^{2/\varepsilon})$). - An FPTAS (fully polynomial-time approximation scheme) is a PTAS whose running time is *also* polynomial in $1/\varepsilon$ (e.g. $O\!\big((1/\varepsilon)^2 n^3\big)$). This is the strongest practical guarantee.

The vertex-cover 2-approximation

A vertex cover of $G = (V, E)$ is a set $C \subseteq V$ such that every edge has at least one endpoint in $C$. Minimum vertex cover is NP-complete. Here is a startlingly simple algorithm that is never more than twice optimal:

APPROX-VERTEX-COVER(G)
  C = empty set
  E' = G.E
  while E' is not empty
      let (u, v) be an arbitrary edge of E'
      C = C union {u, v}              // take BOTH endpoints
      remove from E' every edge incident on u or v
  return C

It runs in $O(V + E)$ with adjacency lists.

Worked example. Take the graph with edges $\{(0,1),(0,4),(0,5),(2,3),(1,2)\}$. Vertex $0$ is a hub. Process edges in increasing order:

1. Pick edge $(0,1)$. Add $0$ and $1$ to $C$. Remove every edge touching $0$ or $1$ — that kills $(0,1),(0,4),(0,5),(1,2)$. Remaining: $\{(2,3)\}$.
2. Pick edge $(2,3)$. Add $2$ and $3$. Remove $(2,3)$. Nothing remains.

Result: $C = \{0,1,2,3\}$, size $4$. Every edge is covered. (A truly minimum cover here is $\{0,2\}$, size $2$ — so our answer is exactly $2\times$ optimal, the worst the ratio allows.)

Why the ratio is 2 — the lower-bound trick

The proof is the template for *every* approximation-ratio argument: you cannot see $C^*$, so you compare $C$ to a computable *lower bound* on $C^*$.

Let $A$ be the set of edges the loop actually *picks* (one per iteration). Because every edge incident on a picked endpoint is immediately deleted, no two edges in $A$ share a vertex — $A$ is a matching, in fact a *maximal* one.

- Lower bound. Any vertex cover $C^*$ must cover each edge of $A$, and those edges share no endpoints, so $C^*$ needs a *distinct* vertex for each: $|C^*| \ge |A|$. - Upper bound. Each iteration adds exactly two vertices: $|C| = 2\,|A|$. - Combine. $|C| = 2\,|A| \le 2\,|C^*|$. $\quad\blacksquare$

The matching $A$ is the lower-bound proxy for $C^*$ that makes the whole argument work without ever computing the optimum.