Cycles · Traveling Salesman Problem

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

We present a \(2\)-approximation algorithm for the traveling salesman problem in a metric graph. A complete undirected graph \(G(V,E=\binom{V}{2})\) is called metric if the weight function \(w \colon E \to \mathbb{R}_{\ge 0}\) of its edges is a metric: for any three distinct vertices \(u,v,z\in V\) the triangle inequality holds \[w(u,v) \le w(u,z)+w(z,v) \ .\] (The two remaining metric axioms are automatically satisfied: there are no loops in the graph, so we can assume \(w(u,u)=0\), and the graph is undirected, so \(w(u,v)=w(v,u)\).)

It is easy to see that for any undirected graph (whose edge weights are non-negative), the minimum weight of a spanning tree is no greater than the minimum weight of a Hamiltonian path (or cycle). Indeed, a Hamiltonian path is a special case of a spanning tree, and deleting any edge of a Hamiltonian cycle gives a spanning tree. (It is interesting to note that a spanning tree has \(n-1\) edges and forms a connected subgraph, whereas a Hamiltonian cycle has \(n\) edges and every vertex has degree two. This additional, seemingly harmless, requirement significantly increases the computational complexity of the problem: the minimum spanning tree can be found in almost linear time, while no polynomial-time exact algorithm for the traveling salesman problem is known.)

Thus, in the first step, the algorithm constructs the minimum spanning tree of the graph. Its weight is certainly no greater than \(\text{OPT}\), the minimum Hamiltonian cycle. For example, for the graph

such a tree can be obtained.

In the next step, we double each edge of the tree. The weight of the resulting set of edges will be no greater than \(2\text{OPT}\).

The resulting graph is connected, and the degree of each vertex is even. Therefore, it contains an Eulerian cycle, which can be quickly found. For example, such a cycle: \[3 \to 4\to 3 \to 2 \to 5 \to 2 \to 3 \to 1 \to 3 \ .\] As seen, vertices repeat in it, but these repetitions can simply be discarded (we go through the list of vertices in the Eulerian cycle and skip the vertex if we have already been there): \[3 \to 4 \to 2 \to 5 \to 1 \to 3 \ .\] By discarding repetitions, we certainly did not increase the cycle length because the weights of the edges satisfy the triangle inequality. For example, the path \(5 \to 2 \to 3 \to 1\) is certainly not lighter than the path \(5 \to 1\). Thus, the weight of the resulting Hamiltonian cycle is certainly no greater than \(2\text{OPT}\).