Given an n‑node graph G=(V,E) with edge weights w:E\to\mathbb{Z}{\geq 0}, edge lengths l:E\to\mathbb{Z}{\geq 0}, a root r\in V and a length bound h\in\mathbb{Z}_{\geq 0}, the length‑constrained minimum spanning tree problem asks for a spanning tree of minimum total weight such that every vertex is at distance at most h from r measured by l. For planar graphs we present a polynomial‑time algorithm: for any constant \epsilon>0 the algorithm returns a tree whose weight is at most O(\log^{1+\epsilon} n) times optimal and whose root‑to‑vertex distances are bounded by (1+\epsilon)h. The method relies on new length‑constrained planar separators, which may be of independent interest. The same technique extends to the length‑constrained Steiner tree problem and yields an integrality‑gap bound of O(\log^3 n / \epsilon) for the natural LP, again with a (1+\epsilon) slack in the length constraint. In contrast, we show that on general graphs, even if vertices are required to be within 2h of the root, no algorithm can achieve an O(\log^{2-\epsilon} n) approximation under standard complexity assumptions. Thus the approximability of length‑constrained MST separates planar from general graphs.
Review