Escape Routes: What To Do When It Is NP-Hard

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

#1. DP over subsets — n ≤ 22

dp[M][v]: 2ⁿ · n states, O(n) (or O(deg)) each.

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 ≈ 9 · 10⁷ states — fine; 2²⁶ · 26 ≈ 1.7 · 10⁹ — too slow and memory 2²⁶ · 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ⁿ) memory).

#2. Meet in the middle — n ≤ 44

Split into two halves, enumerate 2^n/2 subsets each, then combine by sorting + two pointers or binary search.

// 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 · 2²⁰ = 2 · 10⁶ elements instead of 2⁴⁰ — 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 ≤ 40–60 on nice tests

The prunes that matter, in order of value:

1. 1

   order the branching so that the strongest constraint is decided first (largest degree, smallest domain);

2. 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. 3

   forward checking: after assigning, remove impossible values; fail immediately on an empty domain,

4. 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. 5

   restart / randomise the order if a fixed order blows up on one adversarial test.

#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(√n), so "exponential in √n" is a real planar algorithm),
• dominating set on planar graphs: O(2^O(√n) n) via the same,
• "at most k edges to delete to become bipartite": iterative compression or O(4^k · n).

#5. Approximation and randomisation