18.1. Travelling Salesman Problem

A Hamiltonian cycle in an graph \(G = (V, E)\) is a simple cycle that visits all vertices of \(G\).

If \(G\) is complete, a Hamiltonian cycle always exists. Otherwise, it may not exist. Even deciding whether a graph has a Hamiltonian cycle is NP-hard.

Travelling Salesman Problem (TSP): Given a complete graph \(G = (V, E)\) and a weight function \(w : E \rightarrow \mathbb{R}\), find a Hamiltonian cycle \(C\), called a travelling salement tour or simply tour, in \(G\) of minimum weight \(w(C) = \sum_{e \in C} w_e\), which we call the length of the tour.

By the following two exercises, the assumption that \(G\) is complete does not make the problem any easier:

Exercise 18.1: Given a graph \(G = (V, E)\) and an algorithm \(\mathcal{A}\) for the TSP, show how to use \(\mathcal{A}\) to decide whether \(G\) has a Hamiltonian cycle and, if so, find one.

Exercise 18.2: Given a graph \(G = (V, E)\), a weight function \(w : E \rightarrow \mathbb{R}\), and an algorithm \(\mathcal{A}\) that can solve the TSP on complete graphs, show how to use \(\mathcal{A}\) to solve the TSP on \(G\).

A Naïve Algorithm

A naïve algorithm for this problem takes \(O(n!)\) time. Let the vertices in \(G\) be numbered \(v_1, \ldots, v_n\). We can consider any tour of \(G\) to start at \(v_1\). The tour is then fully defined by specifying the order in which the remaining \(n-1\) vertices \(v_2, \ldots, v_n\) are visited after \(v_1\); after visiting the last vertex, the tour returns to \(v_1\). Thus, there are \((n-1)!\) tours to consider. For each tour, it takes \(O(n)\) time to calculate its length. Thus, inspecting all tours and reporting the shortest one found takes \(O(n \cdot (n-1)!) = O(n!)\) time.

A Faster Algorithm Using Dynamic Programming

To obtain a better algorithm based on dynamic programming, we need to develop a recurrrence describing an optimal solution. For any permutation \(\pi\) of the vertices in \(G\) and any index \(1 \le i \le n\), let \(V_{\pi,i} = \{v_{\pi(1)}, \ldots, v_{\pi(i)}\}\). For any subset \(S \subseteq V\), an \(\boldsymbol{S}\)-path is a path in \(G\) that visits all vertices in \(S\) and no other vertices.

Now let \(\pi\) be a permutation such that \(\pi(1) = 1\) and \(\langle v_{\pi(1)}, \ldots, v_{\pi(n)} \rangle\) is a shortest travelling salesman tour of \(G\). Then \(\langle v_{\pi(1)}, \ldots, v_{\pi(i)} \rangle\) is a shortest \(V_{\pi,i}\)-path from \(v_{\pi(1)}\) to \(v_{\pi(i)}\). Of course, we know neither the first \(i\) vertices \(v_{\pi(1)}, \ldots, v_{\pi(i)}\) visited by the optimal tour nor the last vertex \(v_{\pi(i)}\) among them. Thus, we consider all subproblems of this type: For every subset \(S \subseteq V\) such that \(v_1 \in S\) and every vertex \(v \in S\), let \(T(S,v)\) be the length of the shortest \(S\)-path from \(v_1\) to \(v\). Then the length of an optimal travelling salesman tour of \(G\) is

\[\min_{2 \le i \le n} (T(V, v_i) + w(v_i,v_1))\]

because the tour can be decomposed into a shortest \(V\)-path from \(v_1\) to the last vertex \(v_i\) visited before returning to \(v_1\) plus the edge \((v_i, v_1)\). This length can clearly be computed in linear time after computing \(T(V, v_i)\) for all \(2 \le i \le n\). These values \(T(V, v_i)\) can be defined by the recurrence:

\[\begin{aligned} T(\{v_1\}, v_1) &= 0\\ T(S, v_1) &= \infty && \forall |S| > 1\\ T(S, v) &= \min_{u \in S \setminus {v}} (T(S \setminus \{v\}, u) + w(u,v)) && \forall |S| > 1, v \ne v_1 \end{aligned}\]

Indeed, the only \({v_1}\)-path is the one-vertex path \(\langle v_1 \rangle\) of length \(0\). For \(|S| > 1\), there is no open \(S\)-path from \(v_1\) to \(v_1\). Thus, \(T(S, v_1) = \infty\). For any other vertex \(v \in S\), let \(P\) be the shortest \(S\)-path from \(v_1\) to \(v\) and let \(u\) be \(v\)'s predecessor in \(P\). The subpath of \(P\) from \(v_1\) to \(u\) must be a shortest \((S \setminus \{v\})\)-path from \(v_1\) to \(u\). It is clearly an \((S \setminus \{v\})\)-path from \(v_1\) to \(u\) and, if there was a shorter such path \(P'\), we could obtain a shorter \(S\)-path from \(v_1\) to \(v\) than \(P\) by appending \(v\) to \(P'\). Thus, the subpath of \(P\) from \(v_1\) to \(u\) has length \(T(S \setminus \{v\}, u)\). Since we do not know which vertex in \(S \setminus \{v\}\) is \(v\)'s predecessor in \(P\), we consider every vertex in \(S \setminus \{v\}\) as a potential predecessor and choose the one that gives the shortest \(S\)-path from \(v_1\) to \(v\).

We can use dynamic programming to compute all these values \(T(S,v)\): We construct a table \(T\) indexed by the subsets \(S \subseteq V\) and vertices \(v \in S\). Given the values \(T(S \setminus \{v\}, u)\) for all \(v \in S\) and \(u \in S \setminus \{v\}\), we can compute \(T(S,v)\) in \(O(|S| - 1)\) time. If we fill in the table by increasing size of the subset \(S\), then the values \(T(S \setminus \{v\}, u)\) needed to compute \(T(S,v)\) are computed before \(T(S,v)\). The number of table entries to be computed is \(\sum_{i=1}^n \binom{n}{i} i\). Since each such entry can be computed in \(O(i - 1)\) time, the total cost of the algorithm is

\[O\left(\sum_{i=1}^n \binom{n}{i} i^2\right) = O\left(\sum_{i=1}^n \binom{n}{i} n^2\right) = O(2^n \cdot n^2).\]

This proves the following theorem:

Theorem 18.1: The travelling salesman problem in an arbitrary edge-weighted graph \(G\) can be solved in \(O^*(2^n)\) time.

The key idea that led to an improvement of the running time from \(O(n!)\) to \(O\bigl(2^n \cdot n^2\bigr)\) is to switch from considering the different orders in which the vertices in \(G\) are visited by a travelling salesman tour (of which there are \(n!\)) to considering optimal subtours over all subsets of \(V\) (of which there are only \(2^n\)).