The Held-Karp TSP Algorithm

The problem it solves

The Travelling Salesman Problem (TSP) asks: given n cities and the pairwise distances between them, what is the shortest tour that starts at one city, visits every other city exactly once, and returns to the start? It is one of the most famous NP-hard problems in computer science — the decision version is NP-complete, and no polynomial-time exact algorithm is known (or expected, unless P = NP).

The naive exact approach fixes a starting city and tries every ordering of the remaining n−1 cities. That is (n−1)! permutations, or (n−1)!/2 if you dedupe mirror-image tours in a symmetric instance. Factorial growth is brutal: at just 15 cities that is already over 43 billion tours. Held-Karp is the classic way to trade that factorial for a merely exponential 2ⁿ — the same asymptotic idea that turns a naive exponential recursion into a polynomial table in dozens of other dynamic-programming problems, applied to a problem where the honest answer is still exponential but far better than factorial.

The key insight: subsets, not permutations

Brute force wastes enormous effort. Consider two different tours that both begin 0 → 3 → 7 → 2 and then diverge. The cost of getting from the origin to city 2 having visited {3, 7} along the way is identical in both, yet brute force recomputes it every single time it appears inside a full permutation.

Held-Karp's insight is that the future of a partial tour depends only on two things — which cities have already been visited and which city you are currently standing in — not on the exact order you visited them in. So we collapse "the order so far" into a set. That set is stored as a bitmask: an n-bit integer where bit i is 1 iff city i is in the set. This is the optimal-substructure property that makes dynamic programming apply.

How Held-Karp works, step by step

Fix city 0 as the origin. Define the DP state:

• dp[S][j] — the minimum cost of a path that starts at city 0, visits exactly the cities in bitmask S, and ends at city j. Here j must be a member of S, and by convention bit 0 (the origin) is set in every S.

Base case. The path that has visited only the origin and ends there costs nothing: dp[{0}][0] = 0.

Transition (relaxation). To reach city j having visited set S, you must have arrived from some predecessor city k that was the previous endpoint of the path over the smaller set S \ {j}:

dp[S][j] = min over k ∈ S, k ≠ j, k ≠ 0 (or k = 0 only when S = {0, j}) of   dp[S \ {j}][k] + dist[k][j]

Order of evaluation. A state over set S depends only on states over the strictly smaller set S \ {j}. Since removing a bit always yields a smaller integer, iterating masks S in increasing numeric order guarantees every dependency is already computed — the same topological ordering trick used throughout subset DP.

Closing the tour. The states above compute open paths. To close the cycle, add the return edge back to the origin and take the best endpoint:

answer = min over j ≠ 0 of   dp[FULL][j] + dist[j][0]

where FULL = (1 << n) − 1 is the mask with every city visited.

Why the complexity is O(2ⁿ·n²)

Count the work directly:

• There are 2ⁿ possible subsets S.
• For each subset, there are up to n choices of endpoint j.
• So there are 2ⁿ·n DP states — this is also the space, O(2ⁿ·n).
• Filling one state means minimizing over up to n predecessors k, an extra factor of n.

Multiply: 2ⁿ·n·n = O(2ⁿ·n²) time. The 2ⁿ term dominates everything; the n² is polynomial noise beside it. This is a genuine exponential-to-exponential improvement over factorial, not a fix for NP-hardness — Held-Karp is still exponential, and no one has found an exact TSP algorithm that beats the 2ⁿ base (up to polynomial factors) in over sixty years.

Held-Karp vs other TSP approaches

	Brute force	Held-Karp	Christofides	Branch-and-cut (Concorde)
Result	Exact optimum	Exact optimum	≤ 1.5× optimum (metric)	Exact optimum
Time	O(n!)	O(2ⁿ·n²)	O(n³)	Exponential worst case
Space	O(n)	O(2ⁿ·n)	O(n²)	Varies (LP + cuts)
Needs triangle inequality?	No	No	Yes (metric TSP)	No
Handles asymmetric distances?	Yes	Yes	No	Yes (ATSP variants)
Practical size	~11 cities	~18–20 cities	Thousands+	Tens of thousands+
Best for	Never (teaching only)	Small exact instances	Fast metric approximation	Large exact instances

Implementation in Python

from math import inf

def held_karp(dist):
    """Exact TSP tour cost + order via bitmask DP. dist is an n x n matrix.
       Returns (cost, tour) with the tour starting and ending at city 0."""
    n = len(dist)
    FULL = (1 << n) - 1

    # dp[mask][j] = min cost path from 0, visiting exactly `mask`, ending at j.
    # parent[mask][j] = predecessor k that achieved the minimum (for reconstruction).
    dp = [[inf] * n for _ in range(1 << n)]
    parent = [[-1] * n for _ in range(1 << n)]
    dp[1][0] = 0  # base case: only city 0 visited, standing at 0

    for mask in range(1 << n):
        if not (mask & 1):            # every subset must include the origin
            continue
        for j in range(n):
            if dp[mask][j] == inf:    # unreachable state — skip
                continue
            for k in range(n):        # try to extend the path to a new city k
                if mask & (1 << k):    # k already visited
                    continue
                nxt = mask | (1 << k)
                cand = dp[mask][j] + dist[j][k]
                if cand < dp[nxt][k]:
                    dp[nxt][k] = cand
                    parent[nxt][k] = j

    # Close the tour: return to city 0 from the best final endpoint.
    best, last = inf, -1
    for j in range(1, n):
        cand = dp[FULL][j] + dist[j][0]
        if cand < best:
            best, last = cand, j

    # Reconstruct the order by walking parent pointers backward.
    tour, mask, j = [], FULL, last
    while j != -1:
        tour.append(j)
        pj = parent[mask][j]
        mask ^= (1 << j)   # remove j from the set
        j = pj
    tour.reverse()          # now starts at 0
    tour.append(0)          # close the cycle back to origin
    return best, tour

Note the "forward push" style used here: instead of pulling from predecessors, each reachable state dp[mask][j] relaxes every unvisited city k and updates dp[mask | (1<<k)][k]. It computes exactly the same table as the pull recurrence and is often easier to write correctly. The parent array is the only addition needed to recover the tour itself rather than just its length.

Common misconceptions and pitfalls

• "Held-Karp makes TSP polynomial." It does not. TSP is NP-hard; Held-Karp is still exponential (2ⁿ). It only beats the factorial naive method. If anything advertised solves TSP in polynomial time, be very skeptical.
• Memory, not time, is the real wall. The 2ⁿ·n table is what kills you first. At n = 25 the table has 2²⁵·25 ≈ 840 million cells; even one byte each would be near a gigabyte, and you need more than a byte per cost. This is why the practical ceiling is ~20 cities, not because the CPU is too slow.
• Forgetting to pin the origin into every mask. If you don't guarantee bit 0 is set (or don't skip masks lacking it), you waste half the table and can produce paths that never start at the origin. The if not (mask & 1): continue guard handles this.
• Confusing "path" states with "tour" cost. The DP table stores open paths. You must add the closing edge dist[j][0] at the end. Reporting min dp[FULL][j] without the return edge gives the shortest Hamiltonian path, not the shortest tour.
• Assuming symmetry. Held-Karp works fine on asymmetric matrices (dist[a][b] ≠ dist[b][a]). Don't "optimize" by halving the state space assuming mirror tours are equal — that only holds for symmetric TSP.

A little history

In 1962 Michael Held and Richard M. Karp published "A Dynamic Programming Approach to Sequencing Problems" in the Journal of the Society for Industrial and Applied Mathematics, framing TSP as a sequencing problem solvable by dynamic programming over subsets. That same year, Richard Bellman — the father of dynamic programming itself — described the identical recurrence independently, which is why some texts call it the Bellman–Held–Karp algorithm. Richard Karp would later go on to define the class of 21 NP-complete problems (1972), of which TSP's decision variant is a canonical member. More than sixty years on, Held-Karp is still the textbook exact TSP algorithm and still holds the best-known worst-case exponential bound of 2ⁿ up to polynomial factors — a striking testament to how hard genuine improvement over it has proven to be.