Steiner tree with few terminals: the Dreyfus-Wagner subset DP, and the shortest-path MST heuristic's worst case

A town is laying fibre to join a few sites: here a school, a clinic, a library and a pool. Fibre runs under streets, and digging up each street has a cost. The fibre may pass any junction on the way, whether it is a site or not. Which streets should be dug so that every site is connected, at the lowest total cost?

The cheapest such set of streets is a tree, a minimum Steiner tree. With every junction a site, it is a minimum spanning tree, and with two sites it is a shortest path. In between, the problem is NP-hard. Choosing which other junctions to use is the hard part, and trying every set of them takes $2^{n - k}$ attempts for $n$ junctions and $k$ sites.

Few sites change that. A town may have thousands of junctions and only five sites, and dynamic programming over sets of sites rather than sets of junctions gives a running time that is exponential only in $k$ .

In code, junctions are numbered $0$ to $n - 1$ , a street is (u, v, cost), and sites is a list of junctions.

Background: Dynamic Programming II.

Part A: two junctions that are not sites

The cheapest connection costs 17:

Street	Cost
School 0 – junction 5	4
Clinic 1 – junction 5	6
junction 5 – junction 4	3
junction 4 – Pool 3	2
Pool 3 – Library 2	2

Junctions 4 and 5 are not sites, but routing through them saves money. The tree is unique: no other set of streets connects the four sites for 17 or less. Joining the sites by shortest paths between them costs 20 instead: School–Pool through junction 4 (9), Pool–Library (2) and the direct School–Clinic street (9). Its tree joins sites to sites, so it never looks for a junction where three routes could meet.

Part B: a wheel

Put the sites on a rim around a hub junction. Every site has a street to the hub costing $h$ , and neighbouring sites are joined by a rim street costing $r$ , a little less than $2 h$ . The shortest path between neighbouring sites is the rim street, so the shortcut builds its spanning tree from $k - 1$ rim streets and digs $(k - 1) r$ . The star through the hub costs $k h$ . With $k = 8$ , $h = 10$ and $r = 19$ , that is $133$ against $80$ , a ratio of $1.66$ . As $r$ approaches $2 h$ , the ratio approaches $2 - \frac{2}{k}$ .

Why never worse than twice. Walk round an optimal Steiner tree, using every street twice. The walk costs $2 \cdot OPT$ and visits every site. Between consecutive sites on the walk, the walk is at least as long as the shortest path, so those $k$ legs give a closed tour of the sites costing at most $2 \cdot OPT$ . Drop the longest leg and it is a spanning tree on the sites, so the minimum spanning tree costs at most $2 (1 - \frac{1}{k}) \cdot OPT$ . Digging the streets on its paths costs no more than that, since shared streets are dug once. Kou, Markowsky and Berman's version also re-runs a spanning tree on the dug streets and prunes leaves that are not sites. On the wheel it makes no difference.

Part C: dynamic programming over sets of sites

Let $T (S, v)$ be the cost of the cheapest tree that connects the sites in $S$ and the junction $v$ . For a single site $t$ , $T ({t}, v)$ is the shortest distance from $t$ to $v$ . For larger $S$ :

$T (S, v) = min ({min}_{\emptyset \neq A ⊊ S} T (A, v) + T (S ⧵ A, v), {min}_{u} T (S, u) + w (u, v))$

The answer is $T (all sites, t)$ for any site $t$ . Process the sets $S$ in increasing order. For each $S$ , first take every split at every $v$ , which uses only smaller sets. Then the second option is a shortest-path problem: run Dijkstra with $T (S, v)$ as the starting distances. Record which option won at each $(S, v)$ to recover the streets.

Running time. Each pair $A ⊊ S$ assigns every site to $A$ , to $S ⧵ A$ , or to neither, so there are at most $3^{k}$ pairs. The splits take $O (3^{k} n)$ time and the Dijkstra runs take $O (2^{k} m \log n)$ . For 8 sites and 60 junctions that is a few hundred thousand steps. Trying every set of junctions would take $2^{52}$ .

Part D: why the recurrence is right

Take an optimal tree for $(S, v)$ and hang it from $v$ . Every leaf is a site in $S$ or $v$ itself, since any other leaf could be cut off for free. If $v$ has two or more children, split the branches at $v$ into two nonempty groups. Each group contains a site, so it is a tree for $(A, v)$ , and the other group is a tree for $(S ⧵ A, v)$ , with $A$ a nonempty proper subset. Each part is at least as expensive as $T$ of its pair, so the split option is at most the optimum. If $v$ has one child $u$ , the tree minus the street $u$ – $v$ connects $S$ and $u$ , so it costs at least $T (S, u)$ , and the street option is at most the optimum. If $v$ is itself the only site in $S$ , it is the base case. Both options always describe real trees, so neither can go below the optimum. Induction on the size of the tree finishes the proof.

Going further

Faster in $k$ . Björklund, Husfeldt, Kaski and Koivisto replaced the $3^{k}$ with $2^{k}$ for small integer costs, using fast subset convolution. Nederlof then got the same in polynomial space.
Approximation. The best known approximation ratio is $\ln 4 + ε < 1.39$ (Byrka, Grandoni, Rothvoß and Sanità, by iterative randomized rounding of an LP; see Approximation Algorithms). No ratio better than $\frac{96}{95}$ is possible unless P = NP.
Geometry. Between points in the plane, with any point allowed as a junction, the extra points meet at 120°. The Euclidean Steiner tree problem has a polynomial-time approximation scheme.

References

S. E. Dreyfus, R. A. Wagner. The Steiner problem in graphs. Networks 1(3), 1971.
L. Kou, G. Markowsky, L. Berman. A fast algorithm for Steiner trees. Acta Informatica 15, 1981.
A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto. Fourier meets Möbius: fast subset convolution. Proceedings of STOC, 2007.
J. Nederlof. Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65(4), 2013.
J. Byrka, F. Grandoni, T. Rothvoß, L. Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM 60(1), 2013.
M. Chlebík, J. Chlebíková. The Steiner tree problem on graphs: inapproximability results. Theoretical Computer Science 406(3), 2008.

The Fibre Run

Try your rule first