-1
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.