Steiner Tree Problem

| Tags Algorithm 

This problem is required to find the shortest interconnect for a given set of objects. It is superficially similar to the MST problem: given a set V of points(vertices), interconnect them by a network(graph) of shortest length, where the length is the sum of the lengths of all edges. The difference between the Steiner tree problem and the MST problem is that, in the Steiner tree problem, extra intermediate vertices and edges may be added to the graph in order to reduce the length of the spanning tree. These new vertices introduced to decreases the total length of connection are known as Steiner points or Steiner vertices. It has been proved that the resulting connection is a tree, known as Steiner tree. There may be several Steiner trees for a given set of initial vertices.

Metric Properties

  1. \($ d(x,y) \\geq 0\)$ for all \($ x, y\)$
  2. \($ d(x, y) = 0\)$ if and only if \($ x = y\)$
  3. \($ d(x, y) = d(y, x)\)$
  4. (Triangle inequality) \($ d(x,y) \\leq d(x,z) + d(z,y)\)$

Metric Seiner Problem

Given an undirected graph \($ G = (V, E)\)$ with nonnegative edge costs and whose vertices are partitioned into two sets, required and Steiner, find a minimum cost tree in \($ G\)$ that contains all the required vertices and any subset of the Steiner vertices. With a restriction to instances in which the edge costs satisfy the triangle inequality, i.e., \($ G\)$ is a complete undirected graph, and for any three vertices \($ u, v, w, cost(u, v) \\leq cost(u, w) + cost(w, v)\)$, it is named the metric Steiner tree problem.

MST-based Algorithm

Algorithm
Let \($R\)$ denote that set of required vertices. It is easy to verify that a minimum spanning tree on \($R\)$ is a feasible solution for this problem.The cost of an MST on \($R\)$ is within \($2OPT\)$.

Eulerian Graph

In graph theory, an Eulerian trail(or Eulerian path) is a trail in a graph which visits every edge exactly once, an Eulerian cycle is an Eulerian trail which starts and ends on the same vertex. And a graph containing an Eulerian cycle is called Eulerian Graph.

Steps

  1. Construct graph \($G'\)$ as a complete graph on \($R\)$
  2. Cost of edge \($(u,v)\)$ in \($G'\)$ is defined to be the shortest \($u-v\)$ path in \($G\)$, \($G'\)$ is a metric closure on \($R\)$
  3. Find a MST \($T_R\)$ on \($G'\)$
  4. Replace each edge in MST with corresponding path in \($G\)$ to obtain \($T\)$, and \($T\)$ is a Steiner Tree.

MST-Seiner Algorithm

Input: A graph \($G=(V,E, w)\)$ and a required set \($R \\subset V\)$.
Output: A Steiner Tree \($T\)$.

  1. Construct the metric closure \($G_R\)$ on required set \($R\)$
  2. Find an MST \($T_R\)$ on \($G_R\)$
  3. T \($ \\leftarrow \\emptyset\)$
  4. for each edge \($e=(u,v) \\in E(T_R)\)$ do
  5. ␣␣␣␣Find a shortest path \($P\)$ from \($u\)$ to \($v\)$ on \($G\)$
  6. ␣␣␣␣if \($P\)$ contains less than two vertices in \($T\)$ then
  7. ␣␣␣␣␣␣␣␣Add \($P\)$ to \($T\)$
  8. ␣␣␣␣else
  9. ␣␣␣␣␣␣␣␣Let \($p_i\)$ and \($p_j\)$ be the first and last vertices already in \($t\)$
  10. ␣␣␣␣␣␣␣␣Add subpaths from \($u\)$ to \($p_i\)$ and from \($p_j\)$ to \($v\)$ to \($T\)$
  11. Output \($T\)$

Proof

\($w(T) \\leq 2w(smt(G, R))\)$

Let \($G_R = (R, E(G_R), \\overline w)\)$.

  1. \($w(T) \\leq \\overline w(T_R)\)$ since at most all the shortest paths are inserted.
  2. Let \($smt(G, R)\)$ be the Steiner minimal tree. Doubling edges of \($smt(G,R)\)$, find a Eulerian tour \($X\)$ on this new graph.
  3. \($w(X) = 2w(smt(G, R))\)$ since \($X\)$ traverses each edge exactly twice.
  4. On the other hand, since \($X\)$ visits all required vertices, we have \($w(X) \\geq w(tsp(G_R)) \\geq w(T_R)\)$ where \($tsp(G_R)\)$ is a minimal Rudrata cycle on G_R.
  5. We get \($w(T) \\leq w(T_R) \\leq 2w(smt(G,L))\)$.

Previous     Next