Faster parallel methods for approximating minimum spanning trees
Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces
Data Structures and AlgorithmsComputational GeometryDistributed, Parallel, and Cluster Computing
Summary
Finding the shortest way to connect all points in a network is a common problem called the minimum spanning tree (MST). The authors developed new faster ways to find approximate MSTs using many computers working together in parallel. They improved the speed and efficiency for different types of spaces, including general distances, points in Euclidean space, and spaces with a structure called doubling dimension. This means it’s now faster to get very close solutions to the MST problem using large-scale parallel computing.
What this means in practice
- •For big data engineers: Speed up clustering and network design tasks in distributed systems by rapidly approximating minimum spanning trees at large scale.
- •For geospatial analysts: Process large geographic datasets efficiently when computing network connections or minimal road networks in high-dimensional Euclidean spaces.
Authors
Eunjin Oh, Hyeonjun Shin
Abstract
We develop a unified algorithmic framework for computing approximate minimum spanning trees (MSTs) in metric spaces in the fully scalable Massively Parallel Computation (MPC) model. Using this framework, we obtain the following results for any fixed constant $σ\in(0,1)$: - General metrics: Given all pairwise distances, we compute a $(1+\varepsilon)$-approximate MST in $O(\log(1/\varepsilon))$ rounds using $n^σ$ local space per machine and $\widetilde{O}(n^2)$ total space. - Euclidean spaces: Given $n$ points in $\mathbb{R}^d$, we compute an $O(1/σ^4)$-approximate MST in $O(1)$ rounds using $(nd)^σ$ local space per machine and $O(nd+n^{1+σ})$ total space. - Doubling metrics: Given $n$ points in a metric of doubling dimension $\mathrm{ddim}=O(σ\log n)$, we compute an $O(1/σ)$-approximate MST in $O(\mathrm{ddim}/σ^4)$ rounds using $n^σ$ local space per machine and $\widetilde{O}(n^{1+σ})\cdot 2^{O(\mathrm{ddim})}$ total space. For any fixed constant $\varepsilon\in(0,1)$, these results give the first constant-round MPC algorithms achieving $(1+\varepsilon)$-approximation in general metrics and $O(1)$-approximation in a high-dimensional Euclidean space, respectively. They improve upon the $O(\log\log n+\log(1/\varepsilon))$-round algorithm for general metrics [SODA'25] and the $O(\log\log n\cdot\log\log\log n)$-round algorithm for Euclidean spaces [SODA'24], respectively. Moreover, our round complexity for general metrics is asymptotically optimal in its dependence on $\varepsilon$, matching the $Ω(\log(1/\varepsilon))$ lower bound of [SODA'25] under the 1-vs-2-cycles conjecture. Our result also answers an open question raised by [STOC'23].