Travelling Salesman Problem

Dragonfall

Given an answer to the travelling salesman problem, how do you check it in polynomial time? It seems you must know the length of every route and compare it to the answer.

2ltben

If you don't know the lengths of the routes Dijkstra's algorithm becomes more or less inert. If you remove the scalar values from the edges of a group, the edges become equidistant and it becomes a matter of finding a route where no vertice is visited twice.

Dragonfall

I'm not sure what you mean.

Alkatran

According to wikipedia, the traveling salesman problem is NP-Hard. NP-Hard means it is at least has hard as problems in NP. If we knew it was in NP, it would be NP-complete.

So, in answer to your question, I don't think there is a polynomial time algorithm that verifies a given path is the minimum. However, there is one for the decision problem "Is there a tour shorter than L?", which is the decision version of TSP.

Moo Of Doom

How does that not verify that a given tour is shortest? If you can decide in polynomial time whether there is a shorter tour than L, then if the answer turns out negative, then L is the shortest tour.

Alkatran

You're confusing two things: certifying an answer is correct, and actually finding the answer. The TSP decision problem is NP-complete, so there probably isn't a polynomial time algorithm to solve it, but we can verify solutions in polynomial time. The TSP problem is NP-hard, so there might not even be a polynomial time verifier.

In order for such a verifier to work you would need to show there are no shorter paths, but the certificate you've been given only mentions a single path, so you need to actually show no shorter paths exist, which happens to be just as difficult ( see http://en.wikipedia.org/wiki/Co-NP ).

Dragonfall

I'm slightly confused. What is the difference between the "TSP decision problem" and the "TSP problem"? What is a solution of the "TSP decision problem" and how do you verify it?

D H

You are given a set of nodes and distances between pairs of nodes for both the TSP problem and the TSP decision problem. The goal of the TSP problem is to find the minimum length tour. Note that the solution to the TSP problem is a Hamiltonian path. The solution is not a simple yes or no.

The TSP decision problem is a much simpler problem. You are given a length L. The goal is to determine whether there exists some tour whose length is shorter than L. This is a simple yes/no question. In particular, you are not asked for the optimal solution.

Dragonfall

Then what is the difference between the verification of the two? If you are given a hamiltonian path, you can get a length L, and if there is no tour whose length is shorter than L, it is the shortest path.

D H

Suppose we have three cities in an equilateral triangle, with nodes seperated by a length L. Some TSP decision problems with this network: Is there a hamiltonian path whose length is at most 4L? at most 2L?

Alkatran

It's very easy to verify one, and not so much to verify the other.

Verifying an answer to the decision problem is just summing up the path lengths you're given to make sure they're less than L, and making sure all the cities are visited exactly once.

Verifying the optimization problem requires you to show there are no shorter paths, which can be very hard.

Moo Of Doom

Ah, I was under the impression an answer to the decision problem would be "yes," rather than "here is a path shorter than L." Hence the source of my confusion.