vii. 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}.$

Dreyfus-Wagner — exact, $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$.

Base: $\mathrm{dp}[\{i\}][t_i]=0$ for each terminal $t_i$.

Two transitions:

1. Merge two sub-trees meeting at $v$: $\mathrm{dp}[\text{mask}][v]={\min }_{\varnothing \ne \text{sub}⊊\text{mask}}(\mathrm{dp}[\text{sub}][v]+\mathrm{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, seeded from every vertex with its current dp[mask][·] value: $\mathrm{dp}[\text{mask}][v]={\min }_u(\mathrm{dp}[\text{mask}][u]+w(u,v))$.

Answer: ${\min }_v\mathrm{dp}[\text{full}][v]$.

const ll INF = 1e18;
 
ll steiner(int n, const vector<vector<pair<int, ll>>>& adj, const vector<int>& term) {
    int k = term.size(), FULL = 1 << k;
    vector<vector<ll>> dp(FULL, vector<ll>(n, INF));
    for (int i = 0; i < k; i++) dp[1 << i][term[i]] = 0;
 
    for (int mask = 1; mask < FULL; mask++) {
        for (int v = 0; v < n; v++)                                   // 1. merge sub-trees at the same vertex
            for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask)
                if (dp[sub][v] < INF && dp[mask ^ sub][v] < INF)
                    dp[mask][v] = min(dp[mask][v], dp[sub][v] + dp[mask ^ sub][v]);
 
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;   // 2. Dijkstra to move the meeting point
        for (int v = 0; v < n; v++) if (dp[mask][v] < INF) pq.push({dp[mask][v], v});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dp[mask][u]) continue;
            for (auto [v, w] : adj[u]) if (d + w < dp[mask][v]) { dp[mask][v] = d + w; pq.push({dp[mask][v], v}); }
        }
    }
    return *min_element(dp[FULL - 1].begin(), dp[FULL - 1].end());
}

Complexity: subset enumeration ${\sum }_{\text{mask}}{2}^{|\text{mask}|}=3^k$, times $n$ vertices $\to O(3^{k}n)$; Dijkstra per mask, $2^k$ masks, $\to O(2^k(m+n\log n))$; space $O(2^{k}n)$. Practical up to $k\approx 12$-$15$ with $n$ in the thousands.

Proof: Dreyfus-Wagner is correct

Root any optimal Steiner tree $T$ for terminal set mask at an arbitrary vertex $v\in T$. Two cases, exhaustive:
(a) $v$ is a branching point (degree $\ge 2$ in $T$, with at least two of its subtrees each containing at least one terminal): removing $v$ splits $T$ into subtrees, and grouping them into any two non-empty sets partitions mask into sub and mask \ sub, each spanned by a smaller tree rooted at $v$ — exactly the merge transition, minimised over every such split.
(b) $v$ has only one subtree containing terminals (degree 1 in $T$, or a pass-through vertex with everything on one side): then $T$ restricted to that side, plus the edge from $v$ to its one neighbour $u$ on that side, is a smaller instance — exactly the grow transition, $\mathrm{dp}[\text{mask}][v]=\mathrm{dp}[\text{mask}][u]+w(u,v)$, and running Dijkstra from all vertices simultaneously finds the optimal choice of $u$ (and chains of such moves) in one pass per mask, since the grow step is literally shortest-path relaxation.
Every optimal tree falls into case (a) or (b) at any vertex it contains (in particular, at the root of whatever shape it has), so the DP’s two transitions, applied for every mask in increasing order of popcount, are exhaustive — and by induction on mask (both transitions only reference strictly smaller masks or the Dijkstra relaxation within the same mask, which itself only improves values monotonically to a fixed point), $\mathrm{dp}[\text{mask}][v]$ converges to the true optimum. $■$

Tested: steiner checked against brute force (enumerate every vertex subset containing all terminals, take the MST of the induced subgraph if connected, keep the minimum over all subsets) on small random graphs with up to 10 vertices and up to 4 terminals.

Approximation: the metric-closure MST — a 2-approximation

1. Compute all-pairs shortest paths among the terminals (one Dijkstra per terminal).
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.

// for each terminal t: dijkstra(t)                       // k runs, reusing an already-tested Dijkstra
// build the complete graph on terminals with dist[i][j]
// mst = kruskal(that graph)                               // reusing an already-tested Kruskal
// expand each MST edge into its shortest path

Proof: the metric-closure MST is a 2-approximation

Take the optimal Steiner tree $T^{\ast }$ (cost $\mathrm{OPT}$) and double every edge, giving an Eulerian multigraph (every vertex has even degree) of cost $2\mathrm{OPT}$ that is connected and spans all terminals (plus possibly Steiner vertices). An Eulerian circuit of this multigraph visits every terminal; shortcutting it — skip repeated and non-terminal vertices, keeping only the first visit to each terminal — gives a Hamiltonian cycle on the terminals of length $\le 2\mathrm{OPT}$ (shortcutting never increases length, by the triangle inequality on shortest-path distances). Dropping the single most expensive edge of that cycle gives a spanning path, hence a spanning tree, on the terminals of cost $\le 2\mathrm{OPT}$ — and the MST of the terminals’ metric closure is by definition no worse than any spanning tree on them, in particular this one. Finally, expanding each MST edge back into its shortest path gives an actual connected subgraph of the original graph spanning all terminals, of total cost equal to the terminal-MST’s cost (no further loss, since each edge’s weight in the metric closure already is the true shortest-path distance) — $\le 2\mathrm{OPT}$. $■$

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);
ll total = 0;
for (int i = 0; i < k; i++) total += dist(terms[i], terms[(i + 1) % k]);
total /= 2;

Proof: the cyclic-sum identity

The minimal connected subtree spanning the terminals (the “Steiner tree in a tree”) is exactly their virtual tree: the union of all pairwise paths between terminals, which is also the union of root-to-terminal paths pruned of any part not on the way to at least one terminal. Consider the terminals sorted by DFS entry time (tin) and connected cyclically $t_1\to t_2\to \cdots \to t_k\to t_1$: this cyclic sequence of paths together traverses every edge of the virtual tree exactly twice — once “going down and across” into a subtree in DFS order and once “coming back” when a later terminal’s path returns through it, which happens because consecutive terminals in tin-order are exactly the ones whose connecting path in the virtual tree enters and leaves each branch in a single down-up sweep (the same reasoning as an Euler tour of a tree traversing each edge exactly twice). So ${\sum }_i\mathrm{dist}(t_i,t_{i+1})$ counts every virtual-tree edge’s weight exactly twice, and halving gives the true cost. $■$

Tested: the cyclic-sum formula checked against brute-force search over all subsets of tree edges (keep the minimum-weight edge subset connecting all terminals) on random trees with up to 15 vertices and up to 6 terminals.

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.

Variants / Use Cases

• Steiner tree in a grid / on a plane — the geometric version (Euclidean Steiner tree) is also NP-hard, with a different $\sqrt{3}/2$ structure.
• Held-Karp — the same “DP over subsets of a small special set” pattern.
• Network design, VLSI routing, phylogenetics — where Steiner trees originate.