Held-Karp Algorithm

The Exact TSP Problem

Given costs $d(i,j)$ between $n$ cities, find a minimum-cost cycle that starts at city $0$, visits every other city exactly once, and returns to $0$. Costs may be symmetric, as with ordinary distances, or asymmetric, as with one-way travel times.

Fixing city $0$ removes rotations of the same cycle, but brute force still considers $(n-1)!$ orders. Held–Karp replaces those full histories with reusable summaries.

Compressing Route Histories

Different visit orders can lead to the same visited set and endpoint. Their past costs differ, but every legal continuation available from that state is identical. The more expensive prefix is therefore dominated: appending the same future can never make it cheaper.

State and Recurrence

Let $DP[S][j]$ be the minimum cost of a path that starts at $0$, visits exactly the cities in $S$, and ends at $j$. Valid states contain both $0$ and $j$.

The base state is $DP[\{0\}][0]=0$. The recurrence asks one question: which city $k$ was visited immediately before $j$? Remove $j$, solve the smaller endpoint state at $k$, then add the final edge $k\to j$.

After all cities are visited, the path is not yet a tour. Close it explicitly:

Bitmask Representation

A bitmask stores subset membership in one integer. Bit $i$ is $1$ exactly when city $i$ belongs to the subset. For four cities, mask $1101_2$ represents $\{0,2,3\}$.

Bitmasks are not what makes the recurrence correct; they make dense subset tables compact, indexable, and fast. A sparse map keyed by subsets can express the same DP when only selected states should be stored.

Four-City Trace

Use the symmetric distance matrix from the implementation:

For example, the full-set state ending at city $2$ is

The two candidates correspond to arriving from city $1$ or city $3$. Closing from $2$ adds $d(2,0)=15$, producing an optimal tour cost of $80$.

Reconstructing the Tour

A cost table alone forgets which predecessor achieved each minimum. Store parent[mask][j] whenever a transition improves a state. After choosing the best final endpoint, repeatedly:

1. record the current endpoint $j$;
2. read its predecessor $k=parent[mask][j]$;
3. clear bit $j$ from the mask and continue from $k$;
4. reverse the recovered prefix, then append city $0$ to close the cycle.

Why the Recurrence Is Correct

Prove the state invariant by induction on $|S|$. The base state $DP[\{0\}][0]=0$ is correct. For a larger state $(S,j)$, every valid path must enter $j$ from exactly one predecessor $k\in S\setminus\{j\}$. Before that last edge, it is a path for state $(S\setminus\{j\},k)$.

By the induction hypothesis, the table stores the cheapest such prefix. Replacing it with any more expensive prefix cannot improve the completed path, so minimizing over every possible predecessor finds the cheapest path for $(S,j)$. Finally, every Hamiltonian tour has one last city before returning to $0$; minimizing over that endpoint examines every possible tour ending.

Implementation

def held_karp(dist):
    """Return (one optimal tour, its cost) for a square distance matrix."""
    n = len(dist)
    if n == 0 or any(len(row) != n for row in dist):
        raise ValueError("dist must be a nonempty square matrix")
    if n == 1:
        return [0, 0], 0

    INF = float("inf")
    states = 1 << n
    # dp[mask][j]: cheapest 0-to-j path visiting exactly `mask`.
    dp = [[INF] * n for _ in range(states)]
    parent = [[-1] * n for _ in range(states)]
    dp[1][0] = 0

    for mask in range(states):
        if not (mask & 1):
            continue
        for j in range(n):
            if not (mask & (1 << j)) or dp[mask][j] == INF:
                continue
            for k in range(n):
                if mask & (1 << k):
                    continue
                next_mask = mask | (1 << k)
                candidate = dp[mask][j] + dist[j][k]
                if candidate < dp[next_mask][k]:
                    dp[next_mask][k] = candidate
                    parent[next_mask][k] = j

    full = states - 1
    end = min(range(1, n), key=lambda j: dp[full][j] + dist[j][0])
    best_cost = dp[full][end] + dist[end][0]
    if best_cost == INF:
        raise ValueError("no finite Hamiltonian tour exists")

    tour = [end]
    mask, j = full, end
    while j != 0:
        previous = parent[mask][j]
        mask ^= 1 << j
        j = previous
        tour.append(j)
    tour.reverse()
    tour.append(0)
    return tour, best_cost

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

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

struct Result { vector<int> tour; long long cost; };

Result heldKarp(const vector<vector<long long>>& dist) {
    int n = dist.size();
    if (n == 0 || n >= 31) throw invalid_argument("unsupported city count");
    for (const auto& row : dist)
        if ((int)row.size() != n) throw invalid_argument("dist must be square");
    if (n == 1) return {{0, 0}, 0};

    const long long INF = numeric_limits<long long>::max() / 4;
    int states = 1 << n;
    vector<vector<long long>> dp(states, vector<long long>(n, INF));
    vector<vector<int>> parent(states, vector<int>(n, -1));
    dp[1][0] = 0;

    for (int mask = 1; mask < states; mask++) {
        if (!(mask & 1)) continue;
        for (int j = 0; j < n; j++) {
            if (!(mask & (1 << j)) || dp[mask][j] == INF) continue;
            for (int k = 0; k < n; k++) {
                if (mask & (1 << k)) continue;
                int next = mask | (1 << k);
                long long candidate = dp[mask][j] + dist[j][k];
                if (candidate < dp[next][k]) {
                    dp[next][k] = candidate;
                    parent[next][k] = j;
                }
            }
        }
    }

    int full = states - 1, end = -1;
    long long best = INF;
    for (int j = 1; j < n; j++) {
        long long candidate = dp[full][j] + dist[j][0];
        if (candidate < best) best = candidate, end = j;
    }
    if (end == -1) throw runtime_error("no finite Hamiltonian tour");

    vector<int> tour{end};
    int mask = full, j = end;
    while (j != 0) {
        int previous = parent[mask][j];
        mask ^= 1 << j;
        j = previous;
        tour.push_back(j);
    }
    reverse(tour.begin(), tour.end());
    tour.push_back(0);
    return {tour, best};
}

int main() {
    vector<vector<long long>> dist = {
        {0,10,15,20}, {10,0,35,25}, {15,35,0,30}, {20,25,30,0}
    };
    Result result = heldKarp(dist);
    cout << "Cost: " << result.cost << "\nTour:";
    for (int city : result.tour) cout << " " << city;
}

import java.util.*;

class HeldKarp {
    static class Result {
        final int[] tour;
        final long cost;
        Result(int[] tour, long cost) { this.tour = tour; this.cost = cost; }
    }

    static Result solve(long[][] dist) {
        int n = dist.length;
        if (n == 0 || n >= 31) throw new IllegalArgumentException("unsupported city count");
        for (long[] row : dist)
            if (row.length != n) throw new IllegalArgumentException("dist must be square");
        if (n == 1) return new Result(new int[]{0, 0}, 0);

        final long INF = Long.MAX_VALUE / 4;
        int states = 1 << n;
        long[][] dp = new long[states][n];
        int[][] parent = new int[states][n];
        for (long[] row : dp) Arrays.fill(row, INF);
        for (int[] row : parent) Arrays.fill(row, -1);
        dp[1][0] = 0;

        for (int mask = 1; mask < states; mask++) {
            if ((mask & 1) == 0) continue;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0 || dp[mask][j] == INF) continue;
                for (int k = 0; k < n; k++) {
                    if ((mask & (1 << k)) != 0) continue;
                    int next = mask | (1 << k);
                    long candidate = dp[mask][j] + dist[j][k];
                    if (candidate < dp[next][k]) {
                        dp[next][k] = candidate;
                        parent[next][k] = j;
                    }
                }
            }
        }

        int full = states - 1, end = -1;
        long best = INF;
        for (int j = 1; j < n; j++) {
            long candidate = dp[full][j] + dist[j][0];
            if (candidate < best) { best = candidate; end = j; }
        }
        if (end == -1) throw new IllegalStateException("no finite Hamiltonian tour");

        List<Integer> tour = new ArrayList<>();
        int mask = full, j = end;
        tour.add(j);
        while (j != 0) {
            int previous = parent[mask][j];
            mask ^= 1 << j;
            j = previous;
            tour.add(j);
        }
        Collections.reverse(tour);
        tour.add(0);
        return new Result(tour.stream().mapToInt(Integer::intValue).toArray(), best);
    }

    public static void main(String[] args) {
        long[][] dist = {
            {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}
        };
        Result result = solve(dist);
        System.out.println(Arrays.toString(result.tour) + " cost=" + result.cost);
    }
}

All three versions now retain predecessor choices and return one optimal tour as well as its cost. They use a dense table for clarity; memory becomes the practical bottleneck before the bit-shift limit does.

Complexity and the Memory Wall

There are $2^n$ masks, up to $n$ endpoints per mask, and up to $n$ next-city transitions per reachable state:

The dense implementation allocates $n2^n$ table cells even though many are invalid. Fixing city $0$ and storing only reachable endpoint states improves constants, not the exponential class.

If only the optimum value is needed, process states by subset size and keep fewer layers, or store reachable states sparsely. If the tour must be reconstructed, retain parents, recompute selected layers, or use a divide-and-conquer reconstruction strategy. Each choice trades memory, runtime, and implementation complexity.

Useful Variants

Be careful when adding time windows, vehicle capacity, or several salespeople. Subset and endpoint may no longer summarize every fact relevant to the future; extra state dimensions or a different optimization model are then required.

Common Pitfalls and a Reliable Checklist

Where Held–Karp Is Useful

• Benchmarking: measure the optimality gap of nearest-neighbor, local-search, or learned routing methods on small instances.
• Sequencing: order a small set of manufacturing, inspection, or robotic operations with pairwise transition costs.
• Clustered optimization: solve small clusters exactly while a higher-level heuristic connects the clusters.
• Subset-DP template: adapt the same mask-and-endpoint pattern to Hamiltonian paths, precedence-constrained tours, and other sequencing problems.

Exercises

1. Trace: verify all six size-three endpoint values in the second SVG directly from the distance matrix.
2. Dominance: prove formally that an expensive prefix can be discarded when its subset and endpoint match a cheaper prefix.
3. Bitmasks: list every valid state for mask 1101 and explain why endpoints $1$ and $0$ are not both ordinary choices.
4. Asymmetry: change $d(1,3)$ without changing $d(3,1)$ and recompute the optimal directed tour.
5. Path variant: modify the Python function to accept specified start and end cities without closing the cycle.
6. Verification: compare the returned cost with brute-force enumeration for random matrices up to $n=9$.

History and Takeaway

Michael Held and Richard Karp published their dynamic-programming treatment of sequencing problems in 1962. Richard Bellman published an independent dynamic-programming treatment of TSP in the same year, which is why the method is also called Bellman–Held–Karp.