Wait, What?
An exponential algorithm can still be a major improvement when it replaces n! possible tours with roughly n²2ⁿ structured subproblems.
The Held–Karp dynamic-programming algorithm is one of the classic exact methods for the travelling salesperson problem (TSP). Brute-force enumeration considers every possible visit order. Held–Karp notices that many tours share the same partial situation: which cities have already been visited, and which city are we currently at? Once that state is defined correctly, dynamic programming can reuse the best answer for the same subset-and-endpoint combination.
For learners, Held–Karp is a superb transition from polynomial-time classroom dynamic programming to exponential-time exact algorithms. It teaches state design, bitmask representation, recurrence proofs, memory compression, path reconstruction and the practical meaning of exponential complexity.
Quick Answer
Learn Held–Karp in this order: TSP contract → factorial brute force → fix one start city → subset-and-last-city state → base cases → recurrence → subset iteration order → bitmask implementation → close the tour → reconstruct the route → O(n²2ⁿ) time → O(n2ⁿ) memory → exact-versus-approximate algorithm choice. The essential idea is the state, not the bit tricks.
1. State the TSP Precisely
Given n cities and a cost d(i,j) for travelling from city i to city j, find a minimum-cost tour that:
- starts at a chosen city;
- visits every city exactly once;
- returns to the start.
In a symmetric TSP, d(i,j)=d(j,i). In an asymmetric TSP, direction matters. Held–Karp dynamic programming can be formulated for either, as long as the cost matrix and transition rule match the problem.
2. Why Brute Force Becomes Impossible Quickly
If one start city is fixed, a naive exact search may examine permutations of the remaining n−1 cities—on the order of (n−1)! candidate tours.
Dynamic programming does not make TSP polynomial. Instead, it collapses many permutations into shared subproblems. That is why the algorithm is a major improvement while still remaining exponential.
3. Fix a Start City to Remove Rotational Duplication
Choose city 0 as the start. Every tour is treated as beginning and ending there. This removes equivalent rotations of the same cycle and makes the dynamic-programming state cleaner.
The remaining cities are usually indexed 1 through n−1.
4. The State: Visited Set Plus Current Endpoint
Define:
DP[S][j] = minimum cost to start at 0,
visit exactly the cities in S,
and finish at city jHere S is a subset that includes j but excludes the fixed start city 0.
This is the central compression step. Two different partial tours that have visited the same set S and end at the same city j have the same future possibilities. Only the cheaper one needs to survive.
5. Base Cases
For a subset containing only city j:
DP[{j}][j] = d(0,j)The cheapest way to start at 0, visit only j and finish at j is simply the direct edge from 0 to j.
6. The Recurrence
Suppose |S|>1 and j∈S. The tour segment reaching j must have come from some previous city k∈S\{j}. Therefore:
DP[S][j] = min over k in S\{j}
( DP[S\{j}][k] + d(k,j) )This recurrence asks a precise question: if j is the final city of this partial path, which previous endpoint k gives the cheapest way to reach it after visiting all other cities in S?
7. Close the Tour at the End
Let A be the set of all non-start cities. Once every city has been visited, add the cost of returning from the final city j to 0:
answer = min over j in A
( DP[A][j] + d(j,0) )Do not forget this final edge. DP[A][j] is a Hamiltonian path from the start to j, not yet a completed tour.
8. Why the Recurrence Is Correct
Take an optimal partial route represented by DP[S][j]. Immediately before reaching j, it must be at some k in S\{j}. Everything before that final edge is itself an optimal solution to the smaller state DP[S\{j}][k]. If it were not, replacing it with a cheaper route to that same smaller state would make the supposedly optimal DP[S][j] cheaper—a contradiction.
This is the principle of optimality in concrete form.
9. Bitmasks Encode Subsets Efficiently
For implementation, represent a subset S by an integer bitmask. If bit i is 1, city i is present in the subset.
mask = 0b10110could represent a set containing three selected cities, depending on the indexing convention.
Useful operations include:
contains i: mask & (1 << i)
add i: mask | (1 << i)
remove i: mask ^ (1 << i) # only if i is known present
iterate bits: repeatedly extract set bitsBitmasks make set operations fast, but they should come after the state meaning is understood.
10. Iterate States in Dependency Order
DP[S][j] depends on states with one fewer visited city. Therefore, process subsets by increasing size, or use a mask order that guarantees required smaller states have already been computed.
A simple conceptual order is:
for subset_size = 1 to n-1:
for each subset S of that size:
for each j in S:
compute DP[S][j]An implementation may iterate masks numerically, but dependency correctness must be preserved.
11. Bottom-Up Pseudocode
start = 0
for each city j != start:
DP[{j}][j] = d(start, j)
for size = 2 to n-1:
for each subset S of non-start cities with |S| = size:
for each j in S:
DP[S][j] = infinity
for each k in S, k != j:
DP[S][j] = min(
DP[S][j],
DP[S - {j}][k] + d(k,j)
)
A = all non-start cities
answer = min_j (DP[A][j] + d(j,start))12. Trace Four Cities Before Writing Bitmask Code
Use cities 0,1,2,3. Write all singleton states first:
DP[{1}][1]
DP[{2}][2]
DP[{3}][3]Then size-two states such as DP[{1,2}][2]. For each state, record:
subset S | endpoint j | candidate predecessor k | candidate cost | chosen costOnly after the recurrence feels mechanical should the same table be encoded as integer masks.
13. Complexity: Why It Is O(n²2ⁿ)
There are O(2ⁿ) subsets. For each subset there can be O(n) choices of endpoint j, and each state may inspect O(n) predecessor cities k. This yields:
time = O(n² 2ⁿ)Storing a value for each subset-and-endpoint state uses:
space = O(n 2ⁿ)These are still exponential, but dramatically smaller than factorial enumeration for moderate n.
14. Exponential Does Not Mean “All Exponentials Are the Same”
For n=20, 2ⁿ is about one million. For n=30, it is about one billion. Multiplying by n² and storing tables for each state quickly becomes substantial. A method practical around one problem size may become impossible only a few cities later.
Professional planning should estimate actual states, bytes and operations, not merely label the method “exponential.”
15. Reconstructing the Optimal Tour
If the application needs the route, not only its cost, store the predecessor k that achieved each minimum:
parent[S][j] = best predecessor kAfter choosing the final city, backtrack through parent states while removing the current endpoint from S. Reverse the recovered sequence and add the start city at both ends as required.
This increases memory but turns an objective value into an actionable tour.
16. Memory Can Be Reduced When Only the Cost Is Needed
Each layer of subset size depends only on the previous size. A layered implementation can keep fewer states at once, reducing memory. More advanced layouts index only valid endpoint/subset combinations or use sparse maps when n is small but constraints remove many states.
However, aggressive memory compression can make tour reconstruction harder. Optimise according to the output contract.
17. Bit-Level Engineering Matters
High-performance implementations pay attention to:
- compact contiguous DP arrays;
- fast iteration over set bits;
- cache locality;
- numeric overflow;
- infinity sentinels;
- parallelisation by independent states within a layer;
- precomputed distance matrices.
A mathematically correct recurrence can still run poorly if memory access is chaotic.
18. Know the Name Ambiguity
“Held–Karp” is used for more than one TSP idea. The dynamic-programming algorithm described here is the Bellman–Held–Karp exact subset DP. In optimisation literature, Held–Karp bound can also refer to a strong lower bound based on 1-trees and Lagrangian relaxation.
These are related historically but are not the same algorithmic object. Professional writing should disambiguate them.
19. Held–Karp Is an Exact Solver Component, Not the Whole TSP World
For larger instances, exact TSP solvers use sophisticated branch-and-cut, cutting planes, bounds and heuristics. Approximation algorithms such as Christofides apply to metric TSP under specific assumptions. Heuristics and local search can handle much larger instances without exact guarantees.
Choose Held–Karp when exactness and moderate n make the exponential state space acceptable—not because it is the default solution to every routing problem.
20. Common Failure States
- Defining DP only by subset and forgetting the endpoint.
- Including the fixed start city inconsistently inside masks.
- Using a recurrence whose predecessor state still contains j.
- Forgetting the final return edge to the start.
- Iterating subsets before their smaller dependencies are available.
- Overflowing integer costs or using a dangerous infinity sentinel.
- Storing every predecessor when only the optimal cost is required.
- Calling the method polynomial because it uses dynamic programming.
- Confusing the exact subset DP with the Held–Karp lower bound.
21. Practice Ladder: Beginner to Professional
- Beginner: list all tours for four cities and observe repeated partial paths.
- Foundation: define DP[S][j] in words without code.
- Intermediate: fill the complete DP table for four or five cities by hand.
- Advanced: implement subsets as bitmasks and reconstruct the chosen tour.
- Professional: profile memory, use compact state layouts, compare cost-only and route-reconstruction versions, and determine the largest n your machine can solve under a fixed resource budget.
- Transfer: use the subset-and-endpoint state pattern for Hamiltonian-path, Steiner-style or sequencing problems where future decisions depend on what has been used and where the partial solution ends.
22. A Better Way to Study Held–Karp
Dynamic programming is easier to learn when the recurrence is decomposed into subgoals. For every state, ask: What does the state mean? What smaller state must exist? What is the final decision? What quantity is minimised? Work one complete four-city table before coding. Then convert the same subsets to bitmasks. ACM SIGCSE research has specifically explored worked-example models for teaching dynamic programming, and broader programming-education research supports subgoal-labelled examples for reducing unnecessary cognitive load.
Learning Hall Boundary
This article owns the Bellman–Held–Karp exact subset dynamic-programming algorithm for TSP and related sequencing problems. It does not replace the existing dynamic-programming foundations, Christofides metric-TSP article, branch-and-bound material, general combinatorial optimisation instruction, MindOS learning-process jobs, Bolt measurement work or Student/Studying Interface workflow content.
Evidence Boundary
Michael Held and Richard M. Karp presented their dynamic-programming approach to sequencing problems in the early 1960s; the journal version appears in Journal of the Society for Industrial and Applied Mathematics 10(1), 1962, pp. 196–210, DOI 10.1137/0110015. IBM Research also preserves the original conference-paper record: IBM Research — Held and Karp. The learning design draws on “A Worked Example Model for Teaching Dynamic Programming,” SIGCSE 2023, DOI 10.1145/3545947.3576232, and related programming-education research on subgoal-labelled worked examples.
Professional rule: you understand Held–Karp when you can define the subset-and-endpoint state from first principles, derive the recurrence without memorising it, estimate the actual exponential resource cost for your n, and reconstruct the exact tour from stored decisions.
