Traveling Salesman Problem Meets Complexity Theory
Crazy ideas meet crazed audience
Merrill Flood was a mathematician who publicized the Traveling salesman problem TSP back in the 1940s.
He says that he found the problem while:
I was struggling with the problem in connecting with a schoolbus routing study in New Jersey.
Today I thought we might look at the TSP from a viewpoint of complexity theory.
First, we note that the origins of the TSP are unclear. In 1832 it was mentioned in a handbook for traveling salesmen in Germany and Switzerland. William Hamilton talked about the related problem later named for him:
On finding a circuit through all points of graph.
Karl Menger, in the 1930s, defined the TSP, and considered the obvious bruteforce algorithm, and observed the nonoptimality of the nearest neighbor heuristic. We have annotated Wikipedia’s optimaltour example to show (in blue) one case where a node is not connected to either of its two nearest neighbors in the tour and another where a mutual nearestneighbor edge is not used in the optimal tour (the latter is a slight fib asis but can be nudged, we believe):
Modern Times–Practice
The TSP is now well known to be NPcomplete thanks to Dick Karp’s brilliant work in the 1970s. Flood would be happy to hear—we believe—that there is now a computer program Concorde that can solve TSP with many cites and get a nearly optimal solution. The authors of this program are: David Applegate, Robert Bixby, Vasek Chvatal, and William Cook.
Concorde has been applied to problems of gene mapping, protein function prediction, vehicle routing, conversion of bitmap images to continuous line drawings, scheduling ship movements for seismic surveys, and in studying the scaling properties of combinatorial optimization problems.
Modern Times–Theory
Concorde’s solutions are guaranteed to be within 23% of optimal and have worked for problems with tens of thousand cities or more. A lot more than Flood considered.
So why are we interested in the TSP still? A good question.
The answer is not simple. In spite of the problem’s NPcompleteness and widespread belief that PNP we still do not know for sure. Could there be an algorithm that always solves TSP in polynomial time? We do not know.
We also as complexity theorists want provable algorithms, want exact algorithms, or at least approximate algorithms with provable bounds. These are lacking. This is why we were excited by the recent result of a tiny improvement to the bound on TSP by Anna Karlin, Nathan Klein, and Shayan Oveis Gharan.
Maybe we are crazy to be excited over a microscopic shaving off from . But their result comes with new ideas, and since we don’t believe that is Nature’s final answer, those ideas should yield further advances. What we are really crazy over is new ideas, and that prompts us to attempt to find another in the rest of this post. What complexity theorists do have more of than when Ken and I started is receptacles for new ideas, and we try for one in resourcebounded communication complexity.
Alice and Bob
In this spirit of craziness let’s take a complexity viewpoint of TSP. Let’s visit Alice and Bob. By the way I always have thought the invention of them by Ron Rivest, Adi Shamir, and Leonard Adleman in their 1978 RSA paper was important. This idea has probably helped improve exposition more than any other single idea.
They Meet the TSP
So suppose that Alice and Bob are presented with a city TSP. Further suppose that Alice can solve the TSP, but Bob like the rest of us cannot. An issue is:
Can Alice send a succinct message to Bob that allows him to find an optimal tour in polynomial time?
Without the word “succinct” there would be the simple answer of sending Bob her optimal tour. We will discuss a modest improvement: she can send half as many bits to Bob as it takes to describe the optimal tour. We suspect the following is known, but it suggests a possible interesting direction.
Theorem 1 (Main) Alice can send Bob a message of bits, so that he can get an optimal TSP tour in polynomial time.
This theorem holds for general TSP: it can be asymmetric and need not satisfy the triangle inequality.
The Proof
Proof: Let’s assume that ; the argument is the essentially same if is odd.
Alice will first solve the TSP exactly. Assume she finds an optimal tour that visits the cities in order
To simply the notation let be the distance from to . Then let Alice send Bob the odd cities in order
This message has the right length in bits of .
Bob receives this message and creates the following bipartite graph : The left vertices are the cities
The right vertices are
has edges connecting every left vertex to every right vertex; i.e., is the complete bipartite graph.
The first idea is that any perfect matching in extends uniquely to a tour, because Bob knows the order of the odd vertices in Alice’s tour. That is, if is an edge in the tour, then Bob knows that the next edge goes to node (modulo ).
The second idea—which is a caveat—is that an optimal matching under the graph’s original distance function might not produce Alice’s tour. For this to be true, it would need to be the case that for every optimal tour, either one of the two perfect matchings it induces would need to be an optimal matching for the tour’s odd and even vertices. An example where this fails is shown at lower left in our diagram above: The green edge is part of the optimal oddeven matching but is not in Alice’s optimal tour.
The trick is to change the distance function to include the edge that Bob must add to the tour. That is, we give the edge the cost
Note has edges connecting every left vertex to every right vertex; i.e., is the complete bipartite graph.
Bob then finds a minimum cost matching for the graph . This can be done in polynomial time. We claim the following:

The matching
has the cost of the original TSP tour.
 Every minimum complete matching of yields a tour for the original TSP with the same cost as the matching.
These claims imply that Bob can solve the TSP in polynomial time.
We note that (1) follows from the definition of the graph and its costs. In order to see (2) let match to . This means that there are edges
for all . This is clearly a tour, since is a permutation by the definition of matching.
Open Problems
The fact that Alice can send only half of the tour to Bob suggests: can we avoid having Alice solve the TSP in order to compute her message? This is the direction we are interested in. If she could do that it would improve some known complexity bounds on TSP. A possible idea is:
Replace having Alice solve the city TSP exactly. Instead have her solve some randomly selected subproblem exactly, and then use the above method to add in the remaining cities.
Can this work?
We have not found something like this when searching on TSP and communication complexity, but would not be surprised if the matching idea, caveat, and trick have been noticed and remarked on before.
Why do you say “nearly optimal” and “guaranteed to be within 23% of optimal”? Concorde is an exact solver
And, can this trick be applied recursively?
not mentioned, TSP is somewhat unique among NP complete problems in that it can be explained very simply in terms of everyday life/ understanding, eg to a teenager, so in that way its somewhat iconic of the field. other problems such as satisfiability are easily understood by CS students but still more abstract. some other NP complete problems are like this eg bin packing etc.
Is there a known relation between the constant in Theorem 1 and hardness of approximation?
How much more than half of the optimal solution would Bob need for MAX3SAT?
Or more generally, a protocol with some functions f(n), g(n). We ask the Alice goddess for f(n) selected bits and we complete the task in time g(n). And we want f(n) and g(n) as small as possible (f to equal 0 and g to be polynomial). This has the feeling of an Arthur–Merlin protocol, but I am not an expert.