# Can any Steiner Tree Problem be converted to Node-Weighted Steiner Tree Problem?

Steiner Tree Problem: Given a weighted graph G(V,E,w) where w is the weight function on edges and a subset of vertices S⊆Q called terminals, a Steiner Tree is a connected subgraph which connects all vertices in S. Finding minimum weight Steiner Tree is called Steiner Tree Problem.

Node-weighted Steiner Tree Problem Given a weighted graph G(V,E,w) where w is the weight function on nodes and a subset of vertices S⊆Q called terminals, a Node-Weighted Steiner Tree is a connected subgraph which connects all vertices in S. Finding minimum weight Steiner Tree is called Node-Weighed Steiner Tree Problem.

My question is: can any Steiner Tree Problem be converted to Node-weighted Steiner Tree Problem? I have the following approach and need to verify whether it is correct:

Lets assume we have a Steiner Tree problem with weighted edges. Consider an edge (u, v) with weight w assigned to it. Lets place a vertex X on this edge, so that the edge splits in two edges: (u, X) and (X, v). Assign zero weight to each of those edges, and assign weight w to vertex X. Repeat this for every edge of the initial graph.

The obtained graph will be node weighted and any solution to the node-weighted problem can be easily converted to match initial Steiner Tree Problem.

Basically, I need someone to verify all above is valid. I would also greatly appreciate any references from reliable sources, regarding this issue.

• This looks like homework. – Jeffε Feb 26 '13 at 14:43
• @JɛﬀE It isn't though. – Saage Feb 27 '13 at 8:07

Sounds right. Denote by $G$ the original graph, and by $G'$ the graph after introducing the new vertices.
The first direction is trivial - every Steiner tree in $G$ corresponds to a Steiner tree in $G'$, with the same weight (by splitting each edge with its new vertex).
The second direction is less trivial. Still, consider a minimal Steiner tree $T$ in $G'$. We can assume w.l.o.g that $T$ does not contain any leaf that corresponds to a new edge-vertex. Indeed, this vertex is not in $S$, so if it is a leaf, it can be removed from the tree, keeping it a Steiner tree with minimal weight (unless you allow negative weights, which I assume you don't).
Now that we have a Steiner tree without edge-vertex leafs, we can convert it to a Steiner tree in $G$: root the tree by some vertex that is not an edge-vertex, then by the construction, all the edge-vertices have a single child in this tree. So you can replace each pair of edges $(u,X),(X,v)$ by $(u,v)$ in the original graph, obtaining a Steiner tree with the same weight.