<p>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.   </p>

CC BY-SA 3.0
2014-03-20T15:26:38.267Z
2014-03-20T15:26:38.267Z
Bangye
<p>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 ?</p>

<np-hardness>
NP Hardness of Metric Steiner Tree
user62089
# NP Hardness of Metric Steiner Tree

(Asked by: username_0 on 2014-03-19)

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 ?

**Tags:** np-hardness


---

## 1 answers

### Answer by username_1 on 2014-03-20. Score: 0

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.


---

