Preprocessing for Steiner Tree Problems

by Mihai Popa for OGDF - Open Graph Drawing Framework

The Steiner Tree problem consists of connecting a set of required vertices in a weighted graph at minimum cost. Although the Steiner Tree problem is NP-hard, it can be solved efficiently in practice. One main reason is the existence of powerful preprocessing methods able to reduce the instance size.