Massively Parallel Minimum Spanning Tree in General Metric Spaces
Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Łącki, Vahab Mirrokni, Peilin Zhong · Society for Industrial and Applied Mathematics eBooks · 2025
We study the minimum spanning tree (MST) problem in the massively parallel computation (MPC) model. Our focus is particularly on the strictly sublinear regime of MPC where the space per machine is O (nδ ). Here n is the number of vertices and constant δ ∊ (0, 1) can be made arbitrarily small. The MST problem admits a simple and folklore O (log n )-round algorithm in the MPC model. When the weights can be arbitrary, this matches a conditional lower bound of Ω(log n ) which follows from a well-known 1vs2-Cycle conjecture. As such, much of the literature focuses on breaking the logarithmic barrier in more structured variants of the problem, such as when the vertices correspond to points in low- [2, STOC’14] or high-dimensional Euclidean spaces [28, SODA’24].