1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Is there a reason TSP wouldn't work on a directed graph? The concept of traversal is the same for a directed graph. $\endgroup$
    – heckeop
    May 2, 2021 at 6:41
  • $\begingroup$ There are directed versions of TSP, with or without symmetric distances, but they are typically slower to solve for the same number of nodes because you have twice as many edges. $\endgroup$
    – RobPratt
    May 2, 2021 at 13:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .