In the blog, we will look at the Steiner tree problem in which we are given an undirected graph with positive edge weights, and a subset of vertices in that graph are given, the task is to find the minimum cost of the Steiner Tree.

What is a Steiner Tree?

In the problem, a graph and a subset of vertices in that graph are given, where a Steiner tree is a tree that spans through the given subset. It is possible that the Steiner tree may contain some vertices which are not a part of the given subset but are used to connect the vertices of the subset. The set of vertices provided is called Terminal vertices, whereas the set of vertices that are used to construct the Steiner tree is called the Steiner vertices.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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

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.