I know that finding the optimal solution to One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a solution to Open TSP but can't find a good resource to tell me whether or not One Way TSP is NP-Complete.
2
-
$\begingroup$ What is Open TSP? Is it the same as One Way TSP? Also, what do you mean by a "solution"? There are several ways to solve TSP problems, but none of them run in polynomial time, or else P would be equal to NP. $\endgroup$– HighheathFeb 25 at 10:58
-
$\begingroup$ @Highheath I have edited the question to clarify. I mean finding the optimal solution, which my algorithm can do in polynomial time. $\endgroup$– Darcy SuttonFeb 26 at 9:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
The answer depends on how you define "One Way TSP".
If the One Way TSP problem asks to compute the tour itself, then it cannot possibly be NP-complete since it is not a decision problem, and hence it does not even belong to the class NP.
If the problem is that of deciding whether there is a tour having cost at most $x$, for some input parameter $x$, then the problem belongs to NP (a yes-certificate is the tour itself) and it is NP-complete.
-
$\begingroup$ But wouldn't being able to solve the first problem allow you to solve the second, since if you can find the optimal solution, you can simply check if it is less than X? $\endgroup$ Feb 26 at 9:53
-
$\begingroup$ Absolutely. Nevertheless the first one is not NP-Complete while the second one is. $\endgroup$– StevenFeb 26 at 9:54
-
$\begingroup$
$\endgroup$
1
Take your "one way" problem. Add another city X, make the distance from start to X = 0, make the distance from X to any other city d which is longer than the sum of all other distances, then solve the original TSP for this instance.
In the solution, X obviously must have two neighbours. One neighbour must be the start city, otherwise you would have a total distance >= 2d, instead of a distance less than 2d. If you remove the city X from the solution, you have the optimal solution for the "one way" problem.
-
$\begingroup$ This is the reverse of what I was talking about. My question is if normal TSP can be be polynomial-time reduced to one-way TSP, not the other way round. $\endgroup$ Mar 18 at 9:50