The Held–Karp algorithm, also called the Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman^[1] and by Held and Karp^[2] to solve the traveling salesman problem (TSP), in which the input is a distance matrix between a set of cities, and the goal is to find a minimum-length tour that visits each city exactly once before returning to the starting point. It finds the exact solution to this problem, and to several related problems including the Hamiltonian cycle problem, in exponential time.

Algorithm description and motivation

Number the cities ${\displaystyle 1,2,\ldots ,n}$, with ${\displaystyle 1}$ designated arbitrarily as a "starting" city (since the solution to TSP is a cycle, the choice of starting city doesn't matter). The Held–Karp algorithm begins by calculating, for each set of cities ${\displaystyle S\subseteq \{2,\ldots ,n\}}$ and every city ${\displaystyle e\neq 1}$ not contained in ${\displaystyle S}$, the shortest one-way path from ${\displaystyle 1}$ to ${\displaystyle e}$ that passes through every city in ${\displaystyle S}$ in some order (but not through any other cities). Denote this distance ${\displaystyle g(S,e)}$, and write ${\displaystyle d(u,v)}$ for the length of the direct edge from ${\displaystyle u}$ to ${\displaystyle v}$. We'll compute values of ${\displaystyle g(S,e)}$ starting with the smallest sets ${\displaystyle S}$ and finishing with the largest.

When ${\displaystyle S}$ has two or fewer elements, then calculating ${\displaystyle g(S,e)}$ requires looking at one or two possible shortest paths. For example, ${\displaystyle g(\emptyset ,e)}$ is simply ${\displaystyle d(1,e)}$, and ${\displaystyle g(\{2\},3)}$ is just the length of ${\displaystyle 1\rightarrow 2\rightarrow 3}$. Likewise, ${\displaystyle g(\{2,3\},4)}$ is the length of either ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4}$ or ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}$, whichever is shorter.

Once ${\displaystyle S}$ contains three or more cities, the number of paths through ${\displaystyle S}$ rises quickly, but only a few such paths need to be examined to find the shortest. For instance, if ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4}$ is shorter than ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}$, then ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5}$ must be shorter than ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}$, and the length of ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}$ is not a possible value of ${\displaystyle g(\{2,3,4\},5)}$. Similarly, if the shortest path from ${\displaystyle 1}$ through ${\displaystyle \{2,3,4\}}$ to ${\displaystyle 5}$ is ${\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5}$, and the shortest path from ${\displaystyle 1}$ through ${\displaystyle \{2,3,4,5\}}$ to ${\displaystyle 6}$ ends with the edge ${\displaystyle 5\rightarrow 6}$, then the whole path from ${\displaystyle 1}$ to ${\displaystyle 6}$ must be ${\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5\rightarrow 6}$, and not any of the other five paths created by visiting ${\displaystyle \{2,3,4\}}$ in a different order.

More generally, suppose ${\displaystyle S=\{s_{1},\ldots ,s_{k}\}}$ is a set of ${\displaystyle k}$ cities. For every integer ${\displaystyle 1\leq i\leq k}$, write ${\displaystyle S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_{k}\}}$ for the set created by removing ${\displaystyle s_{i}}$ from ${\displaystyle S}$. Then if the shortest path from ${\displaystyle 1}$ through ${\displaystyle S}$ to ${\displaystyle e}$ has ${\displaystyle s_{i}}$ as its second-to-last city, then removing the final edge from this path must give the shortest path from ${\displaystyle 1}$ to ${\displaystyle s_{i}}$ through ${\displaystyle S_{i}}$. This means there are only ${\displaystyle k}$ possible shortest paths from ${\displaystyle 1}$ to ${\displaystyle e}$ through ${\displaystyle S}$, one for each possible second-to-last city ${\displaystyle s_{i}}$ with length ${\displaystyle g(S_{i},s_{i})+d(s_{i},e)}$, and ${\displaystyle g(S,e)=\min _{1\leq i\leq k}g(S_{i},s_{i})+d(s_{i},e)}$.

This stage of the algorithm finishes when ${\displaystyle g(\{2,\ldots ,i-1,i+1,\ldots ,n\},i)}$ is known for every integer ${\displaystyle 2\leq i\leq n}$, giving the shortest distance from city ${\displaystyle 1}$ to city ${\displaystyle i}$ that passes through every other city. The much shorter second stage adds these distances to the edge lengths ${\displaystyle d(i,1)}$ to give ${\displaystyle n-1}$ possible shortest cycles, and then finds the shortest.

The shortest path itself (and not just its length), finally, may be reconstructed by storing alongside ${\displaystyle g(S,e)}$ the label of the second-to-last city on the path from ${\displaystyle 1}$ to ${\displaystyle e}$ through ${\displaystyle S}$, raising space requirements by only a constant factor.

Algorithmic complexity

The Held–Karp algorithm has exponential time complexity ${\displaystyle \Theta (2^{n}n^{2})}$, significantly better than the superexponential performance ${\displaystyle \Theta (n!)}$ of a brute-force algorithm. Held–Karp, however, requires ${\displaystyle \Theta (n2^{n})}$ space to hold all computed values of the function ${\displaystyle g(S,e)}$, while brute force needs only ${\displaystyle \Theta (n^{2})}$ space to store the graph itself.

Example^[3]

Distance matrix:

${\displaystyle C={\begin{pmatrix}0&2&9&10\\1&0&6&4\\15&7&0&8\\6&3&12&0\end{pmatrix}}}$

Functions description:

• g(x, S) - starting from 1, path min cost ends at vertex x, passing vertices in set S exactly once
• c_xy - edge cost ends at x from y
• p(x, S) - the second-to-last vertex to x from set S. Used for constructing the TSP path back at the end.

k = 0, null set:

Set ∅:

       g(2, ∅) = c21 = 1 
       g(3, ∅) = c31 = 15
       g(4, ∅) = c41 = 6

k = 1, consider sets of 1 element:

Set {2}:

       g(3,{2}) = c32 + g(2, ∅ ) = c32 + c21 = 7 + 1 = 8       p(3,{2}) = 2
       g(4,{2}) = c42 + g(2, ∅ ) = c42 + c21 = 3 + 1 = 4       p(4,{2}) = 2

Set {3}:

       g(2,{3}) = c23 + g(3, ∅ ) = c23 + c31 = 6 + 15 = 21     p(2,{3}) = 3
       g(4,{3}) = c43 + g(3, ∅ ) = c43 + c31 = 12 + 15 = 27    p(4,{3}) = 3

Set {4}:

       g(2,{4}) = c24 + g(4, ∅ ) = c24 + c41 = 4 + 6 = 10      p(2,{4}) = 4
       g(3,{4}) = c34 + g(4, ∅ ) = c34 + c41 = 8 + 6 = 14      p(3,{4}) = 4

k = 2, consider sets of 2 elements:

Set {2,3}:

         g(4,{2,3}) = min {c42 + g(2,{3}), c43 + g(3,{2})} = min {3+21, 12+8}= min {24, 20}= 20
         p(4,{2,3}) = 3

Set {2,4}:

         g(3,{2,4}) = min {c32 + g(2,{4}), c34 + g(4,{2})} = min {7+10, 8+4}= min {17, 12} = 12
         p(3,{2,4}) = 4

Set {3,4}:

          g(2,{3,4}) = min {c23 + g(3,{4}), c24 + g(4,{3})} = min {6+14, 4+27}= min {20, 31}= 20
          p(2,{3,4}) = 3

Length of an optimal tour:

 f = g(1,{2,3,4}) = min { c12 + g(2,{3,4}), c13 + g(3,{2,4}), c14 + g(4,{2,3}) }
                  = min {2 + 20, 9 + 12, 10 + 20} = min {22, 21, 30} = 21

Predecessor of node 1: p(1,{2,3,4}) = 3

Predecessor of node 3: p(3, {2,4}) = 4

Predecessor of node 4: p(4, {2}) = 2

Predecessor of node 2: p(2, {}) = 1

Hence, an optimal TSP tour is given by 1 → 2→ 4 → 3→ 1.

Pseudocode^[4]

function algorithm TSP (G, n) is
    for k := 2 to n do
        g({k}, k) := d(1, k)
    end for

    for s := 2 to n−1 do
        for all S ⊆ {2, ..., n}, |S| = s do
            for all k ∈ S do
                g(S, k) := minm≠k,m∈S [g(S\{k}, m) + d(m, k)]
            end for
        end for
    end for

    opt := mink≠1 [g({2, 3, ..., n}, k) + d(k, 1)]
    return (opt)
end function

Related algorithms

References