Approximation algorithms — approximation ratio, examples: Visual walkthrough

Step 1 — What is a graph, an edge, a vertex cover?

WHAT. Look at figure s01. The five dots are vertices; the lines between them are edges. The two amber dots are a cover candidate.

WHY. Before we can say "smallest cover" we must be able to check a cover: run your finger along every line and confirm at least one endpoint is amber. If even one line has both endpoints white, it is not a cover.

PICTURE. In s01, follow the highlighted line — one endpoint is amber, so that edge is covered. The dashed line has both endpoints amber too. The set of amber dots covers all edges, so it is a valid vertex cover of size 2.

Figure — Approximation algorithms — approximation ratio, examples

Step 2 — The algorithm, drawn as it runs

WHAT. Figure s02 runs this on a 6-vertex graph. Round 1 grabs one edge (cyan), colours both ends amber, and greys out everything those two dots touched. Round 2 grabs a still-uncovered edge, and so on.

WHY grab both endpoints? Because we do not know which endpoint the optimal solution would prefer, so we take both — that costs us at most a factor of 2, which is exactly the price we will pay.

PICTURE. Notice in s02 that after each round the greyed edges are truly gone: they can never be picked again, so no two picked (cyan) edges can share a dot.

Step 3 — The picked edges form a matching

WHAT. Collect only the cyan edges we picked in Step 2. Figure s03 shows them alone — they never touch each other.

WHY they are disjoint. The moment we pick edge $(u, v)$ , step 2 erases every edge touching $u$ or $v$ . So any later picked edge cannot use $u$ or $v$ . Disjointness is forced by the erasing rule. See Maximum Matching.

PICTURE. In s03 the three amber "dominoes" sit apart, each covering two dots, none overlapping. This picture is the engine of the whole proof.

Step 4 — The lower bound: OPT must spend one dot per domino

WHAT. Take any legal cover — including the unknown optimal one. Figure s04 shows one domino edge $(u, v)$ ; the cover must include $u$ or $v$ (or both) to cover that edge.

WHY one distinct dot each. The dominoes are disjoint (Step 3). So the dot the optimum spends on domino #1 cannot also cover domino #2 — different domino, different endpoints. Therefore the optimum spends at least one distinct dot per domino.

PICTURE. In s04, each red circle marks one dot the optimum is forced to include, one per domino. Count them: at least $∣ M ∣$ .

Step 5 — Climb the LB-ladder to the ratio

WHAT. Figure s05 is a number line: $OPT$ sits somewhere above $∣ M ∣$ ; our $ALG = 2∣ M ∣$ sits at most at $2 \cdot OPT$ .

WHY multiplying keeps the direction. $2$ is positive, and multiplying an inequality by a positive number never flips it: from $∣ M ∣ \leq OPT$ we may write $2∣ M ∣ \leq 2 OPT$ .

PICTURE. The amber bracket in s05 shows the guaranteed band: whatever the unknown $OPT$ is, our answer lands inside $[OPT, 2 OPT]$ . We never had to pin down $OPT$ itself — it stays hidden between $∣ M ∣$ and $2∣ M ∣$ .

Step 6 — Edge and degenerate cases

We promised the reader never hits an unshown scenario. Figure s06 tiles the corner cases.

Worked example Every case checked

No edges ( $E = \emptyset$ ) — the trivial case. No edge is ever uncovered, so the while-loop never runs: $C = \emptyset$ , $∣ M ∣ = 0$ , and $OPT = 0$ . Here the fraction $\frac{ALG}{OPT} = \frac{0}{0}$ is undefined, so the ratio simply does not apply. We handle it separately: with nothing to cover, the algorithm already returns the exact optimum ( $C = \emptyset$ ). The ratio definition assumes $OPT > 0$ . Panel A.
A single edge. One domino, $∣ M ∣ = 1$ , $ALG = 2$ , but $OPT = 1$ (one endpoint suffices). Ratio is exactly 2 — this is the tight worst case, proving $ρ = 2$ cannot be improved for this algorithm. Panel B.
A triangle (odd cycle). Pick one edge → its two endpoints go into $C$ and become amber. But those two dots touch all three edges of the triangle, so erasing every edge incident to them wipes out the whole graph. The loop stops: the algorithm never picks a second edge. So $ALG = 2$ , while $OPT = 2$ (a triangle needs two dots). Ratio here is $2/2 = 1$ — better than the worst case. Panel C.
A star (one hub, many leaves). Optimum is just the hub ( $OPT = 1$ ). Our algorithm picks one hub–leaf edge, takes both, and then all other edges are erased (they all touch the hub): $ALG = 2$ . Ratio exactly 2 again. Panel D.
Isolated dot (degree 0). It touches no edge, is never added, never needs covering. It simply sits out. Panel E.

The one-picture summary

Figure s07 compresses the whole walkthrough: dominoes (the matching) at the bottom fix a floor $∣ M ∣ \leq OPT$ ; doubling each domino's endpoints gives $ALG = 2∣ M ∣$ as the ceiling; the unknown $OPT$ is trapped between them, so $ALG \leq 2 OPT$ falls out for free.

Recall Feynman retelling — say it to a 12-year-old

You want the fewest guards so every hallway (edge) has a guard at one of its two ends. Finding the perfect fewest is too slow. So you do this: walk around and whenever you meet a hallway with no guard, you slap a guard on both its ends and cross off every hallway those two guards can see. Keep going. The special hallways you triggered on never share a guard — they are separate "dominoes." Now here is the magic: even the perfect plan must put at least one guard on each separate domino (else that hallway is unguarded), so the perfect number is at least the number of dominoes. You used exactly two guards per domino. Two times something-not-bigger-than-perfect is at most two times perfect. You just promised "no worse than double" without ever knowing the perfect answer.

Connections

Parent: Approximation algorithms — the general LB-LADDER pattern.
Vertex Cover · Maximum Matching — the two objects this proof welds together.
Greedy Algorithms — the "grab any uncovered edge" loop.
NP-completeness — why we settle for a 2-approximation at all.
Inapproximability / PCP theorem — whether $ρ$ can be pushed below 2.