{"ID":2857330,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.09002","arxiv_id":"2510.09002","title":"Planar Length-Constrained Minimum Spanning Trees","abstract":"In length-constrained minimum spanning tree (MST) we are given an $n$-node graph $G = (V,E)$ with edge weights $w : E \\to \\mathbb{Z}_{\\geq 0}$ and edge lengths $l: E \\to \\mathbb{Z}_{\\geq 0}$ along with a root node $r \\in V$ and a length-constraint $h \\in \\mathbb{Z}_{\\geq 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 $ε\u003e 0$, outputs an $O\\left(\\log^{1+ε} n\\right)$-approximate solution with every node at distance at most $(1+ε)h$ from $r$ for any constant $ε\u003e 0$. Our algorithm is based on new length-constrained versions of classic planar separators which may be of independent interest. Additionally, our algorithm works for length-constrained Steiner tree. 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\\left(\\log ^{2-ε} n\\right)$ for any constant $ε\u003e 0$ under standard complexity assumptions; as such, our results separate the approximability of length-constrained MST in planar and general graphs.","short_abstract":"In length-constrained minimum spanning tree (MST) we are given an $n$-node graph $G = (V,E)$ with edge weights $w : E \\to \\mathbb{Z}_{\\geq 0}$ and edge lengths $l: E \\to \\mathbb{Z}_{\\geq 0}$ along with a root node $r \\in V$ and a length-constraint $h \\in \\mathbb{Z}_{\\geq 0}$. Our goal is to output a spanning tree of mi...","url_abs":"https://arxiv.org/abs/2510.09002","url_pdf":"https://arxiv.org/pdf/2510.09002v2","authors":"[\"D Ellis Hershkowitz\",\"Richard Z Huang\"]","published":"2025-10-10T04:58:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}