Skip to content

Traveling Salesman Problem Meets Complexity Theory

November 19, 2020

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:

{\dots} I was struggling with the problem in connecting with a school-bus 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 brute-force algorithm, and observed the non-optimality of the nearest neighbor heuristic. We have annotated Wikipedia’s optimal-tour 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 nearest-neighbor edge is not used in the optimal tour (the latter is a slight fib as-is but can be nudged, we believe):

Modern Times–Practice

The TSP is now well known to be NP-complete 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 2-3% 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 NP-completeness and widespread belief that P{<}NP 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 {1.5} 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 {1.5}. But their result comes with new ideas, and since we don’t believe that {1.5 - \epsilon} 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 resource-bounded 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 {n} 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 {\frac{n}{2} \lceil \log_{2}n \rceil} 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 {n=2m}; the argument is the essentially same if {n} is odd.

Alice will first solve the TSP exactly. Assume she finds an optimal tour that visits the cities in order

\displaystyle  x_{1}, x_{2}, \dots, x_{n}, x_{1}.

To simply the notation let {d(i,j)} be the distance from {x_{i}} to {x_{j}}. Then let Alice send Bob the odd cities in order

\displaystyle  x_{1}, x_{3}, \dots, x_{2m-1}.

This message has the right length in bits of {\frac{n}{2} \lceil \log_{2}n \rceil}.

Bob receives this message and creates the following bipartite graph {G}: The left vertices are the cities

\displaystyle  x_{2}, x_{4}, \dots, x_{2m}.

The right vertices are

\displaystyle  x_{1}, x_{3}, \dots, x_{2m-1}.

{G} has edges connecting every left vertex to every right vertex; i.e., {G} is the complete bipartite graph.

The first idea is that any perfect matching in {G} extends uniquely to a tour, because Bob knows the order of the odd vertices in Alice’s tour. That is, if {(2k+1,2l)} is an edge in the tour, then Bob knows that the next edge goes to node {2k+3} (modulo {n}).

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 odd-even 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 {(2k+1,2l)} the cost

\displaystyle  d(2k+1,2l) + d(2l,2k+3).

Note{G} has edges connecting every left vertex to every right vertex; i.e., {G} is the complete bipartite graph.

Bob then finds a minimum cost matching for the graph {G}. This can be done in polynomial time. We claim the following:

  1. The matching

    \displaystyle  x_{2k+2} \rightarrow x_{2k+1},

    has the cost of the original TSP tour.

  2. Every minimum complete matching of {G} 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 {G} and its costs. In order to see (2) let {2\pi(k)} match to {2k+1}. This means that there are edges

\displaystyle  2k+1 \rightarrow 2\pi(k) \rightarrow 2k+3,

for all {k}. This is clearly a tour, since {\pi(k)} is a permutation by the definition of matching. \Box

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 {n} 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.

5 Comments leave one →
  1. November 19, 2020 11:27 am

    Why do you say “nearly optimal” and “guaranteed to be within 2-3% of optimal”? Concorde is an exact solver

  2. Sally permalink
    November 20, 2020 5:27 pm

    And, can this trick be applied recursively?

  3. November 20, 2020 9:42 pm

    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.

  4. November 23, 2020 7:05 pm

    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 MAX-3SAT?

  5. Cristóbal Camarero permalink
    November 25, 2020 3:15 pm

    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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s