Planar Length-Constrained Minimum Spanning Trees

In length-constrained minimum spanning tree (MST) we are given an n-node graph G = (V, E) with edge weights w : E → Z ≥0 and edge lengths l : E → Z ≥0 along with a root node r ∈ V and a length constraint h ∈ Z ≥0 . Our goal is to output a spanning tree of minimum weight according to w in which every node is at distance at most h from r according to l.

We give a polynomial-time algorithm for planar graphs which, for any constant ϵ > 0, outputs an O log 1+ϵ n -approximate solution with every node at distance at most (1 + ϵ)h from r. Our algorithm is based on new length-constrained versions of classic planar separators and α-divisions which may be of independent interest. Additionally, our algorithm works for length-constrained Steiner tree and bounds the integrality gap of the natural linear program as O(log 2 n/ϵ), again with (1 + ϵ) slack in the length constraint. Complementing this, we show that any algorithm on general graphs for length-constrained MST in which nodes are at most 2h from r cannot achieve an approximation of O log 2-ϵ n for any constant ϵ > 0 under standard complexity assumptions; as such, our results separate the approximability of length-constrained MST in planar and general graphs.