Held-Karp Algorithm

Purpose: Solve the Travelling Salesman Problem exactly in $O(2^n{n}^2)$ time and $O(2^{n}n)$ memory — the classic bitmask DP. Also called the Bellman-Held-Karp algorithm.

Algorithm

1. Fix vertex $0$ as the start.
2. State: dp[mask][i] = cheapest path that starts at $0$, visits exactly the set mask of vertices, and currently sits at $i\in \text{mask}$.
3. Base: dp[1][0] = 0 (only vertex 0 visited, standing on it).
4. Transition: for every mask, every $i\in$ mask with a finite value, and every $j\notin$ mask:
   $\text{dp}[\text{mask}\cup \{j\}][j]\leftarrow \min (\cdot ,\text{dp}[\text{mask}][i]+w(i,j)).$
5. Answer: ${\min }_i\text{dp}[2^n-1][i]+w(i,0)$ for a tour, or ${\min }_i\text{dp}[2^n-1][i]$ for an open path.

Code

const long long INF = 1e18;
 
long long tsp(int n, vector<vector<long long>>& w) {
    vector<vector<long long>> dp(1 << n, vector<long long>(n, INF));
    dp[1][0] = 0;
 
    for (int mask = 1; mask < (1 << n); mask++) {
        if (!(mask & 1)) continue;                    // must contain vertex 0
        for (int i = 0; i < n; i++) {
            if (!(mask >> i & 1) || dp[mask][i] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (mask >> j & 1) continue;
                int nm = mask | (1 << j);
                dp[nm][j] = min(dp[nm][j], dp[mask][i] + w[i][j]);
            }
        }
    }
 
    long long best = INF;
    int full = (1 << n) - 1;
    for (int i = 1; i < n; i++)
        if (dp[full][i] != INF) best = min(best, dp[full][i] + w[i][0]);
    return best;
}

Reconstruct the tour by storing a par[mask][i] array, or by walking backwards and re-deriving each predecessor.

Paradigm

Dynamic programming over subsets. The insight is that a partial tour’s future cost depends only on which vertices remain and where you are — not on the order you visited them in. That collapses $n!$ orderings into $2^n\cdot n$ states.

Complexity

• Time: $O(2^n{n}^2)$
• Space: $O(2^{n}n)$ — this is usually the binding constraint

$n$	states × transitions	memory (8-byte cells)
15	$7.4\cdot 10^6$	4 MB
18	$8.5\cdot 10^7$	38 MB
20	$4.2\cdot 10^8$	168 MB — too much
22	$2.0\cdot 10^9$	738 MB — no

Proof of Correctness

Claim: dp[mask][i] is the minimum cost of a path from $0$ through exactly the vertices of mask, ending at $i$.

Induction on popcount(mask). Base: dp[1][0] = 0 is trivially correct. Step: any optimal path realising dp[mask][i] has a well-defined second-to-last vertex $k\in \text{mask}\setminus \{i\}$. Deleting $i$ leaves a path over mask \ {i} ending at $k$, which by the inductive hypothesis costs at least dp[mask ^ (1<<i)][k]. The transition considers exactly all such $k$, so it takes the minimum over all possible optimal decompositions. Conversely every value the transition produces corresponds to a real path, so no under-counting occurs. ∎

Variants / Use Cases

• Path instead of cycle — drop the closing edge $w(i,0)$
• Fixed start and end — force the final vertex
• Bitmask DP generally — assignment problems, set cover, Hamiltonian counting, matching in small graphs
• Dreyfus-Wagner — the same subset-DP idea for Steiner trees
• Held-Karp lower bound — a different Held-Karp result: a 1-tree Lagrangian relaxation used to prune branch-and-bound TSP solvers on large instances
• Approximation instead — Christofides gives a $3/2$ guarantee in polynomial time for metric TSP
• Memory relief — iterate masks in increasing popcount and keep only two layers, or use float/int32 costs