Steiner Tree Problem explained (part 1: introduction)

This is a series of articles about Steiner Trees, one of the most studied problem in computer science.

What is a Steiner Tree?

Given a weighted undirectional graph G, and a subset R of V(G) (the set of vertices of G), a Steiner Tree is a tree spanning over R (it may contain vertices not in R).

What is the Steiner Tree Problem, or minimum Steiner Tree?

Given a weighted undirectional graph G, and a subset R of V(G), the Steiner Tree Problem is to find the minimum Steiner Tree, i.e. the Steiner Tree with minimum weight.

Example

Graph and subset of Nodes (in yellow) representing a Steiner Tree Problem

Solution to Steiner Tree Problem (Steiner Tree in blue)

Why is this problem interesting?

This is a NP-hard problem, which means we don’t know if there exists a polynomial algorithm to solve it. Some research focuses on finding polynomial algorithms that provide a “good” solution, for instance with the weight of the returned solution less than twice the the weight of the actual optimal solution. Some other research focuses on re-optimization, that is, given an optimized solution for G, if G…