Question

In the MINIMUM STEINER TREE problem, the input consists of: a complete graph $\mathit{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$with distances ${\mathrm{d}}_{uv}$between all pairs of nodes; and a distinguished set of terminal nodes$\mathit{V}\mathbf{\text{'}}\mathbf{\subseteq }\mathit{V}\mathbf{.}$The goal is to find a minimum-cost tree that includes the vertices $\mathit{V}\mathbf{\text{'}}$. This tree may or may not include nodes in $\mathit{V}\mathbf{-}\mathit{V}\mathbf{\text{'}}$

Suppose the distances in the input are a metric (recall the definition on page 292). Show that an efficient $\mathit{r}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathbf{-}\mathbf{2}$approximation algorithm for MINIMUM STEINER TREE can be obtained by ignoring the nonterminal nodes and simply returning the minimum spanning tree on$\mathit{V}\mathbf{\text{'}}$. (Hint: Recall our approximation algorithm for the TSP.)

Short answer

The MINIMUM STEINER TREE problem is proved.

Step-by-step solution

Step 1: Steiner Tree.

Steiner Tree is a minimum weight tree or a minimum spanning tree that spans through allvertices. If the given subset (or terminal) vertices are equal to the set of all vertices in the Steiner Tree problem, then the problem becomes the Minimum Spanning Tree problem.

And if the given subset contains only two vertices, then it shortest path problem between two vertices. Finding out Minimum Spanning Tree is polynomial-time solvable, but the Minimum Steiner Tree problem is NP-Hard and the related decision problem is NP-Complete.

Step 2: MINIMUM STEINER TREE problem.

a).

For Shortest Path-based Approximate Algorithm Since, the Steiner Tree problem is NP-Hard, there are no polynomial-time solutions that always give optimal cost. Therefore, there are approximate algorithms to solve the same. Below is one simple approximate algorithm. AndThe minimum Steiner tree can be approximated by computing the minimum spanning tree of the sub graph of the metric closure of graph induced by the terminal nodes, where the metric closure of graph is the complete graph in which each edge is weighted by the shortest path distance between the nodes in graph .The following steps are mention below for finding the MINIMUM STEINER TREE:

1) Start with a sub tree$T$ consisting of one given terminal vertex.

2) While$T$ does not span all terminals

a) Select a terminal $x$not in T that is closest to a vertex in $T$.

b) Add to T the shortest path that connects $x$with $T$.

Hence, the input consists of: a complete graph with distances between all pairs of nodes; and a distinguished set of terminal nodes$V\text{'}\subseteq V.$ The goal is to find a minimum-cost tree that includes the vertices $V\text{'}$. This tree may or may not include nodes in $V-V\text{'}$

This algorithm is$(2-2/n)$ approximate, i.e., it guarantees that the solution produced by this algorithm is not more than this ratio of optimized solution for a given graph with n vertices. There are better algorithms also that provide a better ratio.

the distances in the input are a metric. and an efficient ratio two approximation algorithm for MINIMUM STEINER TREE can be obtained by ignoring the nonterminal nodes and simply returning the minimum spanning tree on that vertex .And a minimum weight tree or a minimum spanning tree that spans through allvertices. If the given subset (or terminal) vertices are equal to the set of all vertices in the Steiner Tree problem, then the problem becomes the Minimum Spanning Tree problem.