Simple Length-Constrained Minimum Spanning Trees

Abstract

In the length-constrained minimum spanning tree (MST) problem, we are given an $n$-node edge-weighted graph $G$ and a length constraint $h\ge 1$. Our goal is to find a spanning tree of $G$ whose diameter is at most $h$ with minimum weight. Prior work of Marathe et al.\ gave a poly-time algorithm which repeatedly computes maximum cardinality matchings of minimum weight to output a spanning tree whose weight is $O(\log n)$-approximate with diameter $O(\log n)\cdot h$. In this work, we show that a simple random sampling approach recovers the results of Marathe et al. -- no computation of min-weight max-matchings needed! Furthermore, the simplicity of our approach allows us to tradeoff between the approximation factor and the loss in diameter: we show that for any $\hat{I}\mu \ge 1/\mathrm{poly}(n)$, one can output a spanning tree whose weight is $O(n^{\hat{I}}\mu /\hat{I}\mu )$-approximate with diameter $O(1/\hat{I}\mu )\cdot h$ with high probability in poly-time. This immediately gives the first poly-time $\mathrm{poly}(\log n)$-approximation for length-constrained MST whose loss in diameter is $o(\log n)$.

Added Ravi ack