---
title: "Escape Routes: What To Do When It Is NP-Hard"
summary: Small n, meet in the middle, branch and bound, FPT by a parameter, and approximation — with the running-time arithmetic for each.
difficulty: hard
tags: [exponential, DP, branch and bound]
see: [complexity/npc-graphs, euler/hamilton-dp]
---

Five techniques, ranked by how the constraints tell you which one is intended.

## 1. DP over subsets — $n \le 22$
$\operatorname{dp}[M][v]$: $2^n \cdot n$ states, $O(n)$ (or $O(\deg)$) each.
```cpp subset-dp.cpp
for (int M = 1; M < (1 << n); M++)
    for (int v = 0; v < n; v++) if (M >> v & 1) {
        int P = M ^ (1 << v);
        for (int u = 0; u < n; u++) if (P >> u & 1 && adj[v][u])
            dp[M][v] = min(dp[M][v], dp[P][u] + w(u, v));
    }
```
Arithmetic to check first: $2^{22} \cdot 22 \approx 9 \cdot 10^7$ states — fine; $2^{26} \cdot 26 \approx 1.7 \cdot 10^9$ — too slow *and* memory $2^{26} \cdot 26$ bytes = 1.7 GB, too big. Memory is usually the binding constraint: iterate masks and keep only `dp[mask][v]` as `int` (4 bytes), or drop the `[v]` dimension entirely when the transition depends only on $M$ (then $O(2^n)$ memory).

:::props title="Variants of the same 8 lines"
- Hamiltonian path/cycle and TSP (@euler/hamilton-dp),
- assignment problem with $n \le 20$ (faster than Hungarian for tiny $n$),
- "minimum number of groups with a constraint on each" — iterate subsets, `dp[M] = min over sub ⊆ M`, which is $O(3^n)$ total: enumerate submasks with `for (sub = M; sub; sub = (sub-1) & M)`,
- graph colouring in $O(2^n n)$: precompute which subsets are independent, then "cover $V$ by $\le k$ independent sets" = subset DP, or use inclusion–exclusion for the chromatic polynomial,
- Steiner tree: $\operatorname{dp}[M][v]$ over terminal subsets with Dijkstra between layers, $O(3^t n + 2^t n \log n)$.
:::

## 2. Meet in the middle — $n \le 44$
Split into two halves, enumerate $2^{n/2}$ subsets each, then combine by sorting + two pointers or binary search.
```cpp meet-in-middle.cpp
// subset sum to target T with n <= 40
vector<ll> A, B;                       // all 2^(n/2) subset sums of each half
sort(B.begin(), B.end());
ll best = -1;
for (ll a : A) {
    auto it = lower_bound(B.begin(), B.end(), T - a);
    if (it != B.end() && a + *it == T) { best = T; break; }
}
```
$2 \cdot 2^{20} = 2 \cdot 10^6$ elements instead of $2^{40}$ — the entire trick is that a sorted list can be searched, so pairs become cheap.

## 3. Branch and bound / backtracking with a real prune — $n \le 40$–$60$ on nice tests
The prunes that matter, in order of value:
:::steps
1. **order** the branching so that the strongest constraint is decided first (largest degree, smallest domain);
2. **bound** with a fast relaxation (LP-free: fractional knapsack bound, MST bound for TSP, greedy colour count) and cut the subtree when the bound cannot beat the incumbent,
3. **forward checking**: after assigning, remove impossible values; fail immediately on an empty domain,
4. **memoise on a canonical state** (a bitmask of decided vertices) — the moment you memoise, branch and bound becomes DP and the bound stops mattering,
5. **restart / randomise** the order if a fixed order blows up on one adversarial test.
:::

:::example title="Maximal independent set in a graph with n = 50"
Branch on a vertex $v$: either take it (delete $N[v]$) or forbid it (delete $v$). Recurrence $T(n) = T(n-1) + T(n-d-1)$; with $d \ge 2$ that is $\approx 1.32^n$. Measure-and-conquer analyses push it to $1.1996^n$ by handling low-degree vertices with dedicated rules — which is exactly what the "branch on the degree-2 vertex and contract it" line in real code is doing.
:::

## 4. FPT in a parameter you noticed
"Exponential in $k$, polynomial in $n$" — kernelise then branch:
- vertex cover: bounded search tree $O(2^k k)$, or $O(1.2738^k + kn)$ with branching rules on degree-3+ vertices; LP relaxation gives a $2k$-vertex kernel,
- treewidth $k$: solve any MSO/DP problem in $O(f(k) n)$ once you have a tree decomposition (and for planar graphs, $k = O(\sqrt n)$, so "exponential in $\sqrt n$" is a real planar algorithm),
- dominating set on planar graphs: $O(2^{O(\sqrt n)} n)$ via the same,
- "at most $k$ edges to delete to become bipartite": iterative compression or $O(4^k \cdot n)$.

## 5. Approximation and randomisation
:::props title="Provably-good answers you can code in 5 lines"
- maximal matching → 2-approx for vertex cover and for maximum matching (@proofs/extremal),
- random partition, keep the better side → $\ge m/2$ edges in a bipartite subgraph; derandomise by greedy flipping, which is the same bound,
- Christofides for metric TSP: MST + minimum perfect matching on the odd-degree vertices ($3/2$) — uses @matching/general-matching as a subroutine, which is why that page exists,
- local search "improve by swapping 2" for TSP: $O(1)$-factor in practice, no proof,
- simulated annealing / random restarts for "output any good answer" scoring problems: measure your own bound rather than trusting folklore.
:::

:::note title="Choosing among the five, in one rule"
Read $n$ and $k$ and compute. $2^n$ fits → subset DP. $2^{n/2}$ fits → meet in the middle. $n$ huge but $k \le 20$ → FPT/branch. $n$ huge, no parameter, "output any" → approximation with a proof you can state. If none of the four fit, re-read the statement: you have mis-modelled the problem, which is by far the most common reason.
:::

:::problems
- [[CSES 1690]] Hamiltonian Flights | https://cses.fi/problemset/task/1690 | core | subset DP, directed
- [[CSES 1158]] Book Shop | https://cses.fi/problemset/task/1158 | easy | the DP-size arithmetic, in public
:::