Chapter 9 · Hardness and Escape Routes
The NP-complete Graph Problems Worth Knowing
A table of the classics with their reduction sources, plus the exact promise that makes each one easy again.
In a contest you never prove hardness; you recognise it in 20 seconds and then read the constraints to find the escape route. This page is the recognition table.
| problem | decide / optimise | source of hardness | polynomial when… |
|---|---|---|---|
| Hamiltonian cycle / path | decision | 3-SAT (via gadget circuits), or from TSP | graph is a DAG (DAGs and Topological Order), degree-2 chains, bounded treewidth, n ≤ 20 (Held–Karp: Hamilton in O(2ⁿn²)) |
| Travelling salesman | optimisation | Hamiltonian cycle (set weights 1/2) | metric (2-approx, Christofides 3/2), n ≤ 20, small treewidth |
| Vertex cover | min | Independent set / 3-SAT | bipartite (Kőnig, Kőnig's Theorem and Minimum Covers), tree (DP), FPT in k: O(1.2738k + kn) |
| Independent set / Clique | max | 3-SAT, and each other via complement | perfect graphs, bipartite (= n − matching), interval graphs |
| Graph colouring (k-colouring, k ≥ 3) | decision | 3-SAT | k = 2 = bipartiteness (Bipartite Graphs and 2-Colouring), chordal (greedy on perfect elimination order), planar (four colour theorem is decision-free: always yes for k=4) |
| Subgraph isomorphism / motif | decision | CLIQUE (as special case) | pattern is a tree (DP), pattern size ≤ 4 (colour-coding) |
| Feedback vertex / arc set | min | Vertex cover, 3-SAT | DAG already (0), bipartite tournaments, bounded treewidth |
| Bandwidth / minimum degree spanning tree | opt | Hamiltonian path / exact-degree | degree bound 2 = Hamiltonian; else NP-hard, use MST-style heuristics |
| Max-cut | opt | Not-All-Equal 3-SAT | bipartite (= all edges), planar dual ↔ perfect matching (exact! via General Matching and Blossoms) |
| Densest k-subgraph | opt | CLIQUE | k tiny, or approximation O(√n) |
| Steiner tree | opt | Exact cover / SAT | terminals ≤ 15: Dreyfus–Wagner O(3t n + 2t nlog n) |
| Disjoint paths (2 pairs) | decision | — | polynomial for fixed number of pairs (Robertson–Seymour), NP-complete when the number is part of input |
| Edge-disjoint paths max number | opt | — | it is a flow problem → poly (Max Flow: Ford–Fulkerson, Dinic, Push–Relabel). Recognising this one is a free 30 minutes |
| Partition into triangles / exact cover by 3-sets | decision | X3C | every vertex degree ≤ 2 → paths/cycles |
| Chromatic polynomial evaluation at k ≥ 3 | #P | — | treewidth small: transfer DP along a tree decomposition |
- 2-SAT is linear (2-SAT) — one implication graph and SCCs,
- bipartite matching / vertex cover / max flow / min-cost flow are polynomial (chapters Matching: Definitions and Duality and Cuts and Flows), and a lot of "hard-looking" contest problems are these with a modelling layer on top,
- cycle detection, topological order, bridges, articulation points, SCC, Euler tours are all O(n+m) — statements like "find a permutation satisfying pairwise constraints" are DAGs and Topological Order, not SAT.
n ≤ 20 and "visit all cities" → Held–Karp. n ≤ 40 → meet in the middle. "each number appears at most twice" → degree-2 structure. k ≤ 15 in "choose k vertices" → brute force with bitsets or colour-coding. Sum of n over tests ≤ 3 · 105 and "tree" in the statement → the intended solution is a tree DP and the NP-hard-looking part is a red herring. This is the single most transferable contest skill in the book: the constraints are the intended algorithm's complexity, printed in the statement.
Vertex cover by "take the highest-degree vertex" is a ln n-approximation and can be Ω(log n) off; maximal matching gives a clean 2-approximation (The Extremal Principle). If you cannot prove your greedy is exact, submit the one with a provable factor — problems that ask for any answer within a bound are common precisely because exact is hopeless.