It is known that the metric steiner tree problem is NP hard (Garry and Johnson [1977]). I wanted to know if there is a simpler way of proving the same. Specifically, I am trying to find a polynomial time reduction from the steiner tree problem to the metric steiner tree problem. I am aware of a reduction which uses shortest path between two vertices, but as far as I know, that transformation is just approximation preserving. Can the same be used as a proof for NP hardness and if so, how ?
-1
$\begingroup$
$\endgroup$
0
$\begingroup$
$\endgroup$
Let $G$ be the instance of the general Steiner tree problem and $G'$ be the shortest-path closure of $G$. When the shortest path of every pair of vertices on $G$ is unique, the cost of the Steiner minimum tree on $G$ is the same as that on $G'$. I think that there exists some simple way to transform the edge costs such that the shortest paths are unique and the instance size is polynomial to the original one.
