# Reduction of t-s TSP to TSP

Define t-s TSP to a path on an undirected, weighted (non-negative) graph that starts at $$s$$, visits every node exactly once and ends at $$t$$. The goal is to find a reduction to regular TSP - A path that starts at some node, visits every node exactly once and ends at the start node.

I've come up with the following approach and looking for some feedback on whether this holds.

Let $$G$$ be the input graph to t-s TSP. Construct $$G^{'}$$ by converting

• all edges incident to $$s$$ to out-edges
• all edges incident to nodes other than $$s$$ to bidirectional edges
• construct a directed edge from $$t$$ to $$s$$

Now, if there is a solution to t-s TSP on $$G$$, there is a solution to TSP on $$G^{'}$$ by following the same path as in t-s TSP on $$G$$, and appending the edge (t, s). If there is a solution to TSP on $$G^{'}$$, then there is a t-s TSP solution on $$G$$ by following the path of TSP on $$G^{'}$$ and excluding the edge - (t, s).

Thus, the reduction holds.

"Regular" TSP is undirected, but you have constructed a directed graph. You can keep everything undirected by introducing a dummy node that is adjacent to only $$s$$ and $$t$$.