1.
Introduction
2.
What is a Steiner Tree?
3.
Spanning Tree Vs. Steiner Tree
4.
Algorithm
5.
Solution
6.
Applications of Steiner Tree
7.
7.1.
What is a Spanning Tree?
7.2.
What is a Minimum Spanning Tree?
7.3.
Can a Steiner Tree contain vertices that are not in the given subset?
8.
Conclusion
Last Updated: Mar 27, 2024

# Steiner Tree Problem

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

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

### 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.