Is One Way TSP NP-complete?

Question

I know that 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 Open TSP is NP-Complete.

Answer 1

Here is a self-contained proof for the NP-completeness of one-way TSP.

We can reduce normal (closed) TSP to one-way (open) TSP by solving $\binom n2$ one-way TSP instances, each corresponding to a different edge $uv$ in the closed TSP problem:

• Add two new cities $a$ and $b$ to the original complete graph on $n$ vertices.
• Add new edges $au$ and $bv$ with an arbitrary finite weight. Call the sum of weights of edges in the graph so far $M$.
• Add all remaining edges that have to be added to get a complete graph, each with a weight larger than $M$.
• It is clear that the one-way TSP solution for this expanded graph with $n+2$ vertices will start with $au$ and end with $vb$, and the path in between is the TSP solution for the original graph when the endpoints are constrained to be $u$ and $v$.
• After solving all $\binom n2$ one-way TSP instances, take the parts of the solutions in the original graph and close the loops there. The loop with the lowest weight is the normal TSP solution for the original graph.

Since the reduction is clearly doable in polynomial time and space, one-way TSP is NP-complete.