vertex cover

Imagine a city map where edges are streets and vertices are intersections, and you want to place a guard at some intersections so that EVERY street has a guard at one of its two ends. The fewest guards that watch all streets is a minimum vertex cover. The vertex cover problem asks whether the job can be done with at most k guards.

Formally, a vertex cover of an undirected graph G is a set of vertices such that every edge has at least one endpoint in the set. The decision problem VERTEX-COVER takes G and a number k and asks whether a vertex cover of size at most k exists. It is in NP: a candidate set of k vertices is the certificate, and a verifier scans every edge in polynomial time to confirm each is covered. The optimization version, find the smallest cover, is the NP-hard cousin.

VERTEX-COVER is NP-complete, and the cleanest proof rides on a beautiful identity: a set S is a vertex cover of G if and only if the remaining vertices (everything NOT in S) form an independent set, no edge runs between them. So G has a vertex cover of size k exactly when G has an independent set of size n - k, where n is the number of vertices. This gives an immediate reduction to and from INDEPENDENT SET, and through it from 3-SAT, so vertex cover joins the standard toolkit. Importantly, vertex cover is also a star example of coping with NP-hardness: it has a trivial factor-2 approximation (repeatedly pick both endpoints of an uncovered edge) and is fixed-parameter tractable in k, so the hardness is far from a dead end.