Chapter XVI Steiner Tree

The cheapest connection

Connect these dots cheaply, but you can use other dots as relay points if it helps.

The Steiner tree in Graphs problem takes a weighted graph and a terminal subset, and asks for the minimum-weight subtree containing every terminal:

T^{'} subtree of G, T \subseteq V (T^{'}) min e \in E (T^{'}) \sum w (e) . (1)

Non-terminals may be included as connecting Steiner points — that's the freedom that makes (1) more powerful than the spanning tree. NP-hard (Karp).

When every vertex is a terminal, the problem collapses:

T = V ⟹ (1) is the minimum spanning tree, which is in P. (2)

So the hardness comes entirely from the choice of which non-terminals to include. The 2-approximation via metric closure is the workhorse heuristic; the best polynomial-time approximation ratio known is roughly 1.39 (Byrka et al.).

Figures, in plain terms

(1)

min picks the choice that minimizes the expression after.

Two conditions sit under the min: T' subtree of G says T' is a connected, cycle-free piece of G; T ⊆ V(T') says the terminals T are all included as vertices of that subtree. The notation V(T') extracts the vertex set of the subtree T'.

The thing being minimized is Σ over edges of T' of w(e) — the big-Σ (capital sigma) is summation, the same shape as big-AND from chapter 1 but for adding numbers.

So the figure says: among every connected, cycle-free subgraph that includes all terminals, find the one whose edges total the least weight.

Non-terminal vertices may or may not be included — they're free to use as connecting waypoints (Steiner points), or skipped if going around is cheaper.

(2)

T = V is the special case where every vertex is a terminal. No optional Steiner points — every dot must be in the tree.

⟹ is the implication arrow from chapter 10.

MST in P says the resulting problem (connecting every vertex with minimum-weight edges) is the minimum spanning tree, solvable in polynomial time by Kruskal or Prim.

So Steiner tree's hardness comes entirely from the optional non-terminal vertices. Strip that choice away and the problem collapses to a textbook polynomial-time algorithm.