A Fast and Simple $(1+\epsilon )$-Approximation for Minimum Spanning Trees in Doubling Metrics

Abstract

The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a $(1+\epsilon )$-approximation to the MST of an $n$-point metric space $(X,\mathbf{d})$ of doubling dimension $\mathrm{ddim}$. In doubling metrics, previous deterministic algorithms incur a running time with dependence ${\epsilon }^{-O(\mathrm{ddim})}$. We give a deterministic algorithm that computes a $(1+\epsilon )$-approximation to MST in time $2^{O(\mathrm{ddim})}n(\log n+{\epsilon }^{-1}{\log }^4(1/\epsilon ))$. For bounded doubling dimension, this improves the previous dependence on $\epsilon$ from ${\epsilon }^{-O(\mathrm{ddim})}$ to essentially linear in ${\epsilon }^{-1}$. Moreover, as a special case, our result improves the previous best deterministic running time for bounded-dimensional Euclidean metrics due to Arya and Mount~[SODA'16] by almost a factor of ${\epsilon }^{-1}$. We also show that, unlike in bounded-dimensional Euclidean spaces, MSTs in bounded doubling metrics can have arbitrarily large maximum degree, while every doubling metric nevertheless admits a $(1+\epsilon )$-approximate MST of maximum degree $2^{O(\mathrm{ddim})}\log (1/\epsilon )$.

arXiv commentUpdated version with corrected citations