Richard Karp, 1972 — twenty-one classical problems, all NP-complete. The map of hardness everyone draws from.
Richard Karp, at the University of California, Berkeley, took Cook's 1971 result and showed that NP-completeness was not a curiosity confined to satisfiability. In a single paper Karp proved that twenty-one classical combinatorial problems — including 0-1 integer programming, clique, vertex cover, set cover, Hamiltonian circuit, the traveling salesman problem, partition, knapsack, and graph coloring — are all NP-complete. Each proof is a polynomial-time reduction from a known NP-complete problem to the next. The paper turned NP-completeness from a single result into a theory and a working method: when you encounter a new problem, look for a reduction from one of these twenty-one and you are done. Every NP-completeness proof in software engineering since 1972 — including the ones in chapters six, seven, and eight of this book — uses Karp's template.