21 chapters · 63 sections

The mother problem. Cook (1971) proved SAT NP-complete; Karp (1972) fanned out from it to twenty more problems that look nothing alike but turn out to be the same hardness in disguise.

Karp's first reduction from SAT. Replace each Boolean variable with a 0/1 integer; replace each clause with a linear inequality. SAT becomes "does Ax ≥ b have a 0/1 solution?"

Find the largest fully-connected subgraph. Easy to state, brutal to compute, and the gateway from logic problems into graph problems.

Pick as many sets as you can without two of them sharing an element. The dual of set cover, and the problem behind every "you can't double-book this resource" rule in the world.

Pick the smallest set of vertices that touches every edge. Karp's "Node Cover" — the cleanest demonstration that NP-completeness can be cheap to recognize.

Cover every element of a universe using as few sets as possible. The greedy ln(n)-approximation is one of the most-used algorithms in industry that nobody calls by its name.

Remove the smallest set of vertices that breaks every cycle. The vertex-deletion problem behind every "this can't deadlock" guarantee.

Same idea, but you delete edges instead of vertices. Every "rank these things consistently" problem in the world reduces to it.

Find a cycle that visits every vertex exactly once. The skeleton inside every traveling-salesman variant.

Drop the directions. Still NP-complete. The undirected case has more structural lemmas (Dirac, Ore) but no general polynomial test.

Restrict SAT to clauses of at most three literals. Still NP-complete. The standard starting point for almost every reduction in the literature.

Color the vertices so adjacent vertices differ; use as few colors as possible. The graph problem behind compiler register allocation.

Partition the vertices of a graph into cliques, using as few as possible. The same as coloring the complement graph.

Cover the universe so every element is covered exactly once by your chosen sets. The problem under Sudoku, polyomino tiling, and Knuth's Dancing Links.

Find the smallest set that intersects ("hits") every set in a family. The dual of set cover, but framed from the elements' side.

Connect a chosen subset of vertices with the cheapest tree. Other vertices may be used as helpful waypoints — that is the Steiner trick.

Bipartite matching is in P. Add a third side and it becomes NP-complete — one of complexity theory's cleanest dimensional cliffs.

Pack the most value into a fixed-capacity bag. The textbook NP-complete problem with a famously fast pseudo-polynomial DP.

Schedule jobs with deadlines and penalties on a single machine. Ada was designed for problems with deadlines that matter.

Split a multiset of integers into two subsets with equal sums. Knapsack's special case, surprisingly hard, surprisingly close to easy.

Partition the vertices into two groups to maximize the edges between the groups. The crown jewel of approximation algorithms — and the canonical benchmark for quantum optimization.