---
title: "The NP-complete Graph Problems Worth Knowing"
summary: A table of the classics with their reduction sources, plus the exact promise that makes each one easy again.
difficulty: core
tags: [NP-complete, recognition]
see: [complexity/classes, complexity/escape]
---

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 (@directed/dag-toposort), degree-2 chains, bounded treewidth, $n \le 20$ (@euler/hamilton-dp) |
| Travelling salesman | optimisation | Hamiltonian cycle (set weights 1/2) | metric (2-approx, Christofides $3/2$), $n \le 20$, small treewidth |
| Vertex cover | min | Independent set / 3-SAT | bipartite (Kőnig, @matching/konig), tree (DP), FPT in $k$: $O(1.2738^k + kn)$ |
| Independent set / Clique | max | 3-SAT, and each other via complement | perfect graphs, bipartite (= $n$ − matching), interval graphs |
| Graph colouring ($k$-colouring, $k \ge 3$) | decision | 3-SAT | $k = 2$ = bipartiteness (@foundations/bipartite), 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 $\le 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 @matching/general-matching) |
| Densest $k$-subgraph | opt | CLIQUE | $k$ tiny, or approximation $O(\sqrt n)$ |
| Steiner tree | opt | Exact cover / SAT | terminals $\le 15$: Dreyfus–Wagner $O(3^t n + 2^t n\log 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 (@flow/maxflow). 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 \ge 3$ | #P | — | treewidth small: transfer DP along a tree decomposition |

:::note title="Three that look hard but are not"
- **2-SAT** is linear (@special/twosat) — one implication graph and SCCs,
- **bipartite matching / vertex cover / max flow / min-cost flow** are polynomial (chapters @matching/intro and @flow/cuts), 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 @directed/dag-toposort, not SAT.
:::

:::example title="Reading a problem's constraints as a confession"
$n \le 20$ and "visit all cities" → Held–Karp. $n \le 40$ → meet in the middle. "each number appears at most twice" → degree-2 structure. $k \le 15$ in "choose $k$ vertices" → brute force with bitsets or colour-coding. Sum of $n$ over tests $\le 3 \cdot 10^5$ 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.
:::

:::warning title="The trap of 'but maybe my greedy works'"
Vertex cover by "take the highest-degree vertex" is a $\ln n$-approximation and *can* be $\Omega(\log n)$ off; maximal matching gives a clean 2-approximation (@proofs/extremal). 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.
:::

:::problems
- [[CF 1198C]] Matching vs Independent Set | https://codeforces.com/problemset/problem/1198/C | hard | the reduction *is* the solution: greedily take edges, the leftovers are independent
- [[CSES 2181]] Counting Tilings | https://cses.fi/problemset/task/2181 | hard | the "hard" problem with a small width promise
:::