2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This looks like homework. $\endgroup$
    – Jeffε
    Feb 26, 2013 at 14:43
  • 1
    $\begingroup$ @JɛffE It isn't though. $\endgroup$
    – Saage
    Feb 27, 2013 at 8:07

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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