<p>Sounds right. Denote by $G$ the original graph, and by $G'$ the graph after introducing the new vertices.</p>

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

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

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

<p>I don't see any bugs here, but maybe I missed something.</p>

CC BY-SA 3.0
2013-02-26T10:10:55.883Z
2013-02-26T10:10:55.883Z
Shaull
<p>Steiner Tree Problem:
Given a weighted graph G(V,E,w) where w is the weight function on <strong>edges</strong> 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.</p>

<p>Node-weighted Steiner Tree Problem
Given a weighted graph G(V,E,w) where w is the weight function on <strong>nodes</strong> 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.</p>

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

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

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

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

CC BY-SA 3.0
2013-02-26T14:43:38.177Z
This looks like homework.
Jeffε
CC BY-SA 3.0
2013-02-27T08:07:23.247Z
@JɛﬀE It isn't though.
Saage
<graph-theory>
Can any Steiner Tree Problem be converted to Node-Weighted Steiner Tree Problem?
Saage
# Can any Steiner Tree Problem be converted to Node-Weighted Steiner Tree Problem?

(Asked by: username_0 on 2013-02-26)

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.

**Tags:** graph-theory

> **Comments:**
> **username_1**: This looks like homework.  
> **username_0**: @JɛﬀE It isn't though.  

---

## 1 answers

### Answer by username_2 on 2013-02-26. Score: 2 | Accepted answer

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.

I don't see any bugs here, but maybe I missed something.


---

