Karp's 21 NP-complete problems

Example

In 1972 Richard Karp showed that 21 combinatorial decision problems are NP-complete. In his naming they are:

1. satisfiability, 0-1 integer programming, clique, set packing, node cover, set covering, feedback node set;
2. feedback arc set, directed Hamilton circuit, undirected Hamilton circuit, satisfiability with at most 3 literals per clause;
3. chromatic number, clique cover, exact cover, hitting set, Steiner tree, 3-dimensional matching;
4. knapsack, job sequencing, partition, max cut.

Each problem lies in NP, since a proposed solution can be checked in polynomial time. Hardness comes from a tree of polynomial-time reductions rooted at satisfiability, which is NP-complete by the Cook–Levin theorem.

Check of one link: clique reduces to node cover, which is vertex cover. Let $G$ be a graph with $n$ vertices and let $\overline{G}$ be its complement. A set $S$ of vertices is a clique in $G$ exactly when no edge of $\overline{G}$ has both ends in $S$. That holds exactly when every edge of $\overline{G}$ has an end in the complement $V \setminus S$, so $V \setminus S$ is a vertex cover of $\overline{G}$. So $G$ has a clique of size $k$ exactly when $\overline{G}$ has a vertex cover of size $n - k$. So the map $(G, k) \mapsto (\overline{G}, n - k)$ is a polynomial-time reduction. Undirected Hamilton circuit is the Hamiltonian cycle problem.