31
$\begingroup$

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?

$\endgroup$
20
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ "Just follow the tour given, record its total cost and finally compare the total cost to x." -> Yes, but there are exponential number of tours to check! $\endgroup$ – Lazer Jul 20 '12 at 7:45
  • 2
    $\begingroup$ I was just a tad too slow, it seems. ;-) $\endgroup$ – Niel de Beaudrap Jul 20 '12 at 7:45
  • 3
    $\begingroup$ @Lazer No, there is exactly one tour to check. You are given a tour and you record its length. If it is less than $x$, output yes, otherwise no. $\endgroup$ – Juho Jul 20 '12 at 8:02
  • $\begingroup$ "decide whether there is a tour" this definitely means that we are not given a tour. What am I missing? $\endgroup$ – Lazer Jul 20 '12 at 8:04
  • 3
    $\begingroup$ @Lazer No, in the problem you are given a weighted graph and a target cost. The certificate is a tour. For an alternative explanation, see Niel's answer. Just as in the example on Wiki in the case of SUBSET-SUM, we are not given zero, but instead we are given a particular subset as a certificate. $\endgroup$ – Juho Jul 20 '12 at 8:20
34
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Sorry for the pedantry, but TSP is not NP-hard because there are $O(n!)$ tours. For example, sorting is in P although there are $n!$ possible permutations as well. Huge or quickly growing search spaces don't always imply hardness. $\endgroup$ – Juho Jul 20 '12 at 14:49
  • $\begingroup$ @Juho It is possible to verify that a sequence is sorted, by simply checking that $n_0 <= n_1 <= ...$. However, to know that something is the BEST solution for TSP, it is required to know that the cost is the minimum cost, which inherently requires knowing all other costs. $\endgroup$ – Casey Kuball Jul 20 '12 at 14:53
  • 4
    $\begingroup$ No, you can obtain the optimum even without computing the lengths of all the other tours. And yes, it is possible to prove this is in fact the optimum without computing all the other tours. For an example consider branch & bound. $\endgroup$ – Juho Jul 20 '12 at 15:09
  • 7
    $\begingroup$ All I'm saying is that huge search spaces don't necessarily mean the problem is difficult. Even when we for example don't know of a better algorithm than brute-force that enumerates all the possibilities, it doesn't mean it's the only algorithm out there. Dynamic programming is good example even here: the Held-Karp algorithm is an exact algorithm for TSP running in $O(n^22^n)$ time. Sorry, this is arguably just nitpicking, but I just wanted to add a reminder :) $\endgroup$ – Juho Jul 20 '12 at 15:15
  • $\begingroup$ @Juho good point. I've updated the answer to no longer indicate brute force as the only option (only that there aren't any polynomial solutions). $\endgroup$ – Casey Kuball Jul 20 '12 at 16:55
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.