Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
This looks like homework. –  JɛffE Feb 26 '13 at 14:43
    
@JɛffE It isn't though. –  Saage Feb 27 '13 at 8:07
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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