How can I verify a solution to Travelling Salesman Problem in polynomial time?

Question

So, TSP (Travelling salesman problem) decision problem is NP complete.

But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is no way to find the optimal solution in polynomial time (which is because the problem is not in P)?

Anything that might help me see that the verification can in fact be done in polynomial time?

Answer 1

To be more precise, we do not know if TSP is in $\mathsf{P}$. It is possible that it can be solved in polynomial time, even though perhaps the common belief is that $\mathsf{P} \neq \mathsf{NP}$. Now, recall what it means for a problem to be $\mathsf{NP}$-hard and $\mathsf{NP}$-complete, see for example my answer here. I believe your source of confusion stems from the definitions: an $\mathsf{NP}$-hard problem is not necessarily in $\mathsf{NP}$.

As you and the Wikipedia page you link states, the decision problem is $\mathsf{NP}$-complete: given the costs and an integer $x$, decide whether there is a tour cheaper than $x$. One way of seeing the problem is in $\mathsf{NP}$ is to see that given a solution, it is easy to verify in polynomial time whether the solution is cheaper than $x$. How can you do this? Just follow the tour given, record its total cost and finally compare the total cost to $x$.

Answer 2

The crux is that you have to consider the decision problem:

Travelling Salesman Problem (Decision Version). Given a weighted graph G and a target cost C, is there a Hamiltonian cycle in G whose weight is at most C?

For a 'yes' instance, the certificate is just some Hamiltonian cycle whose weight is at most C. If you could solve this problem efficiently, you could find the cost of a minimum tour by binary search, starting with the weight of the entire network as an upper bound.

Answer 3

You are probably thinking of the problem of determining whether a given solution to the TSP is the best solution. However, there is no known polynomial solution for this, which means that this problem is in NP-hard, but not necessarily NP-Complete.

The TSP Decision Problem is actually about determining whether the weight of any solution in a graph G is at most cost C (as explained better in Niel's answer), which is certainly verifiable in polynomial time.

Answer 4

You can show that it is optimal given an oracle that solves the decision problem (see other answers) in polynomial time by querying if there exists a shorter solution. If your goal is to construct an optimal solution given the oracle, proceed as follows. Find the minimum total weight via binary search (or if there are non-integer edge weights, find a total weight which differs from the minimum by less than the min difference between two edge weights). Call this value $M$. For each edge in the graph, remove the edge, and query the oracle to see if there is still a solution of at most $M$. If so, leave the edge out, and continue. If not, put the edge back in, and continue. When you've processed all the edges, you'll be left with a Hamiltonian cycle of minimum weight.