I am wondering where could I find proof for following S-TSP to TSP transformation.

S-TSP (Steiner Travelling Salesman Problem) def: Let $G=(V, E)$ be a non-directed weighted graph. Let $V' \subset V$ be a subset of V that is required to be visited. Optimal solution is to find the shortest possible closed walk to go through all vertices from $V'$.


TSP: It is very popular problem, so I won't define it here.

Let D be distance matrix.

I am working on METRIC instances, so $\forall i, j, k \in D: d(i, j) + d(j,k) \geq d(i, k)$

What I did in my software implementation: I calculated the distance matrix. I created a COMPLETE subgraph G'(V', E), where the weight of the edges was set to distance (minimal weight of path between two specific nodes). On that subgraph I ran TSP methods.

I think that the optimal solution for S-TSP problem on graph G is equivalent to optimal solution for TSP problem on graph G'.

The proof I thought was correct:

Let S be solution of S-TSP problem. Let $\hat{V}$ be a subset of vertices that are visited multiple times.

  1. Choose vertex $v_i \in \hat{V}$
  2. Let $v_j$ be a vertex that was visited just before $v_i$.
  3. Let $v_k$ be a vertex that is visited just after $v_i$.
  4. Let's confirm that if we replace $v_j, v_i, v_k$ in the solution with $v_j, v_k$ that the solution doesn't change.
  5. As we are working with metric instances $d(v_j, v_i) + d(v_i, v_k) \geq d(v_j, v_k)$. From this step we can see that the solution can't change.
  6. If we do this steps for all vertices that are visited multiple times, we can see that the solution is the same.

Am I correct? Is there a better proof out there, better formulated?

Related question: Variation of TSP - Revisit Nodes, but without proof


Your Answer

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

Browse other questions tagged or ask your own question.