5

The Steiner Tree version that I am considering is the following: given an undirected weighted graph $G=(V,E)$ and a subset of vertices $T \subseteq V$, find a minimum tree that connects all the vertices in $T$ which possibly contains vertices outside $T$.

I know that both TSP and Steiner Tree are NP-hard and there are approximation algorithms for these problems that have an approximation guarantee of $2$.

I was wondering whether there is any reduction from the Steiner Tree to TSP?

user12632521
  • 111
  • 4
  • 1
    What kind of reduction are you looking for exactly? The question is now a bit vague. The decision version of both problems is NP-complete, and by applying the machinery that proves the Cook-Levin theorem, you can use their membership of the NP class to reduce either problem to Satisfiability, and from Satisfiability you can then reduce to either problem (using the original reductions of Karp). – Paul Bouman Aug 17 '21 at 22:02

0 Answers0