the 2-approximation for vertex cover

A vertex cover of a graph is a set of vertices that touches every edge — pick people (vertices) so that every friendship (edge) has at least one of its two endpoints chosen. Finding the SMALLEST such set is NP-hard. Yet there is a famously simple algorithm that never overshoots the optimum by more than a factor of two, and it is one of the cleanest illustrations of how an approximation guarantee gets proved.

Here is the whole algorithm. Repeat until no edges remain: pick any still-uncovered edge (u, v), add BOTH endpoints u and v to your cover, then delete all edges touching u or v. The edges you picked, one at a time, share no endpoints — they form what is called a matching, in fact a maximal one. Why is the result a valid cover? Every edge you deleted was touched by u or v, so it is covered; the loop only stops when every edge is gone, so every edge is covered. Why at most 2x optimal? Say you picked k edges, so your cover has 2k vertices. Those k edges share no endpoints, so ANY cover — including the optimal one — must spend at least one distinct vertex on each of them: OPT >= k. Therefore your 2k is at most 2 * OPT. That single comparison, your cover versus the matching size, is the entire proof.

The beauty here is that the matching size k is a quantity you can compute, and it doubles as a provable lower bound on OPT — exactly the surrogate trick that makes approximation proofs work without knowing OPT. The honest limitations: taking both endpoints is wasteful (a smarter choice might cover the same edges with fewer vertices on real graphs), and the factor 2 is essentially the best simple combinatorial bound known. Doing substantially better is hard: under a widely believed conjecture (the Unique Games Conjecture), no polynomial algorithm can beat 2 by any constant, so this naive method is, in a precise sense, nearly optimal.