Held–Karp algorithm¶

An exact dynamic-programming algorithm for the traveling-salesman problem that stores the cheapest start-to-end path through each subset of cities, reducing tour enumeration to exponential subset recurrence.

Version: v2 · 2026-09-19 · History
Domain-specific #: 4850
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Algorithms, Exact Traveling Salesman Methods → Computer Science & Software Engineering
Aliases: Bellman–Held–Karp algorithm, Bellman-Held-Karp algorithm

Core Idea¶

The Bellman–Held–Karp algorithm solves TSP exactly by computing the minimum cost of a path from a fixed start through every vertex in a subset and ending at a specified vertex, then closing the best full path into a tour. Optimal substructure lets a state for subset S and endpoint j minimize over predecessor k in S; subset-size order ensures predecessor states exist, and a final edge to the start closes the cycle. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Best-Trip Note Building

Suppose you must visit every friend's house once and come back home by the shortest trip. Instead of trying every possible order, you write notes: 'the shortest way to visit these houses and stop at this one.' You build bigger notes from smaller notes. At the end, you add the walk home and pick the best.

The Shortest Round-Trip Table

The traveling salesman problem asks for the shortest route that visits every city once and returns to the start. Trying every possible order takes far too long when there are many cities. The Held–Karp algorithm instead keeps a table: for each set of visited cities and each possible last city, it stores the shortest path. To fill in one entry, it checks every choice of the city visited just before the last one, using answers it already worked out for smaller sets. When all cities are included, it adds the trip back home and picks the best. It always finds the true shortest route, much faster than checking every order, though it still gets slow quickly as cities are added.

Subset Dynamic Programming for TSP

The Held–Karp algorithm solves the traveling salesman problem exactly using dynamic programming. Each state is a pair (S, j): S is a set of cities already visited, and j is the city where the path currently ends. It stores the minimum cost of a path that starts at a fixed city, visits exactly the cities in S, and ends at j. To compute it, the algorithm tries every possible previous city k in S and takes the best. States are computed in order of increasing set size, so every needed smaller state is already known. Finally, it adds the edge back to the start and chooses the cheapest complete tour. This takes about n²·2ⁿ steps, which is still exponential but far faster than checking all n! orderings.

The Bellman–Held–Karp algorithm is an exact dynamic-programming algorithm for the traveling salesman problem. It relies on optimal substructure. Define C(S, j) as the minimum cost of a path from a fixed start vertex that visits exactly the vertices of S and ends at j, where j is in S. The recurrence is C(S, j) = min over k in S∖{j} of C(S∖{j}, k) + d(k, j). Processing subsets in increasing size guarantees that the needed predecessor states already exist. The answer is the minimum over j of C(V∖{start}, j) + d(j, start), which closes a Hamiltonian cycle. There are O(n·2ⁿ) states, each requiring O(n) work, for O(n²2ⁿ) time instead of O(n!) enumeration. The method is correct only if each state records exactly one subset and one endpoint and the recurrence considers every possible predecessor.

Scope of Application¶

Held–Karp algorithm belongs to algorithms and is useful where the analyst can specify a weighted complete directed or undirected graph, a designated start vertex, subsets of remaining vertices, endpoint-indexed path costs, recurrence states and tour reconstruction, then evaluate each dynamic-program state records exactly one visited subset and terminal vertex, the recurrence considers every possible predecessor, and the final minimization closes a Hamiltonian tour. The scope is broad within that domain but bounded by the need for each dynamic-program state records exactly one visited subset and terminal vertex, the recurrence considers every possible predecessor, and the final minimization closes a Hamiltonian tour. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making each dynamic-program state records exactly one visited subset and terminal vertex, the recurrence considers every possible predecessor, and the final minimization closes a Hamiltonian tour the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Held–Karp algorithm can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Held–Karp algorithm. Held–Karp algorithm compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: a weighted complete directed or undirected graph, a designated start vertex, subsets of remaining vertices, endpoint-indexed path costs, recurrence states and tour reconstruction. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express each dynamic-program state records exactly one visited subset and terminal vertex, the recurrence considers every possible predecessor, and the final minimization closes a Hamiltonian tour independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of algorithms because they reuse a weighted complete directed or undirected graph, a designated start vertex, subsets of remaining vertices, endpoint-indexed path costs, recurrence states and tour reconstruction, Optimal substructure lets a state for subset S and endpoint j minimize over predecessor k in S; subset-size order ensures predecessor states exist, and a final edge to the start closes the cycle., and type the carrier, state every parameter and convention in the definition, test that each dynamic-program state records exactly one visited subset and terminal vertex, the recurrence considers every possible predecessor, and the final minimization closes a Hamiltonian tour, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Held–Karp algorithm Domain-specific

Parents (1) — outgoing typed relations

Held–Karp algorithm is a kind of Algorithm Prime

The method is a finite exact algorithm organized by dynamic-programming states.

Hierarchy path (1) — routes to 1 parentless root

Held–Karp algorithm → is a kind of Algorithm → presupposes, conditional Function (Mapping)

Neighborhood in Abstraction Space¶

Held–Karp algorithm sits in a crowded region of the domain-specific corpus (29^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Combinatorial Optimization on Graphs (16 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25