Theoretical Basis

The Steiner Tree Problem is NP-Complete

Graph G = (V, E)
Positive Edge Weights W(e)
R a subset of V
B positive integer bound
Is there a subtree of G that includes all R with cost no more than B?
Heuristic less than twice optimum