A Tour of NP-Complete Problems

Once you have the reduction recipe, NP-complete problems stop looking like a scattered list of curiosities and start looking like a single connected continent. They come from wildly different worlds — logic, graphs, number partitions, scheduling — yet every one is reducible to every other. Knowing the map means that the moment a new problem lands on your desk, you can often recognise its NP-complete cousins on sight, and save yourself weeks of hunting for an efficient algorithm that provably cannot exist (unless \mathsf{P} = \mathsf{NP}).

This page is that map: the great families, a few landmark members of each, the web of reductions binding them, and some field rules for spotting an NP-complete problem in the wild.

Karp's 21 and the great families

In 1972 Richard Karp took Cook's lone NP-complete problem, SAT, and reduced it down a branching tree to 21 classic combinatorial problems, proving each NP-complete. That paper turned a single result into a research programme. The problems sort naturally into a handful of families:

Family	Members	The shared shape
Logic	SAT, 3-SAT, CIRCUIT-SAT	Satisfy a Boolean constraint
Graph selection	Clique, Independent Set, Vertex Cover	Choose vertices meeting an adjacency rule
Graph colouring	3-Colouring, Graph k-Colouring	Label vertices so neighbours differ
Sequencing / tours	Hamiltonian cycle/path, Travelling Salesman (TSP)	Visit everything once, in order
Covering / packing	Set Cover, Bin Packing	Cover or pack with fewest / smallest resources
Number partition	Subset-Sum, Partition, Knapsack	Hit a numeric target with a subset
Scheduling	Job scheduling, timetabling	Assign tasks to slots under constraints

These are not academic toys — they are routing fleets, packing trucks, colouring exam timetables, allocating radio frequencies, folding proteins. NP-completeness is where an enormous share of real optimization work lives, which is exactly why the theory matters so much in practice.

The web of reductions

Every arrow below is a polynomial-time reduction A \to B ("A reduces to B"). Everything descends ultimately from SAT via Cook–Levin, and because reductions compose, each problem is a launch-pad for reaching the next. Notice how a target you care about (say TSP) traces all the way back to SAT through a chain of intermediate problems.

This is why the field grew so fast: nobody re-proves hardness from all of \mathsf{NP}. You find the nearest known-hard neighbour on this map and build one short bridge to it. The distances are small — most famous problems are just two or three reductions from SAT.

Two landmark tours through the graph

To Travelling Salesman: \text{SAT} \le_p \text{3-SAT} \le_p \text{Ham. cycle} \le_p \text{TSP}. A Hamiltonian cycle is just a TSP tour where present edges cost 1 and absent edges cost a huge number: a tour of total length n exists iff a Hamiltonian cycle does.
To Partition: \text{3-SAT} \le_p \text{Subset-Sum} \le_p \text{Partition}. Subset-Sum asks for a subset hitting target t; Partition is the special case of splitting into two equal halves, reached by padding the numbers so "half the total" becomes the target.

The decision-vs-optimization distinction matters here. TSP as an optimization problem ("find the shortest tour") is NP-hard; its decision version ("is there a tour of length \le B?") is the one that sits in \mathsf{NP} and is NP-complete — because a tour is a checkable certificate, but "no shorter tour exists" is not obviously one.

Spotting NP-completeness in the wild

After enough exposure you develop a nose for it. These heuristics are informal — always confirm with an actual reduction — but they are astonishingly reliable first-pass filters.

"Find a subset / assignment / arrangement that satisfies all constraints" — existence questions over an exponential space of configurations scream \mathsf{NP}.
You can check an answer fast but every solving idea seems to require search or backtracking — the tell-tale find-hard / verify-easy gap.
It resembles a known member — packing, covering, colouring, routing, partitioning, or scheduling with hard constraints. Pattern-match to the families above.
Small changes flip it. 2-SAT and 2-colouring are in \mathsf{P}; 3-SAT and 3-colouring are NP-complete. Shortest path is easy; longest simple path is NP-complete. A cycle through every edge (Euler) is easy; through every vertex (Hamilton) is hard. The boundary is often razor-thin — don't assume by analogy, check the exact variant.

When the nose says "NP-complete", the practical response is not despair. You reach for the coping toolkit: approximation algorithms, heuristics, exact exponential methods on small inputs, or exploiting special structure. NP-completeness tells you what to stop looking for — a fast, exact, general algorithm — so you can spend your energy on what will actually work.

Every NP-complete problem reduces to every other, so in a strict sense they are the "same" problem in different costumes — solve one efficiently and you solve them all. Yet the costumes matter enormously in practice. A problem's natural form determines which approximation algorithms apply, which special cases are tractable, and which heuristics work: Euclidean TSP admits a beautiful approximation scheme that means nothing for SAT; Vertex Cover has a clean factor-2 approximation with no analogue for Hamiltonian cycle. The reductions prove the problems are equivalent in worst-case exact difficulty, but the moment you relax to approximate or average-case, the family members part ways dramatically. Same summit, very different climbing routes.

Pattern-matching to a known NP-complete problem is a fabulous way to form a guess — and a terrible way to conclude. Superficially similar problems can land on opposite sides of the tractability line. Finding the shortest path is polynomial; the longest simple path is NP-complete. The minimum spanning tree is easy; the minimum Steiner tree is NP-complete. An Eulerian circuit (every edge once) is decidable in linear time; a Hamiltonian circuit (every vertex once) is NP-complete. So use the resemblance to decide which reduction to attempt, then actually build it — with a two-way correctness proof. The map guides your search; only a reduction settles the question.