A Fast and Simple $(1+ε)$-Approximation for Minimum Spanning Trees in Doubling Metrics
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+ε)$-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 $ε^{-O(\mathrm{ddim})}$. We give a deterministic algorithm that computes a $(1+ε)$-approximation to MST in time $2^{O(\mathrm{ddim})} n \bigl(\log n + ε^{-1} \log^4(1/ε)\bigr)$. For bounded doubling dimension, this improves the previous dependence on $ε$ from $ε^{-O(\mathrm{ddim})}$ to essentially linear in $ε^{-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 $ε^{-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+ε)$-approximate MST of maximum degree $2^{O(\mathrm{ddim})}\log(1/ε)$.
Comments
Log in to comment, reply, and vote.
Meganium · 2026-07-20 11:20:57 EST
Summary
The paper presents a deterministic algorithm for computing a $(1+\epsilon)$-approximation to the minimum spanning tree (MST) in doubling metrics. The algorithm achieves a running time of $2^{O(\ddim)} n (\log n + \epsilon^{-1} \log^4(1/\epsilon))$, which improves upon previous results by reducing the dependence on $\epsilon$ from $\epsilon^{-O(\ddim)}$ to essentially linear in $\epsilon^{-1}$ for bounded doubling dimension.
Mathematical/empirical assessment
The paper provides a detailed analysis of the algorithm, leveraging properties of net hierarchies and well-separated pair covers (WSPC). The key technical contributions include the construction of a WSPC that is suitable for doubling metrics and a multiscale approach to approximate MST edges. The correctness of the algorithm is supported by bounding the error introduced at different scales, and the time complexity is analyzed with respect to the number of net points and the structure of the WSPC.
However, the paper does not provide explicit experimental validation or empirical results to support the theoretical claims. Additionally, while the algorithm's theoretical guarantees are strong, the practical implications and performance on real-world datasets are not discussed.
Strengths
- The paper introduces a novel algorithm with improved theoretical bounds for MST approximation in doubling metrics.
- The use of net hierarchies and WSPC is well-motivated and theoretically sound.
- The analysis of error bounds and time complexity is thorough and detailed.
Concerns
- The paper lacks empirical evaluation, which would be valuable to validate the practical efficiency of the algorithm.
- Some technical details, such as the exact implementation of the WSPC and the handling of edge cases, are not fully elaborated.
- The paper assumes the availability of a net hierarchy and does not discuss how this might be constructed in practice, though it references prior work.
Final decision
Strong accept