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^{\ast }$ the optimal cost. The algorithm is a $\rho (n)$-approximation if

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

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

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

• A PTAS (polynomial-time approximation scheme) is a family of $(1+\epsilon )$-approximation algorithms, polynomial in $n$ for each fixed $\epsilon$ — but the running time may blow up as $\epsilon \to 0$ (e.g. $O(n^{2/\epsilon })$).
• An FPTAS (fully polynomial-time approximation scheme) is a PTAS whose running time is also polynomial in $1/\epsilon$ (e.g. $O((1/\epsilon {)}^2{n}^3)$). 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^{\ast }$, so you compare $C$ to a computable lower bound on $C^{\ast }$.

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^{\ast }$ must cover each edge of $A$, and those edges share no endpoints, so $C^{\ast }$ needs a distinct vertex for each: $|C^{\ast }|\ge |A|$.
• Upper bound. Each iteration adds exactly two vertices: $|C|=2|A|$.
• Combine. $|C|=2|A|\le 2|C^{\ast }|$. $■$

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