Tight Bounds for $(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 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 )$-approximate MST in time $$O_{\mathrm{ddim}}\left(n\log n+\min \left\{n^2,\frac{n}{\epsilon }\log (1/\epsilon )\right\}\right)$$ in the standard real RAM model with a unit-cost exact-distance oracle. For bounded doubling dimension, this improves the previous dependence on $\epsilon$ to essentially linear in ${\epsilon }^{-1}$. We complement this algorithm with a lower bound of $$\Omega \left(n\log n+\min \left\{n^2,\frac{n}{\epsilon }\log (1/\epsilon )\right\}\right)$$ on running time in the same model, already for metrics of doubling dimension at most seven, showing that our running time is essentially tight. For points in ${\mathbb{R}}^d$ with $d=O(1)$, exploiting Euclidean geometry allows us to further improve the dependence on $\epsilon$. We obtain a $(1+\epsilon )$-approximate MST in expected time $$O_d\left(n\log n+\min \left\{n^2,\frac{n}{{\epsilon }^{1-{\beta }_d}}{\log }^{1-{\beta }_d}(1/\epsilon )\right\}\right)$$ for some ${\beta }_d=\Theta (1/d)$, improving the accuracy-dependent term $n{\epsilon }^{-2}{\log }^2(1/\epsilon )$ of Arya and Mount [SODA'16].

arXiv commentImproved running time for MST in doubling metrics, new upper bound for MST in Euclidean spaces, and lower bounds for MST in doubling metrics