Travelling salesman problem on cubic graphs

08 Jan 2018

This is the second post of a series that start here, based on the talks given at a French meeting on algorithms and complexity (GT CoA).

The second talk I want to “review” is: Applications and Constructions of cut-covering decompositions for connectivity problems, by Alantha Newman from the GSOP lab in Grenoble. Her work is partly based on an approch that began with the paper TSP on Cubic and Subcubic Graphs. What I describe in this post is based on this first paper. You can find more advanced lecture notes on this topic, by Newman, here.

---

Cubic graphs are graphs in which every node has degree 3. These graphs have special structures that are useful when designing approximation algorithms for the travelling salesman problem (TSP for short), and this is the topic of this post.

From TSP to Graph-TSP, and then to graphical-TSP

First, one may be confused by the fact the TSP is usually defined on weighted complete graphs, and not on some class of unweighted graphs. Indeed at first it does not make sense, as not all the graphs are eulerian, that is, for some graphs there does not exist a tour (i.e. a circuit in the graph that visits every node exactly once).

We actually deal with graph-TSP here, which is TSP on a subset of instances, whose edge weights are very special. Graph-TSP on an unweighted graph $G$ with $n$ nodes, means that we are looking for the shortest tour in the complete graph $C$ on $n$ nodes, where the weight of the edge between two arbitrary nodes $u$ and $v$ in $C$, is the length of the shortest path between these nodes in $G$. This is known as the metric completion of $G$, and indeed one can check that these distances follow the triangle inequality.

Another problem is interesting to us: graphical-TSP. In this new problem, given a graph, one has to find the shortest tour that visits all the nodes, but with the relaxation that it can visit the nodes and edges more than once.

“Graph-TSP” and “Graphical-TSP” are unpleasantly close names, but fortunately, the problems are equivalent. Suppose you have a tour for graph-TSP, then every edge $(u,v)$ has the weight of the path between $u$ and $v$ in $G$: one can take this path instead of the direct edge. Unfolding every edge this way, one gets a solution for graphical-TSP with the same weight. A similar construction works for the other direction.

The literature seems to focus on Graph-TSP, probably because it generalizes to the classic TSP more easily. For this post, the graphical-TSP is more handy, so we continue wih this one.

Simplified Christofides algorithm

Consider the following simple approximation algorithm for graphical-TSP. Take a minimum spanning tree of the graph $G$, and then consider the path taken if one does a traversal of this tree. This is a tour (in the sense of graphical-TSP), because every node is visited. It gives a 2-approximation, because the optimal tour cannot be lighter than the minimum spanning tree, and because every edge is taken exactly twice in this solution. Also it runs in polynomial-time, and that is what we are looking for.

Christofides algorithm is a refinement of this idea, and it gives a 3/2-approximation for metric instance of (the general) TSP. In particular it gives a 3/2-approximation for graphical-TSP on cubic graphs and we will show how to get better a better ratio.

A few graph theoretic definitions

Before we get to why cubic graphs are nice, we need a few definitions from graph theory.

• A bridge in a graph, is an edge whose removal disconnects the graph.
• A perfect matching, is a matching, i.e. a set of vertex-disjoint edges, that matches all vertices in G.
• A (vertex disjoint) cycle cover is a set of vertex-disjoint cycles that spans all vertices in G.

Note that the two last definitions are pretty similar, and indeed they are two examples of a more general concept, called $k$-factors. But let’s go back to cubic graphs.

Cycle covers from Petersen’s theorem

Petersen’s theorem states that every bridgeless cubic graph, has a perfect matching.

Now, take a bridgeless cubic graph and remove a perfect matching. What is left? A cycle cover of G. Indeed the degree of every node has decreased from three to two, thus the resulting graph must be union of cycles spanning all nodes.

All together now

Let’s put all the ingredients together to get an approximation algorithm for graphical-TSP with a better ratio than Christofides algorithm.

First find a cycle cover of $G$ as in the previous section. This can be done in poynomial time, thanks to the blossom algorithm. This subgraph is visiting every node exactly once, but it is not a tour yet, because it is disconnected. We will now link these cycles together. Consider the graph $G’$ made by contracting every cycle into just one node. On this graph $G’$, take the tour induced by the spanning tree as in the simplified Chritofides algorithm. This tour corresponds to a set of edges in $G$. Now this set of edges plus the edges of the cycle cover form a tour, and we have a solution for graphical-TSP!

What is the weight of this tour? The cycle cover contains exactly $n$ edges. Let $c$ be the number of cycles in this cover. Then there are $2c-1$ edges in the tree. It follows that the tour has weight $n+2c-1$. With a bit of work¹ one can get $c\leq n/6$. This yields to a tour with less then $4n/3$ edges. This is a 4/3-approximation, as a tour cannot be shorter than $n$, which improves on Christofides.

We discussed only cubic graphs and got only a small improvement here, but the approach based on studying the cycle covers is fruitful in other context, and led to many improvements for this fundamental problem.

Bonus: recent advances on asymmetric TSP

On a related topic, there has been recent advances on asymmetric TSP, that is TSP where the directed edges $(u,v)$ and $(v,u)$ do not have the same weight in general. A recent paper gives the long-awaited first constant-approximation algorithm for the problem. You will find links to a summary and videos on Jakub Tarnawski’s webpage. The paper has been covered on Gödel’s lost letter², and in Quanta magazine.

Footnotes