Simple Length-Constrained Minimum Spanning Trees
<|reference_start|>Simple Length-Constrained Minimum Spanning Trees: In the length-constrained minimum spanning tree (MST) problem, we are given an $n$-node edge-weighted graph $G$ and a length constraint $h \geq 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 $\epsilon \geq 1/\operatorname{poly}(n)$, one can output a spanning tree whose weight is $O(n^\epsilon / \epsilon)$-approximate with diameter $O(1/\epsilon)\cdot h$ with high probability in poly-time. This immediately gives the first poly-time $\operatorname{poly}(\log n)$-approximation for length-constrained MST whose loss in diameter is $o(\log n)$.<|reference_end|>
@article{hershkowitz2024simple,
    title={Simple Length-Constrained Minimum Spanning Trees},
    author={D Ellis Hershkowitz and Richard Z Huang},
    journal={arXiv preprint arXiv:2410.08170},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.08170},
    primaryClass={cs.DS}
}