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

- \($ d(x,y) \\geq 0\)$ for all \($ x, y\)$
- \($ d(x, y) = 0\)$ if and only if \($ x = y\)$
- \($ d(x, y) = d(y, x)\)$
- (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 ofrequired vertices. It is easy to verify that aminimum spanning treeon \($R\)$ is afeasible solutionfor this problem.The cost of anMSTon \($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

- Construct graph \($G'\)$ as a complete graph on \($R\)$
- 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\)$ - Find a
**MST**\($T_R\)$ on \($G'\)$ - 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\)$.

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

#### Proof

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

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

- \($w(T) \\leq \\overline w(T_R)\)$ since at most all the shortest paths are inserted.
- Let \($smt(G, R)\)$ be the Steiner minimal tree. Doubling edges of \($smt(G,R)\)$, find a Eulerian tour \($X\)$ on this new graph.
- \($w(X) = 2w(smt(G, R))\)$ since \($X\)$ traverses each edge exactly twice.
- 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.
- We get \($w(T) \\leq w(T_R) \\leq 2w(smt(G,L))\)$.