Steiner Tree

Given a graph and a set of $k$ terminals, find the minimum-weight connected subgraph containing all terminals. It may use extra (“Steiner”) vertices.

$k=2\to \text{shortest path},k=n\to \text{MST},\text{in between}\to \text{NP-hard}.$

Exact: Dreyfus-Wagner — $O(3^{k}n+2^k{n}^2)$

DP over subsets of terminals: dp[mask][v] = the minimum cost of a tree connecting the terminal set mask and containing vertex $v$.

Two transitions:

1. Merge two sub-trees meeting at $v$: ${\min }_{\text{sub}}(dp[\text{sub}][v]+dp[\text{mask}\setminus \text{sub}][v])$.
2. Grow by moving the meeting point along an edge — a Dijkstra over the whole graph for each mask.

See Dreyfus-Wagner for the code. Practical for $k\le 12$-$15$ with $n$ in the thousands.

Approximation

The metric-closure MST — a 2-approximation:

1. Compute all-pairs shortest paths among the terminals.
2. Build the complete graph on the terminals with those distances.
3. Take its MST.
4. Expand each MST edge back into its shortest path.

// 2-approximation
for each terminal t: dijkstra(t);                       // k runs
build complete graph on terminals with dist[i][j]
mst = kruskal(that graph)
expand each MST edge into its path

Why 2: the optimal Steiner tree, doubled, gives an Eulerian tour of the terminals; shortcutting yields a spanning tree on the terminals of cost $\le 2\mathrm{OPT}$, and the MST is no worse. ∎

The best known ratio is $\ln 4+\epsilon \approx 1.386$ (Byrka et al.), via LP rounding.

The variants

Variant	Complexity
$k=2$	shortest path, P
$k=n$	MST, P
General $k$	NP-hard
$k$ small	FPT: $O(3^{k}n+2^k{n}^2)$
Steiner tree in a tree	P — the answer is the virtual tree of the terminals
Steiner forest (pairs to connect)	NP-hard; 2-approximation by primal-dual
Directed Steiner tree (arborescence)	much harder; no constant-factor approximation known
Euclidean Steiner tree	NP-hard; PTAS exists; Steiner points meet at $120°$
Rectilinear Steiner tree	NP-hard; VLSI routing
Prize-collecting Steiner tree	NP-hard; 2-approximation
Node-weighted Steiner tree	$O(\log n)$-approximable

Steiner tree in a tree

When the graph is itself a tree, the minimum connected subgraph containing the terminals is simply the union of the paths between them — computable in $O(k\log n)$ with a virtual tree:

$\text{cost}={\sum }_{\text{virtual edges}}\text{path weight}.$

Equivalently, sort the terminals by DFS entry time and sum $\mathrm{dist}(t_i,t_{i+1})$ around the cycle, halved.

sort(terms.begin(), terms.end(), byTin);
long long total = 0;
for (int i = 0; i < k; i++)
    total += dist(terms[i], terms[(i + 1) % k]);
total /= 2;

Every edge of the Steiner tree is traversed exactly twice by that cyclic walk — a neat and frequently useful identity.

Where it appears

• Network design — connect a set of sites at minimum cable cost.
• VLSI routing — the rectilinear version.
• Phylogenetics — minimum evolution trees.
• Contest problems — usually with $k\le 10$ terminals, signalling Dreyfus-Wagner.

The recognition cue

When a problem says “connect these $k$ special vertices at minimum cost” and $k$ is suspiciously small ($\le 15$) while $n$ is large, it is a Steiner tree and the intended solution is the $O(3^{k}n)$ DP. That constraint pattern is the giveaway.

See also: Dreyfus-Wagner · Minimum Spanning Tree · Virtual Tree