Held-Karp Algorithm

A Bit of History

In 1962, Michael Held and Richard Karp — the same Karp behind Edmonds-Karp's max-flow algorithm from a previous deep dive — published "A Dynamic Programming Approach to Sequencing Problems," showing that the Traveling Salesman Problem previewed in Part 14 could be solved exactly far faster than brute-force enumeration, by cleverly organizing subproblems around subsets of visited cities rather than sequences. The same dynamic-programming-over-subsets idea was independently discovered around the same time by Richard Bellman (of Bellman-Ford fame), and is sometimes called the Bellman-Held-Karp algorithm in recognition of that overlap.

Working Principle

Brute force tries all \((n-1)!\) possible orderings of the remaining \(n-1\) cities after fixing a start. Held-Karp's insight: the cost of the cheapest way to visit a specific set of cities and end at a specific city does not depend on the order in which the earlier cities were visited — only on which set was visited and where the path currently ends. That means the state space is not "all orderings" but merely "all (subset, endpoint) pairs" — vastly smaller.

Define \(C(S, j)\) as the minimum cost of a path starting at city 0, visiting exactly the set of cities \(S\) (with \(0 \in S\)), and ending at city \(j \in S\). The recurrence:

$$C(S, j) = \min_{k \in S, k \neq j} \Big[ C(S \setminus \{j\}, k) + d(k, j) \Big]$$

with base case \(C(\{0\}, 0) = 0\). The final answer is \(\min_{j \neq 0} \big[C(\{0,\ldots,n-1\}, j) + d(j, 0)\big]\), closing the tour back to the start.

Worked Example

For 4 cities \(\{0,1,2,3\}\) with a symmetric distance matrix, the algorithm builds up \(C(S,j)\) for increasingly large subsets \(S\): first all 2-element subsets containing city 0 (i.e., \(\{0,1\}\), \(\{0,2\}\), \(\{0,3\}\)), then all 3-element subsets, then finally the full 4-element set. At each stage, every new value reuses previously computed smaller-subset values — never recomputing a path cost from scratch. With \(n=4\), this means at most \(2^4 \times 4 = 64\) subproblems total, versus \(3! = 6\) full brute-force tours for this tiny example — the savings become dramatic only as \(n\) grows.

Correctness

The recurrence is correct by a straightforward optimal-substructure argument: any optimal path visiting set \(S\) and ending at \(j\) must have arrived at \(j\) from some other city \(k \in S\), having previously visited exactly \(S \setminus \{j\}\) and ended at \(k\) — and that sub-path must itself be optimal (if a cheaper way to visit \(S \setminus \{j\}\) ending at \(k\) existed, splicing it in would produce a cheaper overall path, a contradiction). Trying all valid choices of \(k\) and keeping the minimum is therefore guaranteed to find the true optimum.

Complexity Analysis

There are \(O(2^n)\) subsets and \(n\) choices of endpoint \(j\), and each recurrence evaluation considers up to \(n\) choices of \(k\):

$$\text{Time: } O(n^2 \cdot 2^n) \qquad \text{Space: } O(n \cdot 2^n)$$

This is exponential — still impractical for very large instances — but it is a dramatic improvement over brute force's \(O(n!)\), and remains, over 60 years later, essentially the best known exact algorithm for general TSP instances.

Implementation

def held_karp(dist):
    """dist: n x n distance matrix. Returns minimum tour cost starting/ending at city 0."""
    n = len(dist)
    INF = float('inf')
    # C[mask][j] = min cost to visit exactly the cities in `mask`, ending at j
    C = [[INF] * n for _ in range(1 << n)]
    C[1][0] = 0  # start at city 0 alone

    for mask in range(1 << n):
        if not (mask & 1):
            continue  # city 0 must always be in the visited set
        for j in range(n):
            if not (mask & (1 << j)) or C[mask][j] == INF:
                continue
            for k in range(n):
                if mask & (1 << k):
                    continue
                next_mask = mask | (1 << k)
                new_cost = C[mask][j] + dist[j][k]
                if new_cost < C[next_mask][k]:
                    C[next_mask][k] = new_cost

    full_mask = (1 << n) - 1
    return min(C[full_mask][j] + dist[j][0] for j in range(1, n))

dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print(held_karp(dist))  # 80

#include <vector>
#include <limits>
#include <iostream>
using namespace std;

int heldKarp(vector<vector<int>>& dist) {
    int n = dist.size();
    const int INF = numeric_limits<int>::max() / 2;
    vector<vector<int>> C(1 << n, vector<int>(n, INF));
    C[1][0] = 0;

    for (int mask = 1; mask < (1 << n); mask++) {
        if (!(mask & 1)) continue;
        for (int j = 0; j < n; j++) {
            if (!(mask & (1 << j)) || C[mask][j] == INF) continue;
            for (int k = 0; k < n; k++) {
                if (mask & (1 << k)) continue;
                int nextMask = mask | (1 << k);
                int newCost = C[mask][j] + dist[j][k];
                if (newCost < C[nextMask][k]) C[nextMask][k] = newCost;
            }
        }
    }

    int fullMask = (1 << n) - 1;
    int best = INF;
    for (int j = 1; j < n; j++) best = min(best, C[fullMask][j] + dist[j][0]);
    return best;
}

int main() {
    vector<vector<int>> dist = {
        {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}
    };
    cout << heldKarp(dist) << endl;  // 80
    return 0;
}

import java.util.*;

class HeldKarp {
    static int solve(int[][] dist) {
        int n = dist.length;
        final int INF = Integer.MAX_VALUE / 2;
        int[][] C = new int[1 << n][n];
        for (int[] row : C) Arrays.fill(row, INF);
        C[1][0] = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            if ((mask & 1) == 0) continue;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0 || C[mask][j] == INF) continue;
                for (int k = 0; k < n; k++) {
                    if ((mask & (1 << k)) != 0) continue;
                    int nextMask = mask | (1 << k);
                    int newCost = C[mask][j] + dist[j][k];
                    if (newCost < C[nextMask][k]) C[nextMask][k] = newCost;
                }
            }
        }

        int fullMask = (1 << n) - 1;
        int best = INF;
        for (int j = 1; j < n; j++) best = Math.min(best, C[fullMask][j] + dist[j][0]);
        return best;
    }

    public static void main(String[] args) {
        int[][] dist = {
            {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}
        };
        System.out.println(solve(dist));  // 80
    }
}

Real-World Applications

Exercises

1. Trace through the Held-Karp recurrence by hand for a 4-city instance, filling in the \(C(S,j)\) table for all subsets containing city 0.
2. Explain why representing subsets as bitmasks (rather than, say, Python sets or lists) is essential for the algorithm's practical performance, not just a stylistic choice.
3. Compare the number of subproblems Held-Karp solves for \(n=15\) against the number of tours brute force would enumerate, and comment on how quickly the gap grows.
4. Challenge: Modify the implementation to also reconstruct and print the optimal tour itself, not just its cost (hint: track which \(k\) achieved the minimum at each step).

Limitations