HeldKarp

The Held–Karp algorithm is an exact dynamic programming method for the traveling salesman problem (TSP), named after Michael Held and Richard M. Karp, who described it in 1962. It solves the problem of finding a minimum-cost Hamiltonian cycle in a complete weighted graph by systematically exploring subsets of vertices.

The approach fixes a starting vertex, s. Let V' be the set of the remaining vertices. For every subset S of V' and every endpoint j in S, the algorithm computes D[S][j], the minimum cost of a path that starts at s, visits all vertices in S exactly once, and ends at j. The base case is D[{j}][j] = w(s, j). For larger subsets, the recurrence is D[S][j] = min_{i in S\{j}} D[S\{j}][i] + w(i, j). The optimal tour length is min_{j in V'} D[V'][j] + w(j, s); this final value yields the minimum Hamiltonian cycle when the cycle is closed back to the start.

Complexity-wise, the method examines all subsets of V', of which there are 2^{n-1}, and computes values for up to n endpoints with a minimization over up to n predecessors. This yields a time complexity of O(n^2 2^n) and a space requirement of O(n 2^n).

Significance and usage: Held–Karp is one of the earliest exact algorithms for the TSP and established the subset dynamic programming paradigm. It remains a fundamental teaching example for dynamic programming and influence on later exact solvers, though its exponential growth makes it impractical for large instances. The algorithm illustrates how breaking problems into subproblems defined by vertex subsets can yield exact solutions for challenging combinatorial optimization problems.