Held–Karp algorithm

Algorithm description and motivation

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

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

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

More generally, suppose $S = {s_{1}, \dots, s_{k}}$ is a set of $k$ cities. For every integer $1 \leq i \leq k$ , write $S_{i} = S ∖ {s_{i}} = {s_{1}, \dots, s_{i - 1}, s_{i + 1}, \dots, s_{k}}$ for the set created by removing $s_{i}$ from $S$ . Then if the shortest path from $1$ through $S$ to $e$ has $s_{i}$ as its second-to-last city, then removing the final edge from this path must give the shortest path from $1$ to $s_{i}$ through $S_{i}$ . This means there are only $k$ possible shortest paths from $1$ to $e$ through $S$ , one for each possible second-to-last city $s_{i}$ with length $g (S_{i}, s_{i}) + d (s_{i}, e)$ , and $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 $g ({2, \dots, i - 1, i + 1, \dots, n}, i)$ is known for every integer $2 \leq i \leq n$ , giving the shortest distance from city $1$ to city $i$ that passes through every other city. The much shorter second stage adds these distances to the edge lengths $d (i, 1)$ to give $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 $g (S, e)$ the label of the second-to-last city on the path from $1$ to $e$ through $S$ , raising space requirements by only a constant factor.

2 more chapters are free with a Lably account.

Algorithmic complexity

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

Time

Computing one value of $g (S, e)$ for a $k$ -element subset $S$ of ${2, \dots, n}$ requires finding the shortest of $k$ possible paths, each found by adding a known value of $g$ and an edge length from the original graph; that is, it requires time proportional to $k$ . There are $(\binom{n - 1}{k})$ $k$ -element subsets of ${2, \dots, n}$ ; and each subset gives $n - k - 1$ possible values of $e$ . Computing all values of $g (S, e)$ where $| S | = k$ thus requires time $k (n - k - 1) (\binom{n - 1}{k}) = (n - 1) (n - 2) (\binom{n - 3}{k - 1})$ , for a total time across all subset sizes $(n - 1) (n - 2) \sum_{k = 1}^{n - 2} (\binom{n - 3}{k - 1}) = (n - 1) (n - 2) 2^{n - 3} = Θ (n^{2} 2^{n})$ . The second stage of the algorithm, finding a complete cycle from $n - 1$ candidates, takes $Θ (n)$ time and does not affect asymptotic performance.

For undirected graphs, the algorithm can be stopped early after the $k = ⌊ \frac{n - 1}{2} ⌋$ step, and finding the minimum $g (S, e) + g (S^{c} ∖ {1, e}, e)$ for every ${(S, e) : | S | = ⌊ \frac{n - 1}{2} ⌋, e \in S^{c} ∖ {1}}$ , where $S^{c}$ is the complement set of $S$ . This is analogous to a bidirectional search starting at $1$ and meeting at midpoint $e$ . However, this is a constant factor improvement and does not affect asymptotic performance.

Space

Storing all values of $g (S, e)$ for subsets of size $k$ requires keeping $(n - k - 1) (\binom{n - 1}{k}) = (n - 1) (\binom{n - 2}{k})$ values. A complete table of values of $g (S, e)$ thus requires space $\sum_{k = 0}^{n - 2} (n - 1) (\binom{n - 2}{k}) = (n - 1) 2^{n} = Θ (n 2^{n})$ . This assumes that $n$ is sufficiently small enough such that $S$ can be stored as a bitmask of constant multiple of machine words, rather than an explicit k-tuple.

If only the length of the shortest cycle is needed, not the cycle itself, then space complexity can be improved somewhat by noting that calculating $g (S, e)$ for a $S$ of size $k$ requires only values of $g$ for subsets of size $k - 1$ . Keeping only the $(n - 1) [(\binom{n - 2}{k - 1}) + (\binom{n - 2}{k})]$ values of $g (S, e)$ where $S$ has size either $k - 1$ or $k$ reduces the algorithm's maximum space requirements, attained when $k = ⌊ \frac{n}{2} ⌋$ , to $Θ (\sqrt{n} 2^{n})$ .

Pseudocode

Source:

<b id="mwrA">function</b> algorithm TSP (G, n) <b id="mwrQ">is</b> <b id="mwrg">for</b> k := 2 to n <b id="mwrw">do</b> g({k}, k) := d(1, k) <b id="mwsA">end for</b> <b id="mwsQ">for</b> s := 2 <b id="mwsg">to</b> n−1 <b id="mwsw">do</b> <b id="mwtA">for all</b> S ⊆ {2, ..., n}, |S| = s <b id="mwtQ">do</b> <b id="mwtg">for all</b> k ∈ S <b id="mwtw">do</b> g(S, k) := min<sub id="mwuA">m≠k,m∈S</sub> [g(S\{k}, m) + d(m, k)] <b id="mwuQ">end for</b> <b id="mwug">end for</b> <b id="mwuw">end for</b> opt := min<sub id="mwvA">k≠1</sub> [g({2, 3, ..., n}, k) + d(k, 1)] <b id="mwvQ">return</b> (opt) <b id="mwvg">end function</b>

Algorithm description and motivation

Algorithmic complexity

Time

Space

Pseudocode

More in Discrete mathematics