NP-hard general
Even in graphs. Polynomial for trees + planar graphs.
Advertisement
Dreyfus-Wagner DP
O(3^K × V + 2^K × V²) where K = number of terminals. Enumerate subsets of terminals.
Advertisement
Approximations
2-approx: MST of complete graph on terminals (with shortest-path distances). Best known: (1 + ln(3)/2) ≈ 1.55 (Byrka et al).
Special cases
Metric Steiner: distances satisfy triangle inequality. Euclidean Steiner: points in plane, use Steiner points.