Steiner Tree Problem

Spanning Tree Vs. Steiner Tree

A spanning tree or a minimum spanning tree is a tree that has the minimum weight and such that it spans through all the vertices. If the given subset of vertices is equal to the set of vertices in the Steiner Tree problem, then the problem reduces to finding the minimum spanning tree problem. If the given subset has only two vertices, then the problem reduces to the shortest path problem between two vertices. The minimum spanning tree problem is a polynomial-time solvable problem, whereas the minimum Steiner tree problem is NP-Hard, and the related decision problem is NP-Complete.

Algorithm

• We start with a subtree T such that it contains any one of the given terminal vertexes.
• While the subtree T doesn’t span all of the terminals
  • Select a terminal (x) such that it is not in subtree T and is closest to a vertex in T.
  • Now, add to the subtree T the shortest path that connects x with T.

The algorithm mentioned above is (2-2/n) approximate, which means that it guarantees that the solution which is produced by this algorithm is not more than this ratio of optimized solution for a given graph with n vertices. 

Solution

• Start by adding terminal B to the subtree T.
• Now, choose a terminal which is closest to a vertex in T but is not in T itself.
• The vertices which are connected to B are:
  • A(4)
  • C(6)
  • D(5)
    Choosing the terminal with the minimum weight possible: vertex A.
• Repeat Step 2 by following Dijkstra’s Algorithm until all vertices are traversed.
• Dijkstra’s Algorithm uses the formula:
• dx(y): least cost path from x to y
• dx(y) = minv { c(x, v) + dv(y) }
• The final cost of the Steiner tree for the above problem is:

Path: B - A - D - C E - F - G

Cost: 0 + 4 + 5 + 6 + 7 + 7 + 10 = 39

Applications of Steiner Tree

Some of the areas where a Steiner Tree is used are mentioned below:

• VLSI design
• Wireless Communication
• Network Routing
• Computational biology

Frequently Asked Questions

What is a Spanning Tree?

A Spanning tree is defined as a sub-graph that includes all the vertices of the graph with the minimum possible number of edges.

What is a Minimum Spanning Tree?

A Minimum Spanning Tree is a spanning tree in which the sum of the weight of all the edges is as minimum as possible.

Can a Steiner Tree contain vertices that are not in the given subset?

Yes, a Steiner Tree can contain vertices that are not in the given subset. Such vertices are used to connect the vertices of the given subset.

Conclusion

In this article, we have extensively discussed the Steiner Tree Problem

After reading about this problem, are you not feeling excited to read/explore more articles on Graph? Don’t worry; Coding Ninjas has you covered. To learn about the different types of graphs and applications, what is the difference between a graph and a tree, and what is breadth-first search.  

Check out this problem - Duplicate Subtree In Binary Tree

If you wish to enhance your skills in Data Structures and Algorithms, Competitive Programming, JavaScript, etc., you should check out our Guided path column at Code studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company. 

Do upvote if you find the blogs helpful.

Happy Learning!