Time complexity of Held-Karp algorithm for TSP

Question

When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp¹, I came up with the following question: why the complexity of their algorithm for TSP is $(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1)$ (p. 199), I mean where do they take the factor $k$? If I understood correctly $k-1$ means the number of additions for each subset of cities. Then why each addition operation is coupled with unknown to me $k$ operations? I suppose it is connected somehow to taking minimum, but computing minimum doesn't seem to require such many operations.

Dynamic programming algorithm by Held and Karp and independently Bellman runs as follows: for each pair $(S,c_i)$, meaning a path going through $c_1$, all the elements of $S$ and terminating at $c_i$ compute

$OPT[S,c_i]=min\{OPT[S\setminus\{c_i\},c_j]+d(c_j,c_i):c_j\in S\setminus\{c_i\}\},$

where $d(c_j,c_i)$ means the distance between cities $c_j$ and $c_i$. Then in the formula from the paper $k$ means the size of $S$.

¹Held, Michael; Karp, Richard M., A dynamic programming approach to sequencing problems, J. Soc. Ind. Appl. Math. 10, 196-210 (1962). DOI: 10.1137/0110015, JSTOR. ZBL0106.14103, MR139493.

Answer 1

Addendum to below, clarifying the $k(k-1)$ terms:

So, if you examine the terms in the expression, you can envision (as analogy) the $n-1 \choose k$ term is an enumeration of all binary strings containing $k$ 1's that have a 1 in the first position. In other words, we let each position in the binary string represent the choice of whether a given one of the $n$ cities in the problem are in the exact subset we are considering at the time. So, for 5 cities, 10101 corresponds to the subset {1,3,5}.

Thus, to compute across all subsets of {1,...,$n$}, we simply count through each binary subset (i.e. count through binary strings) of size=2 (i.e. binary strings of size $n$ that contain two 1's), then size=3, then size=4, ...then size=n. (Note that the size=1 subset must contain only the first city, and thus it's irrelevant to compute its partial distance, since the distance from 1 -> all other cities in the subset -> 1 is exactly 0.)

At each subset with $k$ cities, we have to consider up to $k-1$ candidate-optimal, partial paths. Specifically, the optimal, total path could conceivably traverse through the given subset and end up on any of the $k-1$ cities, excluding the first city. Then, for each such candidate sub-path, we compute the optimal tour up to that point as the minimum of any of the previous, size=$k-1$ sub-paths plus the distance from the terminal city for that sub-path to the terminal city for the current candidate sub-path. This gives $(k-1)(k-2)$ such comparisons that we must make. The discrepancy between my $(k-1)(k-2)$ term, and the $k(k-1)$ term in the analysis linked is a notational difference (I would sum over a different range, given my definition of $k$ than they did). At the very least, however, it should illustrate the quadratic-order complexity of that term.

---

How interesting -- I just finished coding this exact algorithm up in C++ a few minutes ago. (So forgive the tangent from pure theory into a little practical discussion. :))

It costs $O(2^n n^2)$ time and $O(2^n n)$ space -- at least under my implementation. Practically speaking though, when your space requirements grow that fast, they become way more painful than the time requirements. For instance, on my PC (with 4 GB of RAM), I can solve instances with up to 24 cities -- any more than that, and I run out of memory.

Of course, I could just be a bad programmer, and you might be able to do better than me in practice. :)

Edit: A little more specifics on one detail of your question: The $k(k-1)$ term comes from the fact that you have to, in the worst case, calculate the partial, optimal distance from the previous subsets (there are at most $n$ of them; note that $k$ is summed over $n$ in the analysis you linked) to the current one. This requires, again in the worst case, $O(k)$ comparisons with subsets of size $k-1$ for a total of $O(k^2)$.

Also, if my explanation wasn't clear enough, here are some nice lecture notes of Vazirani's (PDF). Scroll down to P. 188 for a discussion of TSP, including an analysis of Held-Karp.

Answer 2

Main note

It's important to note that we compute and store not
"distance of optimal path for combination of k cities"
but
"distance of optimal path for combination of k cities AND for end-point city from this combination".
Understanding it will help with meaning of first two multipliers in following formula.

First phase

The number of operations in the first phase is: $$ \displaystyle \sum_{k>=2} \underbrace{ \binom{n-1}{k-1} }_{\substack{ \text{choose city combination} \\ \text{of size = $k-1$}}} \cdot \underbrace{ (k-1) }_{\substack{ \text{choose city to be the last} \\ \text{from $k-1$ cities} \\ \text{in chosen combination} } } \cdot \underbrace{ ((n-1)-(k-1)) }_{ \substack{ \text{choose city} \\ \text{that is not in chosen combination} \\ \text{to add to path} } } $$

Missing superscript in sum means for all k>=2 that is valid for binomial coefficient. So the last valid not null term of sum will be for $k=n-1$ $$ \binom{n-1}{n-2} \cdot (n-2) \cdot 1 $$ It means that our sum doesn`t capture last choices of city to connect to the first city. There are $n-1$ cities to connect to the first city. So finally we will add this term to the sum.

Let transform formula to form that you provide that is also on Held-Karp Wikipedia page.

$$ \displaystyle \sum_{k>=2} \binom{n-1}{k-1} \cdot (k-1) \cdot ((n-1)-(k-1))= \sum_{k>=2} \frac{(n-1)!}{(k-1)!(n-k)!} \cdot (k-1) \cdot (n-k)= \sum_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1)= \sum_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1) $$ Manipulating binomial coefficients leads to: $$ \displaystyle \sum_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1) = \sum_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1) = \sum_{k>=2} \frac{(n-3)!}{(k-2)!(n-3-(k-2))!} \cdot (n-1) \cdot (n-2)= (n-1) \cdot (n-2)\sum_{k>=2} \binom{n-3}{k-2}=(n-1) \cdot (n-2) \cdot 2^{n-3} $$ So the number of operations in the first phase is $(n-1) \cdot (n-2) \cdot 2^{n-3}+(n-1)$

Second phase

Second phase is restoring optimal path by marks we have made in the first phase simultaneously with computing distances.

For each optimal path "for combination of k cities AND for end-point city from this combination" we have saved the second-to-last city.

To backtrack optimal path we need to ask some data structure to return the second-to-last city "for combination of k cities AND for end-point city from this combination". So this data structure must be something like
Map<combination of k cities, Map<last city, second-to-last city>>. As index of combination of k cities we can use, for example, binary_string[city id]=1 if city id is in combination . So we need to look at all elements of combination of k cities to identify combination and index our data structure. This gives us the number of operations for the second phase: $$ \displaystyle \sum_{k>=2}^{n-1} k = \frac{(n)(n-1)}{2} - 1 $$