Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces

Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces

arXiv:2611.06092v1 [cs.DS] 4 Nov 2026

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 σ ∈ (0, 1): • General metrics. Given all pairwise distances, we compute a (1 + ε)-approximate MST e 2 ) total space. in O(log(1/ε)) rounds using nσ local space per machine and O(n • Euclidean spaces. Given n points in Rd , we compute an O(1/σ 4 )-approximate MST in O(1) rounds using (nd)σ local space per machine and O(nd + n1+σ ) total space. • Doubling metrics. Given n points in a metric of doubling dimension ddim = O(σ log n), we compute an O(1/σ)-approximate MST in O(ddim/σ 4 ) rounds using nσ local space per e 1+σ ) · 2O(ddim) total space. machine and O(n For any fixed constant ε ∈ (0, 1), these results give the first constant-round MPC algorithms achieving (1+ε)-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/ε))-round algorithm for general metrics [SODA’25] and the O(log log n · 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 ε, matching the Ω(log(1/ε)) lower bound of [SODA’25] under the 1-vs-2-cycles conjecture. Our result also answers an open question raised by [STOC’23].

∗ POSTECH, South Korea. Email: eunjin.oh@postech.ac.kr. This work is supported by Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS2024-00440239, Sublinear Scalable Algorithms for Large-Scale Data Analysis) and the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00358505). † POSTECH, South Korea. Email: hyeonjun.shin@postech.ac.kr.

Contents 1 Introduction

1

2 Preliminaries

5

3 Technical overview 6 3.1 Forest cutting (for the first iteration) . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Forest merging (for the first iteration) . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Completing the algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 Key ingredients: Truncated Prim and forest cutting 4.1 Truncated Prim’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Forest cutting algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Step 1. Giving orientations to edges . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Step 2. Cutting additional edges from the oriented forest . . . . . . . . . . . 4.2.3 MPC implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12 12 13 15 16 18

5 (1 + ε)-approximate MST in general metrics 5.1 Overall algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Proof of Lemma 5.2: Computing a light contraction . . . . . . . . . . . . . . . . . . 5.2.1 Forest cutting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Forest merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 20 21 21 23

6 Constant approximate MST in Euclidean and doubling spaces 6.1 Overall algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Proof of Lemma 6.2 and Lemma 6.3: Computing a light partition . . . . . . . . . . . 6.2.1 Forest cutting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Forest merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.3 MPC implementation using consistent hashing . . . . . . . . . . . . . . . . .

25 25 27 28 29 30

7 Approximate TSP in constant rounds

32

8 Conclusion

34

A Getting rid of the assumption on bounded spread 40 A.1 Euclidean space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 A.2 Doubling space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 B Proof of Theorem 1.3 assuming Lemma 6.3

41

C Proof of Lemma 6.5

42

1

Introduction

In this paper, we study the minimum spanning tree (MST) problem in metric spaces, which is one of the fundamental problems in computer science. Given a set of points and their pairwise distances, the goal is to compute a spanning tree of minimum total weight in the complete graph on the point set, where the weight of each edge is the distance between its endpoints. The MST problem has been extensively studied, giving rise to a rich body of algorithmic techniques. A central application is hierarchical clustering: removing the edges of an MST in decreasing order of weight progressively partitions the point set into clusters [MRG10, YV18]. In particular, MST-based clustering has been used to identify structures in astronomical data [MRG10, ARD+ 14] and to cluster high-dimensional datasets in machine learning [LRN09]. MSTs also find applications in biology [TCG+ 14, YTW+ 20, SGM+ 24] as well as in representation learning [HGNK20, MHRB20, MLKO25]. Such applications often involve processing large data sets. This motivates the use of modern distributed computing frameworks such as MapReduce, Spark, Hadoop, and Dryad [DG08, DG04, Whi12, IBY+ 07]. Although their implementations differ, these systems must coordinate computation across many machines, and the resulting communication overhead can significantly affect algorithmic efficiency. The Massively Parallel Computation (MPC) model, introduced in [KSV10], has become a central theoretical framework for capturing the algorithmic challenges in these systems. Over the past decade, various algorithmic problems including the MST problem have been extensively studied in the MPC model [ABJ+ 25, ASW19, BFO+ 26, CC23, Gha19, YV18]. In the MPC model, the input of N words is distributed across m machines, each with s words of local memory, giving a total memory of m · s words. Computation proceeds in synchronous rounds of local computation and communication. In each round, each machine can perform unrestricted local computation within its memory bound, and then send and receive O(s) words. The primary complexity measures of an MPC algorithm are its round complexity, local memory s, and the total space m · s. In this work, we consider the fully scalable regime where s = N σ for an arbitrary fixed constant σ ∈ (0, 1). Our goal is to minimize the number of rounds, ideally achieving O(1) rounds, while keeping the total space as small as possible. We focus on the metric MST problem in the fully scalable MPC model. Since a metric induces a complete edge-weighted graph, a natural approach is to apply MPC algorithms for MSTs in general graphs. For general edge-weighted graphs, an exact MST can be computed in O(log n) rounds in the fully scalable regime [ASS+ 18, BDE+ 19, CC23]. However, under the 1-vs-2-cycles conjecture, even computing an approximate MST in a general edge-weighted graph requires Ω(log n) rounds.1 This barrier has motivated extensive work on MPC algorithms for MSTs in more structured settings, particularly metric spaces, including Euclidean and doubling metrics [ANOY14, GWZ25, CJLW22, ABJ+ 25, JMNZ24]. A natural question in this direction is whether approximate MSTs can be computed in o(log n) rounds by exploiting metric structure. Although Euclidean MST is a special case of metric MST, their input representations differ significantly in the MPC model. Our goal is to keep the total space close to linear in the input size. In the general metric setting, all pairwise distances are explicitly given, resulting in an input size of N = Θ(n2 ). In contrast, in the Euclidean setting, the input consists of the coordinates of n points in Rd , requiring only Θ(nd) words. In the doubling metric setting, we assume that each point has an O(1)-word representation from which pairwise distances can be computed locally, resulting in an input size of Θ(n). Therefore, directly applying MPC algorithms for general metrics to Euclidean and doubling metric spaces may not achieve the desired total space complexity. 1 Distinguishing a single cycle on n vertices from two disjoint cycles on n/2 vertices each is conjectured to require Ω(log n) rounds in the fully scalable regime. Several conditional hardness results rely on this conjecture [NS22].

1

Previous work. We review the best-known prior MPC results for MSTs in various metric settings. In the following, we sometimes treat σ and ε as fixed constants. Instead, we indicate any hidden dependence on these parameters by subscripts in the O(·) notation. For low-dimensional Euclidean spaces, Andoni, Nikolov, Onak, and Yaroslavtsev [ANOY14] presented a randomized Oσ (1)-round MPC algorithm that constructs a (1+ε)-approximate MST in expectation using linear total space. This result also extends to doubling metrics without increasing the round complexity and the total space complexity. Although they state their results for the O(1)-dimensional case, their analysis √ also applies to higher dimensions: d = Oε (σ log n/ log log n) in Euclidean spaces and ddim = Oε ( σ log n) in doubling metrics, using O(nσ ) local space.2 As long as the dimensions are within these ranges, the dependence on the dimension in the round complexity and the total space complexity is linear. For high-dimensional Euclidean spaces, [CCAJ+ 23] presented an MPC algorithm that estimates the MST cost within a factor of (1 + ε) in Oσ,ε (1) rounds using O(nd) total space. However, their algorithm does not construct an actual spanning tree. In fact, constructing a constant-factor approximate MST in high-dimensional Euclidean spaces was more challenging; previously, it could be constructed in Oσ (log n) rounds by constructing a sparse Euclidean spanner and then applying an MPC algorithm for MSTs in general graphs. Jayaram, Mirrokni, Narayanan, and Zhong [JMNZ24] broke this O(log n) barrier by presenting an Oσ (log log n · log log log n)-round MPC algorithm that constructs an Oσ (1)-approximate MST using O(nd + n1+σ ) total space. For general metric spaces, [ABJ+ 25] gave a randomized Oσ (log(1/ε) + log log n)-round MPC e 2 ) total space. The total space is algorithm that constructs a (1 + ε)-approximate MST using O(n thus near-linear in the input size. Under the 1-vs-2-cycles conjecture, they also proved that any MPC algorithm with n1−Ω(1) local space and polynomial total space requires Ω(log(1/ε)) rounds to construct a (1 + ε)-approximate MST in a general metric space, for 1/n ≤ ε ≤ 1. Despite recent progress on MPC algorithms for metric MSTs, the best-known algorithms for constructing approximate MSTs in general metrics and high-dimensional Euclidean spaces still require a super-constant number of rounds for fixed ε. This raises the following question, which was also explicitly posed in [CCAJ+ 23, JJLW26]: Can one construct approximate MSTs in both general metric spaces and high-dimensional Euclidean spaces in O(1) rounds in the fully scalable MPC model, while maintaining the approximation ratios of the previous best-known algorithms? Our contributions. We answer this question affirmatively by developing a unified algorithmic framework for constructing approximate MSTs in general metric spaces and high-dimensional Euclidean spaces. In particular, we improve the round complexities of the algorithms of [JMNZ24] and of [ABJ+ 25] without increasing the total space complexities and the approximation ratios. This framework also applies to doubling metric spaces. Specifically, we prove the following theorems. Theorem 1.1. Fix two parameters σ ∈ (0, 1) and ε ∈ (0, 1). There is an O(log(1/(σε))/σ 2 )-round randomized MPC algorithm that, given all pairwise distances of an n-point metric (X, dist), returns a spanning tree of X whose total weight is at most (1 + ε) times the weight of a minimum spanning tree of (X, dist). The algorithm succeeds with probability at least 1 − n−Ω(1) and uses nσ local space e 2 ) total space. per machine and O(n 2 For the dimension bounds, see Theorems 2.1 and 3.1 for Euclidean spaces and Theorem 6.6 for doubling metrics in [ANOY14].

2

Metric General

Dimension

Rounds

Total space

Tree?

Source

1+ε

Oσ (log(1/ε) + log log n)

e 2) O(n

✓

[ABJ+ 25]

1+ε

Oσ (log(1/ε))

e 2) O(n

✓

Theorem 1.1

1+ε

Oσ (1)

Oσ (n)

✓

[ANOY14]

1+ε

Oσ ((1/ε) · log(1/ε))

e O(dn)

—

[CCAJ+ 23]

Oσ (1)

Oσ (log log n · log log log n)

O(nd + n1+σ )

✓

[JMNZ24]

Oσ (1)

Oσ (1)

O(nd + n1+σ )

✓

Theorem 1.2

√ ddim = Oε ( σ log n)

1+ε

Oσ (ddim)

Oσ (n · ddim)

✓

[ANOY14]

ddim = O(σ log n)

Oσ (1)

Oσ (ddim)

e 1+σ ) · 2O(ddim) O(n

✓

Theorem 1.3

— d = O(1)

Euclidean arbitrary d

Doubling

Approximation

Table 1:

Comparison of previous and our results. The local space per machine is nσ for general and doubling metrics and (nd)σ for Euclidean spaces, except that [CCAJ+ 23] uses dO(1) nσ local space. The sixth column with label “Tree?” indicates whether the algorithms return an actual spanning tree.

Theorem 1.2. Fix a constant σ ∈ (0, 1). There is an O(1/σ 2 )-round randomized MPC algorithm that, given a set P of n points in Rd , returns a spanning tree of P whose total weight is O(1/σ 4 ) times the weight of a minimum spanning tree of P . The algorithm succeeds with probability at least 1 − n−Ω(1) and uses (dn)σ local space per machine and O(nd + n1+σ ) total space. Theorem 1.3. Fix a constant σ ∈ (0, 1). There is an O(ddim/σ 4 )-round randomized MPC algorithm that, given a set P of n points in a metric space with doubling dimension ddim satisfying σ log n ≥ Ω(ddim), returns a spanning tree of P whose total weight is O(1/σ) times the weight of a minimum spanning tree of P . The algorithm succeeds with probability at least 1 − n−Ω(1) and uses e 1+σ ) · 2O(ddim) total space. nσ local space per machine and O(n Table 1 compares our algorithms with previous MPC algorithms for metric MSTs. For general metrics, we remove the additive Oσ (log log n) term in the round complexity of Azarmehr, Behnezhad, Jayaram, Łącki, Mirrokni, and Zhong [ABJ+ 25]. For high-dimensional Euclidean spaces, we improve the Oσ (log log n · log log log n)-round bound of Jayaram, Mirrokni, Narayanan, and√Zhong [JMNZ24] to Oσ (1) rounds. For doubling metrics, we extend the dimension range from Oε ( σ log n) in [ANOY14] to O(σ log n) while retaining Oσ (ddim) rounds. On the other hand, the approximation ratio becomes Oσ (1) while the approximation ratio of [ANOY14] is 1 + ε. As an application, our algorithms also yield MPC algorithms for the traveling salesman problem (TSP) in metric spaces. Doubling the weight of an approximate MST immediately gives an estimate of the optimal TSP cost, with twice the approximation factor. We show how to compute an approximate TSP tour itself. The standard method doubles every tree edge, computes an Euler tour, and shortcuts repeated visits to each point. However, under the 1-vs-2-cycles conjecture, computing the traversal order of an arbitrary tree given only its edges requires Ω(log n) rounds in the worst case in the fully scalable MPC model [JMNZ24]. We instead use a hierarchical structure of an approximate MST constructed during our MST algorithms to compute an Euler tour. This gives a (2 + ε)-approximation in general metric spaces and an Oσ (1)-approximation in Euclidean and doubling metric spaces, with high probability, without asymptotically increasing the round complexity, local space per machine, or total space of the corresponding MST algorithms. For details, see Section 7. 3

Estimating the cost vs. Computing an actual tree. Beyond estimating the MST cost, our main contribution is to improve the round complexity for constructing approximate MSTs themselves in the MPC model. This distinction matters not only from an algorithmic perspective but also in applications that require the connections between points. For example, in hierarchical clustering, one can remove the edges of an MST (or an approximate MST) in decreasing order of weight to obtain a nested sequence of partitions of the points. The connected components after each removal determine which points belong to the same cluster at that level. An estimate of the MST cost alone does not identify the edges or the resulting clusters. Another example is network design. The edges of a spanning tree specify which pairs of sites to connect; an approximate MST provides such connections with a total weight within a provable factor of the minimum. Conceptual contribution and main insights. A by-now-standard framework for estimating MST costs in sublinear models uses threshold graphs [CRT05]. For a threshold t, two points are adjacent in the threshold graph if their distance is at most t. By Kruskal’s algorithm, the number of MST edges longer than t is exactly one less than the number of connected components of the threshold graph at t. Thus, by counting the connected components at thresholds 1, (1 + ε), (1 + ε)2 , . . ., we can determine how many MST edges have lengths between consecutive thresholds and use this information to estimate the MST cost. This approach has led to efficient algorithms in several sublinear models [CRT05, CS09, CEF+ 05, DMO+ 25, CCAJ+ 23]. However, constructing an approximate MST is more challenging, since knowing the number of MST edges at each scale does not tell us which edges to include in the tree. Previous MPC algorithms for computing an approximate MST in metrics addressed this issue in this framework, but required a super-constant number of rounds [ABJ+ 25, JMNZ24]. We instead take a different approach based on Prim’s algorithm, inspired by [PvdB25, BDE+ 20]. In particular, [BDE+ 20] presented an O(1)-round adaptive MPC algorithm for computing an exact MST in a general graph based on Prim’s algorithm.3 This suggests a natural question: Can a Primbased approach also be used to construct an approximate MST in fewer MPC rounds? We run truncated executions of Prim in parallel on small neighborhoods that fit on individual machines. The resulting forest serves as a building block for our algorithm, whose main insights are as follows. • By choosing appropriate stopping conditions, each truncated execution selects only edges belonging to a common MST of the input. Their union therefore forms a forest. However, this forest may contain very large trees or too many small trees. • Large trees may span many machines, making it difficult to identify their connected components. We overcome this problem by cutting edges so that each point can identify the root of its resulting tree locally. • Even when the forest contains many small trees, we can use sampling to merge them into fewer trees. The stopping conditions of the Prim executions allow us to bound the expected total weight of the edges added by this procedure by a constant factor of the MST cost. For general metrics, we contract each tree into a single vertex and repeat the procedure. For Euclidean and doubling metrics, we instead retain one representative point per tree and repeat the procedure. In each phase, the number of vertices decreases by a factor of nΩ(σ) , and thus the algorithm terminates in O(1/σ) phases. A more detailed technical overview can be found in Section 3. 3

In the adaptive MPC model, a machine may make adaptive queries to a distributed hash table within a round, whereas communication in the MPC model is received in the next round. Their algorithm uses stopping conditions different from ours and contracts the trees of an auxiliary forest in O(1) AMPC rounds. Thus, it does not face the difficulty of identifying long trees that arises in our MPC setting.

4

2

Preliminaries

Let (X, dist) be a metric space on n points. The doubling dimension of (X, dist) is defined as the smallest value d such that every ball of radius r > 0 can be covered by at most 2d balls of radius r/2. It is known that the doubling dimension of Rd is Θ(d). When we speak about doubling metrics, we treat the doubling dimension ddim as a parameter; we do not assume that it is constant. For two nonempty subsets A, B ⊆ X, we define dist(A, B)= mina∈A,b∈B dist(a, b). Note that these distances need not satisfy the triangle inequality. We sometimes consider the metric (X, dist) as the complete graph with vertex set X and edge weight dist(·, ·). For a graph G = (V, E), we use V (G) and E(G) to denote the vertex set and the edge set of G, respectively. For a finite set Z, we use |Z| to denote the cardinality of Z. We sometimes abuse notation and use |G| to denote the total number of edges and vertices of G. We use OPT(X) to denote the MST cost of X. If it is clear from context, we simply write OPT. Throughout this paper, we assume that the edge weights are pairwise distinct, and therefore the MST is unique. If this is not the case, we can break ties using the lexicographical ordering of the endpoints of the edges. For λ > 0, the exponential distribution with rate λ, denoted by Exp(λ), is the distribution on [0, ∞) with probability density function f (t) = λe−λt for t ≥ 0. In this paper, we use the following standard property of exponential random variables. If X1 , . . . , Xm are independent random variables with Xi ∼ Exp(λi ), then for any A ⊆ {1, . . . , m}, the probability that arg min1≤i≤m Xi P P belongs to A is i∈A λi / m i=1 λi . MPC primitives. The following standard primitives can be done in O(1/σ) MPC rounds using nσ local space per machine and total space linear in the number of input and output records [Goo99, GSZ11]. Here, each record consists of O(1) words, and the number of input and output records is polynomial in n. • Sorting: Given records with comparable keys distributed across machines, we can sort the records by their keys and assign each record its rank in the sorted order. If the records are partitioned into sets S1 , . . . , Sk and each record in Sj is stored together with j, we can also compute its rank within Sj according to the same keys. Each rank can be stored together with its record on the machine that originally stores the record. • PrefixSum: Given a sequence v1 , . . . , vt distributed across machines, with each value vi P stored together with its index i, we can compute the prefix sum ij=1 vj or the prefix minimum min1≤j≤i vj for every i and store the result together with vi on its original machine. For a prefix minimum, we can also return an index attaining the minimum together with any O(1)word data associated with that entry. We can also process multiple sequences separately if each value is stored together with the index of its sequence and its position within that sequence. • Aggregation: Given records (k, v) distributed across machines, we can compute the sum, minimum, or maximum of the values v for each key k, even if records with the same key are stored on different machines. The result can be stored together with every record with that key. We can also count the number of records with each key. • Broadcasting: Given records (k, v) with one value v for each key k, and requests (k, i) distributed across machines, where i is a machine ID, we can send a copy of v to machine i for every request (k, i). We assume that each machine is the destination of at most O(nσ ) requests. All copies are included in the output size.

5

Consistent hashing. For the Euclidean and the doubling metric cases, we need to compute a small neighborhood of each point in parallel. For this, we use (geometric) consistent hashing [JLN+ 05]. A consistent hash φ : X → I for an index set I induces a partition of X into clusters of diameter at most ∆ such that for any two points x, y ∈ X, they are contained in the same cluster if and only if φ(x) = φ(y). Definition 2.1 ([CJK+ 22, Definition 1.6], [BFO+ 26, Definition 1]). Let (X, dist) be a metric space, I an index set, and ∆ > 0. For a distribution H over mappings X → I, let supp(H) denote the set of mappings that can be sampled from H. A random mapping φ ∼ H is a (Γ, Λ)-hash with diameter bound ∆ if: 1. [Diameter] every cluster of every φ ∈ supp(H) has diameter at most ∆. 2. [Consistency] for every X ′ ⊆ X with diameter at most ∆/Γ, we have Eφ∼H [|φ(X ′ )|] ≤ Λ. For Euclidean spaces, Czumaj, Filtser, Jiang, Krauthgamer, Veselý, and Yang [CFJ+ 23, CJK+ 22] showed that there is a deterministic hash φ : Rd → Rd whose description requires poly(d) space. Following [CGJ+ 24], we use this hash φ so that each machine can evaluate it locally without communication. The geometric aggregation algorithm in [CGJ+ 24] provides the following lemma. Lemma 2.2 ([CGJ+ 24]). Let σ ∈ (0, 1) be a fixed constant, and let P ⊆ Rd be a set of n points with d = O(log n). For any ∆ > 0, there exists a (Γ, nσ/2 )-hash φ with diameter bound ∆ and Γ = O(1/σ), whose description and evaluation require poly(d) space. Given the same hash on every machine, we can compute the sum, minimum, or maximum of values associated with the points in P ∩ φ−1 (φ(B(x, ∆/(2Γ)))) for every x ∈ P in O(1/σ) rounds using nσ local space per machine and O(nd + n1+σ ) total space. For doubling metrics, Bhore, Filtser, Oh, Shin, and Singh [BFO+ 26] construct a randomized consistent hash from the input points, together with approximate neighborhood hash pairs. For Γ > 0 and a hash φ : P → I with diameter bound ∆, a set Peφ ⊆ P × I is a set of approximate neighborhood hash pairs if (x, φ(y)) ∈ Peφ whenever x, y ∈ P and dist(x, y) ≤ ∆/Γ, and φ−1 (q) ⊆ S B(x, 2∆) for every (x, q) ∈ Peφ . For each x ∈ P , define AP (x, ∆/Γ) = (x,q)∈Pe φ−1 (q). Then φ B(x, ∆/Γ) ∩ P ⊆ AP (x, ∆/Γ) ⊆ B(x, 2∆) ∩ P . Their result gives the following lemma. Lemma 2.3 ([BFO+ 26]). Let σ ∈ (0, 1) be a fixed constant, and let (P, dist) be an n-point metric space with polynomially bounded aspect ratio and doubling dimension ddim ≤ cσ log n for a sufficiently small constant c > 0. Given ∆ > 0 and Γ ≥ 16, we can construct a (Γ, 2O(ddim/Γ) )-hash φ with diameter bound ∆ and a set of approximate neighborhood hash pairs Peφ of size O(n·2O(ddim/Γ) ), e with high probability, in O(ddim/σ 3 ) rounds using nσ local space and O(n) · 2O(ddim/Γ) total space.

3

Technical overview

In this section, we give an overview of our algorithms for constructing approximate minimum spanning trees for a metric (X, dist) on n points. We first describe the main ideas of our framework, which apply to both general metrics and Euclidean and doubling spaces. But we mainly focus on general metrics in this section. At the end of this section, we show how to use consistent hashing to implement the framework in the Euclidean and doubling settings using O(nd + n1+σ ) e 1+σ ) · 2O(ddim) total space, respectively. and O(n Our starting point differs from that of previous work [JMNZ24, ABJ+ 25], which uses a thresholdgraph-based approach. Motivated by the use of the Prim algorithm for the MST problem in sublinear models [PvdB25, BDE+ 20], we ask whether a Prim-based approach can be used to construct 6

an approximate MST in the MPC model. For each point x ∈ X, let Sx be the set of the nσ points in X closest to x, including x. We run the Prim algorithm starting from x on the points in Sx on a single machine. Since this computation ignores points outside Sx , it may select edges that do not belong to an MST of X. To avoid this, we set τx := 12 maxy∈Sx dist(x, y). Every point outside Sx is at distance at least 2τx from x. We stop the local computation when the total weight of the current tree reaches τx or the next edge has weight at least τx . With these choices, the local computation stops before it would select an edge different from the one selected by the Prim algorithm on X, and therefore, using the same tie-breaking rule in all runs, all selected edges belong to the same MST of X. We call this procedure TruncatedPrim. Let F be the forest on X whose edges are the union of the edges selected from all points x ∈ X. Does F really help? The forest F would be useful if it had at most n1−σ components each with O(nσ ) vertices, and if each component could be identified and gathered on a single machine in O(1) rounds. In a general metric, we could contract each component into a single vertex; in a Euclidean space, we could instead choose one representative point from each component. Either way, the resulting instance has at most n1−σ vertices. If such a reduction decreases the number of vertices by a factor of nσ at every step, we could repeat it for O(1/σ) steps to obtain an exact MST in a general metric and an O(1/σ)-approximate MST in a Euclidean space. In particular, there is an instance that realizes this condition. Consider a point set on a line consisting of n1−σ groups of nσ equally spaced points each, where consecutive groups are sufficiently far. For each point x, the set Sx consists of the points in its group. Then the components of F are precisely the groups. Thus we may safely reduce the instance size in this case. In general, however, F need not have such a convenient structure. We may encounter two difficulties: (i) a component is too large to fit on a single machine; (ii) the number of components is too large to reduce the instance by a polynomial factor. More specifically, consider the case where all n points are equally spaced on a line. In this case, F can be a single path on all n points, which is too large to gather on one machine. At the other extreme, if every pair of distinct points in a general metric has distance 1, then τx = 1/2 for every x. The first candidate edge in each local computation has length 1, so no edge is selected. In this case, F consists of isolated vertices and does not reduce the number of points. Resolving Issue (i): Forest cutting. We start with the following observation. We indeed do not need to gather each component on a single machine for our purposes. Instead, it suffices for each vertex to know an identifier of its component, which can be used to select a representative or to identify vertices to be contracted. However, identifying the components of a forest is still challenging in the MPC model. Indeed, a constant-round MPC algorithm for identifying the components of an arbitrary forest would contradict the 1-vs-2-cycles conjecture [BLM+ 23]. Instead, we cut F into rooted subtrees and identify these subtrees using local neighborhoods. More specifically, we first orient and remove some edges to obtain a rooted forest, and then use random labels to cut additional edges. The cuts ensure that, for each vertex x, the root of its resulting subtree lies in a small forest neighborhood available on its machine. Thus, each vertex can identify its root locally. Resolving Issue (ii): Forest merging. A simple solution is sampling: we sample each component independently with a probability proportional to its size so that the expected number of sampled components is polynomially smaller than n. We connect each unsampled component to

7

its closest sampled component.4 The added edges may not belong to an MST, so we need to bound their weight. For each unsampled component containing a vertex x, its neighborhood Sx intersects a sampled component with high probability, so the edge added for this component has weight at most 2τx . To see why the total cost is small, choose a representative with the minimum threshold in each component of F . The stopping conditions allow us to charge each such threshold to the weight of its component and an MST edge leaving it. Since each MST edge is charged at most twice, the sum of these thresholds for all representatives is O(OPT).5 This implies that the expected total weight of the added edges is also O(OPT). A more detailed explanation will be provided in Section 3.2. This is sufficient for the approximation factor claimed for the Euclidean and doubling cases. For general metrics, we first merge components along MST edges before sampling, reducing the expected sum of τx for the representatives x to εOPT. We now explain the ideas behind forest cutting and forest merging in more detail, focusing on the first iteration for a general metric. Later iterations require additional care, as each contracted vertex must carry the weight of the tree it represents. Details can be found in Section 3.3 and Section 5. We also briefly discuss the modifications for Euclidean and doubling metrics in Section 3.3.

3.1

Forest cutting (for the first iteration)

Let F be the forest obtained by running TruncatedPrim from every vertex x ∈ X. The edges of F are distributed across the machines. For each x ∈ X, one machine stores the neighborhood Sx and the subgraph of F induced by Sx . Our goal is to remove edges from F so that each vertex can identify the root of its resulting tree using local information, while the expected sum of the thresholds τx over the roots x is O(OPT). The forest cutting algorithm consists of two steps. Both steps use the following property, which follows from the definition of τx and the triangle inequality. Property 3.1. For any x, y ∈ X, we have |τx − τy | ≤ dist(x, y)/2. Step 1. Giving orientations to edges. We first orient and possibly remove edges to ensure that each vertex has at most one outgoing edge. Each resulting tree then has a unique vertex with no outgoing edge, which we call its root. For each non-root vertex, the endpoint of its outgoing edge is its parent. The parent relation defines a unique path from each vertex to its root. When we remove an edge, its tail becomes the root of a new tree. We give orientations to edges as follows. For each vertex x, choose the vertex v(x) with the lexicographically smallest identifier among the vertices at distance at most τx /4 from x in F , where distance in F is the total weight of the edges on the path. If v(x) ̸= x, orient the first edge on the path from x to v(x) towards v(x). Since the size of Sx is small, v(x) and the first edge can be computed locally. After all vertices make their choices in F , remove every edge that has not been oriented. To see why each remaining edge has a unique orientation, suppose that an edge (x, y) is oriented in opposite directions. By Property 3.1, v(x) lies within the search region of y and v(y) lies within the search region of x. The choice of the smallest identifier then implies v(x) = v(y), but their paths to this vertex cannot start with the same edge in opposite directions, which is a contradiction. Each vertex orients at most one edge out of itself and therefore has at most one outgoing edge. A resulting tree with k vertices has k − 1 edges, whose outgoing endpoints must be distinct. Thus, exactly one vertex has no outgoing edge, and this implies that each tree has a unique root. 4

In the Euclidean setting, we instead use an approximate nearest root of a sampled component to determine how to merge the components. This can be implemented efficiently using consistent hashing. 5 The forest cutting also ensures that the expected sum of the thresholds of the roots after cutting is O(OPT).

8

For forest merging, we need to show that the sum of τx for the roots is O(OPT). Each root x chooses itself as v(x); therefore, no vertex with a smaller identifier lies within distance τx /4 from x in F . Together with Property 3.1, this implies that the neighborhoods in F of radius τx /16 centered at the roots x are pairwise disjoint. For the analysis, view each edge of F as a line segment of length equal to its weight. For each original component of F before Step 1, consider paths πx from the roots x produced by Step 1 in that component towards a vertex u of minimum threshold in the component, stopping each path from a root x at that vertex or at distance τx /16 from x, whichever comes first. The stopping point may lie in the interior of an edge. Since these path segments πx are disjoint, their total length is at most the weight of F . If πx has length τx /16, we charge τx to the length of πx . Otherwise, πx reaches u, and Property 3.1 implies that τx = O(τu ). As the paths are disjoint, at most one path in each component reaches u; we charge its threshold to τu . The weight of F is O(OPT) because F is contained in an MST, and the sum of the minimum thresholds of the original components of F is O(OPT) by the stopping condition of TruncatedPrim. This implies that the sum of τx for all roots is O(OPT). Step 2. Cutting additional edges from the oriented forest. After Step 1, each non-root vertex can identify its parent in the resulting forest. However, a vertex may not know the root of its tree; we need this information to contract the tree into a single vertex. In Step 2, we cut additional edges to ensure that, for each vertex x, the path in F from x to its root lies in Sx , while the expected sum of τx over all roots remains O(OPT). If so, x can identify its root locally using the subgraph stored on its machine. To achieve this, we use the following strategy. For technical reasons, we attach an infinite ray to each root of the forest obtained after Step 1. For each vertex x, let πx′ be the path of length τx /8 starting at x and following parent edges towards its root, continuing along the attached ray if necessary. The endpoint of the path may lie in the interior of an edge or on a ray. First, the root of x after cutting must lie on πx′ . Second, each edge (v, p(v)) is cut with probability O(dist(v, p(v))/τv ), where p(v) denotes the parent of v in F . The first property allows x to identify its root locally. For the second, cutting (v, p(v)) makes v a new root, and its expected contribution to the sum of τx for all roots is O(τv · dist(v, p(v))/τv ) = O(dist(v, p(v))). We start with the following observation. For every edge (v, p(v)), Property 3.1 implies that ′ is at most 3 dist(v, p(v)). the total length of the portions belonging to exactly one of πv′ and πp(v) Since the union of the two paths has length at least τv /8, the fraction of the union that belongs to exactly one path is at most min{1, 24 dist(v, p(v))/τv }. For example, if dist(v, p(v)) ≤ τv /48, the two paths share at least half of their union. For each edge (v, p(v)), we aim to design a cutting ′ scheme so that the probability of cutting the edge is at most the fraction of πv′ ∪ πp(v) belonging to exactly one of the two paths, which gives the desired bound of O(dist(v, p(v))/τv ). ′ To see how this observation can be useful, focus on the two paths πv′ and πp(v) . Their union consists of three pieces: the piece common to both paths and one piece belonging only to each path. Suppose that each nonempty piece of length ℓ receives an independent random key drawn from Exp(ℓ), and each endpoint chooses the smallest key on its path. Then v and p(v) choose the same key precisely when the smallest key lies in the common piece, which happens with probability equal to the length of the common piece divided by the length of the union. This satisfies the probability bound mentioned earlier. To coordinate these choices across all vertices, we subdivide the edges of the forest and the rays attached to the roots into fragments and assign each fragment I an independent random key drawn from Exp(ℓ(I)), where ℓ(I) is the length of I. Specifically, the fragments are the finite segments obtained by subdividing each edge and ray at the endpoints of the paths πx′ for all vertices x. We 9

assign a distinct label to each ray and to each fragment on an edge, and give every fragment on a ray the label of that ray. Each vertex x takes the label of the fragment with the smallest key on πx′ . We cut an edge if its endpoints have different labels. By the argument above, the probability that a fixed edge (v, p(v)) is cut is O(dist(v, p(v))/τv ), as desired. Moreover, for each vertex x, let I be the fragment with the minimum key in the path πx′ . If I lies on a ray, the root of x before Step 2 lies on πx′ . Otherwise, let (u, p(u)) be the edge containing I. Since I has a unique label, p(u) cannot have the same label as x. Thus, we cut an edge on the path from x to p(u). In either case, the root of x lies on πx′ , and every vertex on the path from x to this root belongs to Sx .

3.2

Forest merging (for the first iteration)

After forest cutting, we have a rooted forest F such that, for each vertex x, every vertex on the path from x to its root belongs to Sx . Moreover, the expected sum of τz for all roots z is O(OPT). Our goal is to merge the trees of F by adding edges of total length at most εOPT, leaving at most n1−σ components. As discussed earlier in this section, we can use sampling to merge the trees. However, the expected cost of the edges added by this approach is bounded in terms of the expected sum of τz over all roots z, which gives only an O(OPT) additive error. This bound is too large for our purpose, as we aim for an additive cost of at most εOPT. Before sampling, we therefore merge the trees using a different strategy to reduce the sum of τz over their roots. Merging via leader compression. We first merge the trees of F along MST edges without introducing any additive error. In each iteration, every component selects a minimum-weight edge leaving it. The cut property ensures that these edges are contained in an MST. Instead of adding all these edges, we use leader compression to merge components while keeping track of the resulting components in the MPC model. Each component independently becomes a leader with probability 1/2. For each nonleader, if its selected edge connects it to a leader, we merge the two components along that edge. The root of each merged component is the root of its leader. A similar combination of a Borůvka-style algorithm and leader compression was also used in [ABJ+ 25] to reduce the number of components. Here, we use this approach to reduce the expected sum of τz over the remaining roots. In each iteration, each root is removed with constant probability, and the expected sum of the thresholds of the remaining roots decreases by a constant fraction. After O(log(1/ε)) iterations, this sum is at most εOPT in expectation. Merging via sampling. Now we merge the remaining components by sampling. This is the only step that can introduce an additive error. We sample each component C independently with probability min{1, |C|/nσ/10 }. For each unsampled component, we add a shortest edge connecting it to a sampled component. The expected number of sampled components is at most n1−σ/10 , and every unsampled component is connected to one of them. For each root z, the components intersecting Sz contain at least nσ points in total. By the sampling probabilities, at least one of these components is sampled with high probability. Since every point in Sz is within distance 2τz of z, the edge added for an unsampled component with root z has length at most 2τz . Thus, on this high-probability event, the total length of the added edges is at most twice the sum of τz over the roots before sampling. By the preceding step, this gives an O(εOPT) bound on the expected contribution from this event; the contribution from the remaining low-probability outcomes can be bounded separately. Consequently, this step reduces the expected number of components to O(n1−σ/10 ) while adding edges of total expected length O(εOPT).

10

3.3

Completing the algorithms

We now explain how to extend the first iteration to obtain an approximate MST in a general metric. We contract each component of the forest into a single vertex. We would like to repeat the same procedure on the contracted graph, using the minimum distance between each pair of components as their edge weight. However, the resulting graph need not satisfy the triangle inequality. To resolve this, we introduce vertex weights: For each contracted vertex v, let Cv denote its component and let ωv be the total weight of its spanning tree. We define the distance between two vertices u and v by dist(u, v) := mina∈Cu , b∈Cv dist(a, b), where the distances on the right are measured in the original metric. These distances and vertex weights satisfy the relaxed triangle inequality: dist(u, v) ≤ dist(u, w) + ωw + dist(w, v). Indeed, the two points of Cw realizing the distances to Cu and Cv can be connected by a path in its spanning tree of length at most ωw . This inequality allows us to extend the algorithm to the instances produced in later iterations. In this way, each iteration reduces the number of vertices by a polynomial factor with high probability. After O(1/σ) iterations, the remaining graph fits on one machine, where we compute an exact MST. By setting the error parameter of each iteration to O(σε), we obtain a (1 + ε)-approximate MST. Most operations in each iteration, including computing the neighborhoods directly, can be implemented in O(1/σ) MPC rounds using O(n2 ) total space. The repeated leader compression takes O(log(1/(σε))/σ) rounds per iteration. Overall, the algorithm takes O(log(1/(σε))/σ 2 ) rounds and e 2 ) total space. uses nσ local space per machine and O(n Modification for Euclidean and doubling spaces. For Euclidean and doubling spaces, there are two key differences. First, contracting components need not preserve the underlying metric structure. We instead select one representative from each component and continue with these points. Since the representatives form a subset of the original points, their MST has weight at most twice that of an MST on the original points. This allows us to bound the weight added at each iteration in terms of the original MST weight and obtain an Oσ (1)-factor approximation. Second, most operations can be implemented in Oσ (1) MPC rounds using O(n1+σ ) total space, apart from the space needed to store the input points. Computing the exact neighborhoods Sx directly, however, involves all pairwise distances and uses quadratic space. We use consistent hashing to compute approximate neighborhoods and approximate nearest sampled roots without constructing all pairwise distances. However, the thresholds derived from approximate neighborhoods may not satisfy Property 3.1, which is crucial for forest cutting. A key technical step is to smooth the approximate thresholds locally, yielding thresholds that satisfy this property while remaining comparable to the exact thresholds. In this way, we show how to retain a constant approximation e 1+σ )2O(ddim) factor for fixed σ. The resulting total space is O(nd + n1+σ ) for points in Rd and O(n for metrics of doubling dimension ddim. Computing a TSP tour. As mentioned earlier, we can obtain a TSP tour by doubling the edges of our approximate MST, computing an Euler tour, and shortcutting repeated vertices. The challenge is to compute the Euler tour efficiently in the MPC model. After forest cutting, each root-to-vertex path fits on a single machine, which allows us to compute an Euler tour of each tree in parallel. We then combine these tours as the trees are merged, following the hierarchy of the MST construction and using the algorithm of [JMNZ24]. This yields a TSP tour of weight at most twice the weight of our tree without asymptotically increasing the round or space complexity. Roadmap. The algorithms for general metrics and for Euclidean and doubling metrics share the same framework, with the modifications described above. In Section 4, we present truncated Prim 11

and forest cutting as common subroutines with parameters that accommodate both settings. We present the general metric algorithm in Section 5 and the algorithms using consistent hashing in Section 6. Finally, we describe the construction of TSP tours in Section 7.

4

Key ingredients: Truncated Prim and forest cutting

In this section, we introduce two subroutines, TruncatedPrim and ForestCutting. In our main algorithms, the input to each call to TruncatedPrim fits in a single machine, so we always run TruncatedPrim locally. The input to ForestCutting is a forest with n vertices; we do not assume any underlying metric. Here, we provide an MPC implementation using O(N ) total space, where N is the input size defined below. These subroutines will be used in both the Euclidean and general metric cases.

4.1

Truncated Prim’s algorithm

In this subsection, we introduce a subroutine, which we call TruncatedPrim, that constructs a subgraph of an MST without computing the entire MST.6 Throughout this subsection, we use X for the vertex set of the complete graph to which the subroutine is applied, and dist for its edge lengths. Recall that Prim’s algorithm starts from a vertex x ∈ X and grows a tree one edge at a time. Let U denote the set of vertices reached so far, initially U = {x}. At each iteration, we select an edge uv minimizing dist(u, v) among all edges with u ∈ U and v ∈ X \ U . We then add this edge to the current tree and add v to U . In our case, we run Prim’s algorithm on a small neighborhood Sx of x that fits in a single machine. Here, an issue is that if a vertex y with y ∈ / Sx has a short edge to a vertex in Sx , an MST of Sx obtained by Prim’s algorithm starting from x is not necessarily contained in an MST of X. To resolve this issue, we choose a neighborhood and a (sufficiently small) threshold together to terminate the procedure before we visit a vertex having a short edge to a vertex in X \ Sx . More generally, we use the following setting. Each vertex x ∈ X is associated with a positive threshold τx , a neighborhood Sx with x ∈ Sx ⊆ X, and a nonnegative vertex weight ωx . We denote a call to this subroutine by TruncatedPrim(x, Sx , τx , ω), where ω denotes the vertex weights {ωy }y∈Sx . Then the algorithm works as follows. For pseudocode, see Algorithm 1. Let U be the set of vertices visited so far, and Ex be the set of chosen edges. Thus the set of the endpoints of the edges of Ex coincides with U unless Ex = ∅. We use ω(Ex ) to denote the total length of Ex P plus v∈U ωv . We terminate the procedure when ω(Ex ) ≥ τx or U = Sx . At each iteration, we choose an edge (u, v) with u ∈ U and v ∈ Sx \ U minimizing dist(u, v). Then we add (u, v) to Ex if its length is less than τx ; otherwise, we immediately terminate the procedure. Then we add v to U , and ω(Ex ) increases by dist(u, v) + ωv accordingly. In Section 6 for the Euclidean case, we always apply Algorithm 1 by setting X as a point set in Rd and dist as the Euclidean distance in Rd . We set ωx = 0 for all x ∈ X. For general metrics, however, we contract several vertices into a single vertex before applying Algorithm 1; see Section 5. Here, each vertex x represents a set Cx of vertices of the original metric, and we abuse the notation to denote dist(x, y) := dist(Cx , Cy ). Thus dist(·, ·) does not satisfy the triangle inequality in general. Instead, by setting the vertex weight ωz to the total weight of the tree maintained within Cz , we will prove the following inequality: dist(u, v) ≤ dist(u, z) + ωz + dist(z, v) 6

for all u, v, z ∈ X.

(1)

Although [BDE+ 20] also used the truncated Prim algorithm, their stopping conditions are different from ours.

12

Algorithm 1: TruncatedPrim(x, Sx , τx , ω) Input: Root x, neighborhood Sx ∋ x, threshold τx > 0, and vertex weights {ωy }y∈Sx U ← {x}; Ex ← ∅; 2 while ω(Ex ) < τx and U ̸= Sx do 3 Let (u, v) be an edge with u ∈ U and v ∈ Sx \ U minimizing dist(u, v); 4 if dist(u, v) ≥ τx then 5 break; 1

Ex ← Ex ∪ {{u, v}}; U ← U ∪ {v};

6 7

return Ex ;

This inequality also holds for the Euclidean case where we set ωz := 0 and dist(u, z) := ∥u − z∥. Therefore, in this subsection, we assume that dist(·, ·) satisfies Equation (1). Analysis. The property we want to achieve is the following: TruncatedPrim returns a subgraph of an MST of X. However, this can be achieved only when the parameters are chosen carefully. In particular, we show that this can be achieved if ωx + dist(x, y) > 2τx for every y ∈ / Sx . Let T be the MST of the complete graph on X with edge lengths dist. We assume that the distance values are pairwise distinct. If this is not the case, we break ties by the lexicographical order of the endpoints, using the same rule throughout. Therefore, T is uniquely determined under this rule. In particular, if we apply Prim’s algorithm from any vertex x, the algorithm returns T . Lemma 4.1. Let x be a vertex in X, and let Sx be a neighborhood with x ∈ Sx ⊆ X such that ωx + dist(x, y) > 2τx for every y ∈ X \ Sx . Let Ex be the set of edges returned by TruncatedPrim(x, Sx , τx , ω). Then Ex ⊆ E(T ). Proof. We prove by induction on k that the first k edges chosen by TruncatedPrim coincide, in the same order, with the first k edges chosen by Prim’s algorithm on X starting from x. The claim holds immediately for k = 0. Suppose that the claim holds after k edges, and that TruncatedPrim is about to add another edge. Let U be the set of vertices visited by TruncatedPrim (and thus by Prim’s algorithm), and Ex the current edge set. We have ω(Ex ) < τx . Let (u, v) be the next edge chosen by Prim’s algorithm, with u ∈ U and v ∈ X \ U . Its length is at most that of the edge added by TruncatedPrim, and hence is less than τx . Then we have the following inequalities: ωx + dist(x, v) ≤ ω(Ex ) + dist(u, v) < 2τx . The first inequality can be obtained by applying Equation (1) along the path from x to u in the current tree. By the assumption on Sx , we have v ∈ Sx . Therefore, TruncatedPrim also chooses (u, v). This implies that Ex ⊆ E(T ).

4.2

Forest cutting algorithm

In this subsection, we introduce a subroutine, which we call ForestCutting, that computes a low-cost forest partition defined as follows. Consider an n-vertex forest F with positive edge weights ℓe , non-negative vertex weights ωx , and positive vertex costs ax . Here, the edge and vertex weights define the distances in F , whereas the vertex costs ax determine the quality of the partition as we will see later. For distinct vertices x and y in the same component of F , let distF (x, y) be the total weight of the edges and vertices on their unique path, including x but excluding y. We set 13

distF (x, x) = 0. Notice that distF (x, y) − distF (y, x) = ωx − ωy if x and y are contained in the same component. We say that a tree is oriented if its edges are oriented towards a unique root, and that a forest is oriented if each of its components is oriented. For a non-root vertex x in an oriented forest, we use p(x) to denote its parent. Removing the edge (x, p(x)) splits its component into two oriented trees, one with the original root and one with the new root x. Our goal is to choose and orient a subset of the edges of F so that the resulting rooted subtrees satisfy the following definition. The first term in (ii) is a lower bound on the total root cost of any partition: each component of F contains at least one root. Definition 4.2 (Low-cost forest partition). A randomized partition of F into oriented subtrees obtained by removing edges and orienting the remaining edges is a low-cost forest partition if the following properties hold. Let R be the set of roots of the resulting trees, and let r(x) be the root of the tree containing x. (i) For every vertex x ∈ V (F ), we have distF (x, r(x)) ≤ ax for every outcome of the random choices. (ii) The expected total cost of the roots satisfies hX

E

z∈R

i

az ≤

X C∈cc(F )

min av + O v∈C

 X e∈E(F )

ℓe +

X



ωv ,

v∈V (F )

where cc(F ) denotes the connected components of F before any edges are removed. Input representation for the MPC model. As input, we are given F along with its edge weights, vertex weights, and vertex costs. Here, the hop-diameter of F may be large. To obtain an O(1/σ)-round MPC implementation, we additionally assume that a small neighborhood of each vertex is given as input. More specifically, let Fx be the subgraph of F induced by {y ∈ V (F ) : distF (x, y) ≤ ax }. For each x ∈ V (F ), the vertices and edges of Fx , together with their identifiers, weights, and vertex costs, are stored on a single machine. In this case, the P input size N is x∈V (F ) |V (Fx )|. In this subsection, we prove the following lemma, which will be used in Section 6 and Section 5. Lemma 4.3. Fix a constant σ ∈ (0, 1). Let F be a forest on at most n vertices with positive edge weights ℓe , non-negative vertex weights ωx , and positive vertex costs ax such that ax ≤ ay + distF (x, y)/8 for any two vertices x, y in the same component of F . Assume that F is stored across machines and that, for each x ∈ V (F ), the records of Fx fit on a single machine with local space nσ . Then there is an O(1/σ)-round MPC algorithm that computes a low-cost forest partition of F along with the root r(x) for every vertex x ∈ V (F ), using nσ local space per machine and O(N ) total space. The algorithm consists of two steps. In the first step, we give orientations to edges and remove some edges so that each resulting component becomes oriented with a unique root. The resulting oriented forest satisfies condition (ii). However, two issues remain: condition (i) does not necessarily hold, and it is unclear if r(x) can be computed in O(1/σ) rounds. In the second step, we remove some edges while keeping condition (ii) so that, for each vertex x ∈ V (F ), either its current root lies in Fx , or an edge on the path from x to that root whose endpoint closer to x lies in Fx is removed. Due to this property, condition (i) is satisfied, and r(x) can be computed locally from Fx once the parent and edge-removal information is available. We describe the first and second steps in Section 4.2.1 and Section 4.2.2. Then we provide an MPC implementation in Section 4.2.3. 14

4.2.1

Step 1. Giving orientations to edges

The idea is simple: For each vertex x ∈ V (F ), choose a vertex v(x) ∈ V (Fx ) with the largest weight ωv(x) , breaking ties by a fixed vertex order. If v(x) ̸= x, orient the first edge on the path from x to v(x) towards v(x). All choices of v(x) are made in the initial forest F . Then we remove every edge not oriented in this way. For a technical reason, we also remove the outgoing edge selected by each vertex x with ωx ≥ ax /2, if such an edge exists. We let F ′ be the resulting forest, and keep F for the initial forest. Now we first show that F ′ is oriented: every edge has only one orientation, every component has a single root, and every edge goes towards the root. Then we show that condition (ii) holds. Lemma 4.4. Assume ax ≤ ay + distF (x, y)/8 for any two vertices x, y in the same component of F . Then F ′ is oriented. Proof. We claim that every edge (x, y) of F ′ has only one orientation. Assume that (x, y) is oriented from x to y. By construction, y is contained in the path in F between x and v(x). In this case, v(x) ∈ V (Fy ). To see this, observe that distF (y, v(x)) = distF (x, v(x)) − distF (x, y) ≤ ax − distF (x, y) ≤ ay . The first inequality holds due to v(x) ∈ V (Fx ), and the last inequality holds by the assumption that ax ≤ ay + distF (x, y)/8. Now assume to the contrary that (x, y) is oriented in both directions. The argument above implies that v(x) ∈ V (Fy ) and v(y) ∈ V (Fx ). By the choice of v(·), this implies that v(x) = v(y), which is impossible: the unique paths from x and y to the same target vertex v(x) = v(y) cannot both start with (x, y). Now observe that every vertex of F ′ has at most one outgoing edge. For a component C of F ′ , |E(C)| = |V (C)| − 1. This implies that C has only one vertex without outgoing edges, which is the root of C. Moreover, since F has no undirected cycle, every edge of C goes towards its root. This completes the proof of the lemma. Lemma 4.5. Assume ax ≤ ay + distF (x, y)/8 for any two vertices x, y in the same component of F . Let R′ be the set of roots of F ′ . Then we have X z∈R′

az ≤

X C∈cc(F )

min av + O v∈C

 X

ℓe +

e∈E(F )

X



ωv .

v∈V (F )

Proof. Let z be a root in R′ . By construction, there are two cases: either v(z) = z, or ωz ≥ az /2. For the latter case, the sum of az for all such roots is at most the sum of 2ωz for all such roots. Therefore, it suffices to focus on the former case. We now analyze an upper bound on az for each root z ∈ R′ with v(z) = z. For each component C of F , choose a vertex uC with minimum cost auC in C. For each root z in C with v(z) = z, let πz be the undirected path in F starting at z towards uC and ending at the first vertex y with distF (z, y) > az /8, or at uC if no such vertex exists. We use ℓ(πz ) to denote the total weight of its edges and vertices, excluding its last vertex. If distF (z, uC ) > az /8, then az < 8ℓ(πz ) by construction. Otherwise, πz ends at uC , and the assumption on the vertex costs implies az ≤ auC + ℓ(πz )/8. We now claim that for any two distinct roots z, z ′ ∈ R′ in the same component of F with v(z) = z and v(z ′ ) = z ′ , there is no vertex y satisfying both distF (z, y) ≤ az /8 and distF (z ′ , y) ≤ az ′ /8. Assume to the contrary that such a vertex y exists. Since y ∈ V (Fz ) ∩ V (Fz ′ ), v(z) = z, and v(z ′ ) = z ′ , we have ωy ≤ min{ωz , ωz ′ }. Thus we have distF (z, z ′ ) ≤ distF (z, y) + distF (y, z ′ ) = distF (z, y) + distF (z ′ , y) + ωy − ωz ′ ≤ distF (z, y) + distF (z ′ , y) ≤ (az + az ′ )/8. 15

The last inequality holds by the assumed bounds on distF (z, y) and distF (z ′ , y). Symmetrically, distF (z ′ , z) ≤ (az +az ′ )/8. Assume without loss of generality that z is preferred to z ′ when choosing v(·), that is, either ωz > ωz ′ , or ωz = ωz ′ and z has a higher priority than z ′ in the fixed vertex order. By the assumption on the vertex costs, we have az ≤ az ′ +distF (z, z ′ )/8 ≤ az ′ +(az +az ′ )/64, which implies az < 2az ′ . Therefore, distF (z ′ , z) < 3az ′ /8 < az ′ , and thus z ∈ V (Fz ′ ). This contradicts v(z ′ ) = z ′ by the choice of v(·). This proves the claim. By construction, every vertex y of πz other than its last vertex satisfies distF (z, y) ≤ az /8. Thus the claim implies that, after excluding the last vertex of each path, the paths are pairwise vertex-disjoint. Moreover, all paths in a component C go towards uC . If two paths contained the same edge, its endpoint farther from uC would be a vertex other than the last vertex of both paths, contradicting the claim. Therefore, each edge belongs to at most one path, and the sum of ℓ(πz ) over P P all these roots is at most e∈E(F ) ℓe + v∈V (F ) ωv . The claim also implies that, in each component C, at most one such root z satisfies distF (z, uC ) ≤ az /8. Hence the term auC = minv∈V (C) av is added at most once per component. Summing the bounds on az and adding the costs of the roots with ωz ≥ az /2 proves the lemma. 4.2.2

Step 2. Cutting additional edges from the oriented forest

Now we have an oriented forest F ′ satisfying condition (ii). Recall that some edges of the initial F are removed in the construction of F ′ . But to simplify notation, we simply redefine F := F ′ . Our goal in this subsection is to remove additional edges from F so that condition (i) also holds. For this, we assign a label i(x) to each vertex x ∈ V (F ), and remove every edge of F whose endpoints have different labels. In the following, as F is oriented, the parent p(x) of a non-root vertex x is uniquely defined. We let ℓx := distF (x, p(x)) = ℓ(x,p(x)) + ωx . By the construction in Section 4.2.1, we have ωx < ax /2 for every non-root vertex x. Algorithm description. We view each edge (x, p(x)) ∈ E(F ) as a segment xp(x) of length ℓx . This allows us to refer to points in the interiors of edges. A vertex of F is also considered as a point. To allow paths to continue beyond a root, we attach an infinite ray to each root of F . For two points p and q with q on the path from p towards its root or on the attached ray, we extend the notation distF (p, q) to denote the total length of the unique path connecting them, including any partial segments at its ends. For each non-root vertex x, set ρx = maxy {ay /2 − distF (x, y)}, where the maximum is taken over x and its non-root ancestors. For each root r, set ρr = ar /2. For each vertex x ∈ V (F ), let px be the point reached by moving from x towards its root for a distance of exactly ρx , continuing along the attached ray if necessary. The point px is uniquely defined for each x ∈ V (F ). We mark the points px for all x ∈ V (F ) and subdivide every edge and every attached ray at the marked points. Let I denote the resulting segments, which we call fragments, excluding the infinite parts of the infinite rays. Notice that the fragments are pairwise interior-disjoint, and each path from x to px is a union of fragments. See Figure 1(a). For each fragment I ∈ I of length ℓ(I), we independently draw a random key ξI from the exponential distribution with rate ℓ(I), that is, Pr[ξI > t] = e−ℓ(I)t for t ≥ 0. Now we define the label i(x) of a vertex x ∈ V (F ) as follows. We first give a label i(I) to each fragment I ∈ I: if I is contained in an edge of F , it has a unique label, and if it is contained in an infinite ray attached to a root, its label is shared by all fragments contained in the same infinite ray. Different rays receive distinct labels that are not assigned to fragments contained in edges of F . For each vertex x ∈ V (F ), let Ix be the fragment with the smallest key among those on the path from x to px , and set i(x) = i(Ix ). In particular, each root of F receives the label of its attached 16

r

x

r px

x

ρy py

ρx

ℓx y

Iy Ix

px

r

x

ρx (a)

Ix

(b)

Figure 1: Fragments used by the forest cutting algorithm. Black dots denote vertices of F , and hollow squares denote marked points pz . Only an ancestor path is shown; other branches are omitted. (a) We attach a ray to the root, mark px at distance ρx from x, and subdivide at all marked points. The shaded fragments form Ix . (b) For y = p(x), the top and bottom shaded paths consist of Iy and Ix , respectively, and the edge (x, y) has length ℓx .

ray. Finally, we remove every edge (x, p(x)) ∈ E(F ) with i(x) ̸= i(p(x)) and return the resulting oriented forest F ′ . Analysis. We now show that the resulting trees form a low-cost forest partition of F if ax ≤ ay + distF (x, y)/8 for any two vertices x, y in the same component of F , and ωx < ax /2 for every non-root vertex x. Lemma 4.6. For a vertex x of F , we have ax /2 ≤ ρx ≤ ax . If p(x) is not a root, |ρx − ρp(x) | ≤ ℓx . Proof. If x is a root, ax /2 ≤ ρx ≤ ax by definition. Otherwise, x itself is included in the maximum defining ρx , and hence ρx ≥ ax /2. To prove the upper bound, let y be a non-root ancestor of x, possibly x itself. By the definition of the distance, distF (y, x) = distF (x, y) + ωy − ωx ≤ distF (x, y) + ay , since ωy < ay /2 and ωx ≥ 0. Applying the assumption on the vertex costs to (y, x) gives ay ≤ ax + distF (y, x)/8 ≤ ax + (distF (x, y) + ay )/2. Rearranging, we obtain ay /2 − distF (x, y) ≤ ax − distF (x, y)/2 ≤ ax . Taking the maximum over y proves ρx ≤ ax . Moreover, if ρx = ay /2 − distF (x, y), then ax /2 ≤ ρx ≤ ax − distF (x, y)/2, so distF (x, y) ≤ ax and y ∈ V (Fx ). Now consider the second part of the lemma. Let y = p(x) be a non-root vertex. The candidates in the maximum defining ρx are x, y, and the non-root ancestors of y. For each candidate other than x, the distance from x is ℓx larger than the distance from y. Therefore, ρx = max{ax /2, ρy − ℓx }. This immediately gives ρx ≥ ρy − ℓx . On the other hand, the assumption on the vertex costs gives ax /2 ≤ ay /2 + ℓx ≤ ρy + ℓx . Thus both terms in the maximum are at most ρy + ℓx , and hence ρx ≤ ρy + ℓx . Combining the two bounds proves |ρx − ρy | ≤ ℓx . Lemma 4.7. For a vertex x ∈ V (F ), we have distF (x, r(x)) ≤ ax , where r(x) is the root of the tree containing x in F ′ . Proof. Let Ix be the fragment with the smallest key among those on the path from x to px . Then i(x) = i(Ix ). If Ix is contained in the infinite ray attached to the root r of the tree in F containing x, then distF (x, r) ≤ ρx ≤ ax by the choice of Ix . Since distF (x, r(x)) ≤ distF (x, r), the lemma holds immediately. Now consider the case that an edge (v, p(v)) of F contains Ix . If i(v) ̸= i(x), 17

then r(x) lies on the path between x and v, and distF (x, r(x)) ≤ distF (x, v) ≤ ρx ≤ ax . If this is not the case, i(v) = i(x) = i(Ix ), but i(p(v)) ̸= i(Ix ). This is because the upward path starting at p(v) does not contain Ix , and the label of Ix is unique. In this case, the edge (v, p(v)) is removed in the construction of F ′ , so r(x) again lies on the path between x and v. Thus the lemma holds in any case. Lemma 4.8. Let R be the set of the roots of F , and R′ be the set of the roots of F ′ . Then we have h X

E

i

X

az ≤

z∈R′ \R

O(ℓx )

x∈V (F )\R

if ax ≤ ay + distF (x, y)/8 for any two vertices x, y in the same component of F , and ωx < ax /2 for every non-root vertex x. Proof. Let x be a non-root vertex of F , and let y = p(x). It suffices to show that the probability that (x, y) is cut by the algorithm is O(ℓx /ax ). Indeed, a non-root vertex x of F becomes a root of F ′ exactly when (x, y) is cut. By linearity of expectation, we have h X

E

i

az =

z∈R′ \R

X

ax Pr[i(x) ̸= i(y)] ≤

X

O(ℓx ).

x∈V (F )\R

(x,y)∈E(F )

Now we focus on analyzing the probability that (x, y) is cut. Let Ix be the set of fragments contained in the path from x to px . Similarly, let Iy be the set of fragments contained in the path from y to py . See Figure 1(b). First suppose that y ∈ / R. The event that (x, y) is cut by the algorithm happens only when the fragment of Ix ∪ Iy with the smallest key is contained in Ix ⊕ Iy , where Ix ⊕ Iy = (Ix \ Iy ) ∪ (Iy \ Ix ). Then we have h

i

P

I∈Ix ⊕Iy ℓ(I)

Pr[i(x) ̸= i(y)] ≤ Pr arg min ξI ∈ Ix ⊕ Iy = P

I∈Ix ∪Iy ℓ(I)

I∈Ix ∪Iy

≤ O(ℓx /ax ).

Here, the equality holds by a standard property of independent exponential random variables, and the last inequality holds since the total length of the fragments in Ix ⊕Iy is at most ℓx +|ℓx +ρy −ρx | ≤ 3ℓx by the bound |ρx − ρy | ≤ ℓx proved above, and the total length of the fragments in Ix ∪ Iy is at least ρx ≥ ax /2. Now suppose that y ∈ R. The label i(y) is shared by all fragments on the ray attached to y. Thus i(x) ̸= i(y) exactly when Ix lies on the edge (x, y). The portion of the path from x to px on this edge has length min{ρx , ℓx }, and hence Pr[i(x) ̸= i(y)] = min{ρx , ℓx }/ρx ≤ ℓx /ρx ≤ 2ℓx /ax . 4.2.3

MPC implementation

We now provide an MPC construction of a low-cost forest partition of F using the primitives in Section 2. As input, we are given F along with its edge weights ℓe , vertex weights ωx , vertex costs ax , and neighborhoods Fx . For each x ∈ V (F ), the vertices and edges of Fx are stored on a single P machine, and the input size is N = x∈V (F ) |V (Fx )|. First step. In the first step, we choose v(x) ∈ V (Fx ) and the parent edge, if any, of each vertex x locally, since Fx contains the path from x to v(x) and is stored in a single machine. Using Aggregation on edge identifiers, we identify the edges that are not chosen by any vertex. Removing the outgoing edge of a vertex x with ωx ≥ ax /2 can be done locally. Using Broadcasting, we send the parent and parent-edge length of each vertex, or its root status, to every Fx containing that vertex. Therefore, the first step can be implemented in O(1/σ) MPC rounds. 18

Second step. In the second step, we compute ℓx for non-root vertices and ρx and px for all vertices locally using the parent information received in the first step. The proof above shows that the maximum defining ρx can be computed using only x and its non-root ancestors in Fx . Using Sorting, we sort the marked points px along each edge and attached ray and obtain O(n) fragments, keeping only the part up to the last marked point on each ray. Then we choose a random key ξI and the label i(I) of each fragment I locally.7 Using the machine ID and a local index, we assign distinct labels to the fragments contained in edges of F . All fragments on the ray attached to a root share the label of that root, using labels distinct from those of fragments in edges. Now we assign the label i(x) for each vertex x as follows. Note that the number of fragments contained in the x-px path can be large although the number of edges contained in the path is O(|V (Fx )|). To resolve this issue, for each edge e of F , we compute the minimum key among its fragments together with the label of the corresponding fragment using Aggregation. Using Broadcasting, we send this pair to every Fx containing e. Thus each Fx receives O(|V (Fx )|) pairs. Since the total size of the neighborhoods stored on each machine is O(nσ ), each machine receives O(nσ ) pairs, and the total number of pairs is O(N ). For each px , we also compute the minimum key and its corresponding label on the part of the last edge or ray on the x-px path ending at px . This part starts at the child endpoint of the edge or at the root of the ray. We obtain these O(n) pairs using PrefixSum along each edge and ray, and send the pair for px to the machine containing Fx using Broadcasting. Then each vertex x obtains i(x) locally from the pairs for the complete edges on its path and the part ending at px . Finally, we use Broadcasting to collect the endpoint labels of each edge, compare them to determine whether the edge is removed, and send this information to every Fx containing its child endpoint. Then each vertex x can find its root locally in Fx by Lemma 4.7. We use a constant number of primitive operations on O(N ) records, and thus spend O(1/σ) MPC rounds with O(N ) total space. This completes the proof of Lemma 4.3 together with all arguments in Section 4.2.1 and Section 4.2.2.

(1 + ε)-approximate MST in general metrics

5

In this section, we present a fully scalable MPC algorithm for computing a (1+ε)-approximate MST of a general metric (X, dist) with n vertices. For any fixed constants σ, ε ∈ (0, 1), the algorithm e 2 ) total space. Each uses O((1 + log(1/(σε)))/σ 2 ) rounds, nσ local space per machine, and O(n primitive in Section 2 takes O(1/σ) rounds on a polynomial number of records [GSZ11]. We may consider the metric (X, dist) as a complete undirected graph whose edge weights are the distances of a metric on its vertex set, and call it the metric graph of (X, dist). Let G0 be the input metric graph of (X, dist). We construct a spanning tree of G0 in a bottom-up fashion. At each level, we partition the current set Q of vertices into clusters and construct a spanning tree TC on each cluster C. Then we contract each cluster Cv into a single vertex v and proceed with the contracted graph. Thus each current vertex represents a connected component of the forest constructed so far in G0 . Throughout the construction, for each current edge, we store an edge of G0 of minimum weight between the two represented components and use its weight as the current edge weight. Before contracting each cluster C, we add the stored edge of G0 corresponding to each edge of TC to the final spanning tree. Since distances between contracted vertices need not satisfy the triangle inequality, we assign each vertex v a weight ω(v) equal to the total edge weight of the tree maintained within its component. 7

We assume that ξI fits within a single word, which is also assumed in [ABJ+ 25].

19

With these vertex weights, we have dist(u, v) ≤ dist(u, z) + ω(z) + dist(z, v), since the tree within the component represented by z connects any two of its points at cost at most ω(z).

5.1

Overall algorithm

To formulate this idea, we introduce the notion of a light contraction. Let G be a complete graph with edge weight dist(·, ·) and nonnegative vertex weight ω(·). We use OPT(G) to denote the minimum total edge weight and vertex weight of a spanning tree of G. For a partition C of V (G), the contracted graph G/C is defined as the complete graph where a vertex v corresponds to a partition class Cv of C. We set the edge weight distC (u, v) := dist(Cu , Cv ). Consider a spanning tree TC of a partition class C of C. Its weight weight(TC ) is defined as the total edge weight and vertex weight of TC . For each vertex v ∈ V (G/C), we set the vertex weight ωC (v) := weight(TCv ). When the context is clear, we omit the subscript C from distC (·, ·) and ωC (·). Definition 5.1 (Light contraction). Let b ≥ 2 and ε ∈ (0, 1), and let G be an m-vertex complete graph with edge-weight function dist(·, ·) and nonnegative vertex-weight function ω(·). Consider a partition C of V (G) and spanning trees {TC }C∈C . Then we say G/C is a (b, ε)-light contraction of G if the following conditions hold: (i) The number of vertices of G/C is O(m/b) + 1. (ii) The MST cost of the contracted graph satisfies OPT(G/C) ≤ (1 + ε) · OPT(G). A main technical contribution of this section is an O((1 + log(1/ε))/σ)-round randomized MPC construction of a light contraction G/C, along with a partition C of V (G) and spanning trees {TC }C∈C , which is stated in the following lemma. Lemma 5.2. Fix two parameters ε, σ ∈ (0, 1). Let n and m be two integers with m ≤ n, and let b = nσ/10 . Given an m-vertex complete graph G with edge weight dist(·, ·) and vertex weights ω(·) satisfying dist(u, v) ≤ dist(u, z) + ω(z) + dist(z, v) for any three vertices u, v, z ∈ V (G), there is a randomized MPC algorithm that computes a partition C and spanning trees {TC }C∈C such that G/C is a (b, ε)-light contraction with probability at least 1 − n−Ω(1) . The algorithm uses O(log(1/ε)/σ) e 2 ) total space. rounds, nσ local space per machine, and O(n We first prove Theorem 1.1 using Lemma 5.2. We then describe the construction of a light contraction and its MPC implementation in Section 5.2. Proof of Theorem 1.1 assuming Lemma 5.2. Let L = ⌈20/σ⌉, and keep b = nσ/10 fixed throughout the algorithm. Initially, the weight ω(·) of every vertex of G0 is zero, and the weight of each edge uv is dist(u, v). Starting with G = G0 , repeatedly compute a (b, ε/(2L))-light contraction using Lemma 5.2 while |V (G)| > nσ/3 . For each cluster C, keep the stored original edges corresponding to the edges of TC as part of the output and contract C. We make at most L calls and report failure if more than nσ/3 vertices remain. Each tree TC joins distinct current components, so the selected original edges remain a forest. The updated vertex weights are the weights of the maintained internal trees, so the inequality required by the lemma continues to hold. On every successful call, the number of vertices becomes O(m/b) + 1; while m > nσ/3 , this is at most m/nσ/20 for sufficiently large n. Thus L successful calls suffice. The remaining complete graph occupies O(n2σ/3 ) words and fits on one machine. Compute its exact MST and add the corresponding original edges to the output. The resulting spanning tree T has w(T ) = OPT(G) for the final graph G. If all calls succeed, then ε w(T ) ≤ 1 + 2L 

L

OPT(G0 ) ≤ eε/2 OPT(G0 ) ≤ (1 + ε)OPT(G0 ). 20

Sorting and aggregation update the vertex weights and the minimum edges between the new components, together with their stored original edges, in O(1/σ) rounds using O(n2 ) total space. With fresh randomness in each call, a union bound over at most L calls gives success probability 1 − n−Ω(1) . Since L = O(1/σ) and each call uses error ε/(2L), the total number of rounds is e 2 ). O((L/σ)(1 + log(2L/ε))) = O((1 + log(1/(σε)))/σ 2 ), and the total space is O(n

5.2

Proof of Lemma 5.2: Computing a light contraction

In this subsection, we prove Lemma 5.2: compute a (b, ε)-light contraction of an m-vertex complete graph G with edge weight dist(·, ·) and vertex weights ω(·). Throughout this subsection, we assume the following weighted triangle inequality: dist(u, v) ≤ dist(u, z) + ω(z) + dist(z, v)

for all u, v, z ∈ V (G).

(2)

Here, ε, σ ∈ (0, 1), n ≥ m, and b= nσ/10 . In particular, (b log n)2 is asymptotically smaller than the e 2 ) total space. For a vertex v ∈ V (G) local space complexity. We use O(nσ ) local space and O(n and a radius r, we use BG (v, r):= {u ∈ V (G) | ω(v) + dist(v, u) ≤ r}. We start by computing the smallest value rv with |BG (v, rv )| = min{m, ⌈cb log n⌉} for every vertex v ∈ V (G), and we let Sv := BG (v, rv ), where c > 0 is a sufficiently large constant. Since we use Θ(n2 ) total space, we can compute rv and Sv in O(1/σ) rounds for every vertex v ∈ V (G) using Sorting. Then we apply TruncatedPrim(v, Sv , rv /2, ω) for every vertex v ∈ V (G). Here, ω denotes the vertex weights {ω(v)}v∈V (G) . We place all vertices of Sv and all edges in Sv × Sv into a single machine for each vertex v ∈ V (G) in O(1/σ) MPC rounds in total. Then we run TruncatedPrim locally without any communication. Let F be the union of the edge sets returned by the calls of TruncatedPrim. Then the edges and vertices of F are spread over the machines, and some edges are created multiple times by different calls. We remove duplicate copies in O(1/σ) MPC rounds using Sorting. By Lemma 4.1, F is contained in an MST of G. Therefore, condition (ii) holds immediately by taking C as the vertex sets of the connected components of (V (G), E(F )) and each TC as the corresponding component tree. Indeed, we have OPT(G/C) = OPT(G). However, we still have two issues: we need to identify the component of F containing each vertex, and condition (i) does not necessarily hold. Since each tree of F might be large, it is unclear if we can do this in O(1/σ) MPC rounds. To resolve the first issue, we apply ForestCutting described in Section 4, and to resolve the second issue, we merge several components so that we have O(m/b) + 1 components at the end. 5.2.1

Forest cutting

We first apply ForestCutting with av := rv /8 and ℓuv := dist(u, v) for every vertex v ∈ V (F ) and edge (u, v) ∈ E(F ). The subroutine ForestCutting requires Fx to be stored on a single machine for each x ∈ V (F ), where Fx is the subgraph of F induced by {y ∈ V (F ) : distF (x, y) ≤ rx /8}. By construction, Fx has O(b log n) vertices, and thus we can place all edges and vertices of Fx on a single machine in O(1/σ) MPC rounds. The total space of Fx for all vertices x ∈ V (F ) is within the total space complexity of O(n2 ). We first show that this satisfies the assumption of Lemma 4.3 in the following lemma. In Section 4, recall that we let distF (x, y) be the total weight of the edges and vertices on their unique path, including x but excluding y, for any two distinct vertices x and y in the same component of F . We set distF (x, x) = 0. Lemma 5.3. For any edge (u, v) ∈ E(F ), ru ≤ rv + ω(u) + dist(u, v). Therefore, ax ≤ ay + distF (x, y)/8 for any two vertices x, y ∈ V (F ) in the same component of F . 21

Proof. Recall that rv is the smallest radius such that |BG (v, rv )| = min{m, ⌈cb log n⌉}, and Sv = BG (v, rv ). For every z ∈ Sv , Equation (2) gives ω(u) + dist(u, z) ≤ ω(u) + dist(u, v) + ω(v) + dist(v, z) ≤ ω(u) + dist(u, v) + rv . Here, the second inequality follows from the fact that z ∈ Sv . Thus Sv ⊆ BG (u, ω(u) + dist(u, v) + rv ), so this ball contains at least min{m, ⌈cb log n⌉} vertices. By the definition of ru , we obtain ru ≤ ω(u) + dist(u, v) + rv , which proves the first part of the lemma. This also immediately gives au ≤ av + distF (u, v)/8 by the definition of distF (·, ·) and av for an edge (u, v) of F . Summing these inequalities along the x-y path in F gives ax ≤ ay + distF (x, y)/8 for any two vertices x, y in the same component of F . Thus we can apply ForestCutting on F in O(1/σ) MPC rounds. Then we have a low-cost forest partition F of F consisting of oriented trees such that hX

E

i

X

rz /8 ≤

z∈R

C∈cc(F )

min rv /8 + O



v∈C

dist(u, v) +

X

(u,v)∈E(F )

X



ω(v) ,

(3)

v∈V (F )

where cc(F ) denotes the connected components of F before any edges are removed and R denotes the roots of the trees of F , by Definition 4.2 and Lemma 4.3. Moreover, each vertex v has the identifier of its root r(v) of the tree containing v in F, which allows us to identify the component of F containing v. Also, condition (ii) still holds, since the edges retained by ForestCutting are contained in an MST of G. Before discussing the second step, we prove the following lemma, which will be used in proving that condition (ii) still holds after the second step. hP

Lemma 5.4. E

z∈R rz

i

= O(OPT(G)), where R denotes the set of the roots of the trees of F.

Proof. It suffices to show that the right-hand side of Equation (3) is O(OPT(G)). The second term of the right-hand side of the equation is O(OPT(G)) since F is contained in the MST of G. Thus P we focus on proving C∈cc(F ) minv∈C rv = O(OPT(G)). If F has a single component, ω(v) + dist(v, x) ≤ weight(F ) for all vertices v, x ∈ V (F ) by applying Equation (2) along the v-x path in F . This implies that BG (v, weight(F )) contains all vertices of F . By the choice of rv , we have rv ≤ weight(F ) = OPT(G), which is the desired bound. Otherwise, let T be an MST of G containing F . For each component C of F , choose an edge (u, v) ∈ E(T ) with u ∈ C and v ∈ / C. If v ∈ / Su , ru < ω(u) + dist(u, v) ≤ weight(F [C]) + dist(u, v). Otherwise, consider the call TruncatedPrim(u, Su , ru /2, ω). The tree visited by this call is contained in F [C]. There are two cases when the subroutine terminates: either the total weight of the edges and vertices visited by the call is at least ru /2, or the next edge has length at least ru /2. In the first case, ru ≤ 2 · weight(F [C]). In the second case, ru ≤ 2 · dist(u, v), since u is visited and v ∈ / C. Thus, in all three cases, min rx ≤ ru ≤ 2 · weight(F [C]) + 2 · dist(u, v). x∈C

Each edge (u, v) of T is chosen by at most two components of F , one containing u and one containing v. Therefore, X C∈cc(F )

min rx ≤ x∈C

X

2 · weight(F [C]) +

C∈cc(F )

X (u,v)∈E(T )

which proves the lemma. 22

4 · dist(u, v) ≤ 6 · OPT(G),

5.2.2

Forest merging

Now we merge components of F by adding edges of G, while keeping the additive error induced by this procedure at most ε·OPT(G). We may use a similar approach to that used in the Euclidean case, which we call Merging-via-Sampling: sample each component with probability proportional to its size, and for a component which is not sampled, connect it to the closest sampled component.8 Here, the size of a component is the number of vertices of G it contains. As in the Euclidean case analyzed in Section 6, we can show that the additive error induced by this procedure is at most P z∈R rz , which is O(OPT(G)) in expectation by Lemma 5.4. This is acceptable in Section 6, but our desired approximation ratio is (1 + ε) here. To reduce this expected error, we first merge several components using edges of an MST T of G before applying Merging-via-Sampling. This reduces the expected sum of rz of the roots of the resulting trees to ε′ · OPT(G) for a sufficiently small constant ε′ ≤ ε. For this, we use the cut property: for each component C of F, the minimum-weight edge of G leaving C is contained in T . Therefore, we may merge the two components containing its endpoints without introducing any error. However, these edges may connect many components in a long chain, so it is unclear how to identify the resulting component containing each vertex in O(1/σ) MPC rounds. To resolve this, we use the standard technique of leader compression and call the resulting procedure Mergingvia-Leader-Compression. Merging via leader compression. We repeat the following procedure, starting with the components of F and using their roots as representatives. In each iteration, the expected sum of rz for all roots z decreases by a constant fraction, counting this sum as zero once only one component remains. In each iteration, for each current component C, we pick an edge eC = (u, v) with u ∈ C and v ∈ / C with minimum dist(u, v) in O(1/σ) MPC rounds in total for all components. Then each component becomes a leader independently with probability 1/2. For each nonleader component C, let eC = (u, v) with u ∈ C and v ∈ / C. If the component containing v is a leader, we add eC and merge C with that component. We do this for all components in O(1/σ) MPC rounds. Each component formed by a merge consists of one leader component, say Clead , and nonleader components. A nonleader component whose chosen edge does not lead to a leader remains unchanged. Every edge used to merge these components has one endpoint in Clead . For each new component, we use the root of Clead as the root of the merged component. Thus, using Sorting and Broadcasting, we can pass the identifier of the new root to every vertex of its component in O(1/σ) MPC rounds. We repeat this procedure for a sufficiently large number t = O(1 + log(1/ε′ )) of iterations, stopping as soon as only one component remains. Each iteration takes O(1/σ) MPC rounds, so the entire procedure takes O((1 + log(1/ε′ ))/σ) rounds. hP

Lemma 5.5. After applying Merging-via-Leader-Compression, E

z∈R′

i

rz ≤ (ε′ /2)·OPT(G)

if there are at least two components, where R′ denotes the set of roots of the resulting forest. Proof. Let Φi be the sum of rz over the roots after i iterations. Initially, E[Φ0 ] = O(OPT(G)) by Lemma 5.4. Fix an iteration where the current forest has at least two components. For each component C, the probability that C is a nonleader and the component reached by eC is a leader is 1/4. If this event happens, C is merged into the leader component. Thus with probability 1/4, each rz is removed from Φi . Therefore, E[Φi+1 | the current forest] ≤ (3/4) · Φi . Thus, after a 8 Unlike in the Euclidean case, we can find the closest sampled component for each unsampled component in O(1/σ) MPC rounds in total as we have Θ(n2 ) total space.

23

sufficiently large number t = O(1 + log(1/ε′ )) of iterations, E[Φt ] ≤ (3/4)t · E[Φ0 ] ≤ (ε′ /2) · OPT(G), which proves the lemma. Merging via sampling. Now we merge components so that the number of resulting components becomes O(m/b) + 1. This is the only step that can increase the MST cost. For each component C returned by Merging-via-Leader-Compression, we sample it independently with probability pC = min{1, |C|/b}, where |C| denotes the number of vertices of G in C. The expected number P of initially sampled components is at most m/b, since C |C| = m. If no component is sampled, we choose an arbitrary component and treat it as sampled. Then for each non-sampled component C, we find its closest sampled component nn(C), that is, we find the edge (u, v) with minimum dist(u, v) such that u ∈ C and the component nn(C) containing v is sampled, and then connect C with nn(C) using (u, v). Since we have Θ(n2 ) total space, this can be done in O(1/σ) MPC rounds for all non-sampled components. Lemma 5.6. Let A be the set of edges added by Merging-via-Sampling. Then h X

E

i

dist(u, v) ≤ ε′ · OPT(G).

(u,v)∈A

Proof. Let E be the event that, for every non-sampled component C with root z, some sampled component intersects Sz . Condition on the forest after leader compression. If m ≤ ⌈cb log n⌉, then Sz = V (G) for every root z, so E holds since at least one component is sampled. Otherwise, for each root z, the probability that no initially sampled component intersects Sz is at most (1 − pC ) ≤ exp(−|Sz |/b) ≤ exp(−c log n),

Y

where the product is over the current components C intersecting Sz , whose sizes sum to at least |Sz |. A union bound over at most m ≤ n roots gives Pr[E c ] ≤ ε′ /(2n) for a sufficiently large constant c depending on ε′ , where E c denotes the event that E does not occur. Fix an outcome in E and a non-sampled component C with root z. There is a sampled component C ′ containing a vertex x ∈ Sz . Since z ∈ C, the edge (z, x) is a candidate for connecting C to a sampled component. Thus, the edge (u, v) added for C satisfies dist(u, v) ≤ dist(z, x) ≤ rz − ω(z) ≤ rz , where the second inequality follows from the definition of Sz . For every pair u, v ∈ V (G), applying Equation (2) along the u-v path in an MST of G gives dist(u, v) ≤ OPT(G). Since at most m − 1 ≤ n edges are added, the total added weight is at most n · OPT(G) even when E does not hold. Therefore, h X

E

i

dist(u, v) ≤ E[Φt ] + n · Pr[E c ] · OPT(G) ≤ ε′ · OPT(G).

(u,v)∈A

Let C be the final partition of V (F ). Note that each component C of C has a spanning tree TC , and each vertex v ∈ C is associated with its root r(v) in TC . Therefore, we can compute G/C in O(1/σ) MPC rounds using O(n2 ) total space. We have shown that the expected number of components of C is O(m/b). By Lemma 5.6, the expected value of OPT(G/C) is at most (1 + ε) · OPT(G). By combining these results, we now prove Lemma 5.2.

24

Proof of Lemma 5.2. We apply the entire construction Θ(log n) times independently in parallel with ε′ = ε/4. For each execution, let K be the number of components in C, and let W be the total weight of the edges added by Merging-via-Sampling. We already showed that E[K] ≤ O(m/b) and E[W ] ≤ (ε/4) · OPT(G). By Markov’s inequality and a union bound, the two bounds K ≤ O(m/b) and W ≤ ε · OPT(G) hold simultaneously with probability at least 1/2. Furthermore, we already showed that for every execution, OPT(G/C) ≤ OPT(G) + W . Among the Θ(log n) executions with K ≤ O(m/b), we return the one with minimum W , and report failure if there is no such execution. With probability at least 1 − n−Ω(1) , some execution satisfies both bounds above. The selected execution then also satisfies both bounds, and hence gives a (b, ε)-light contraction. The executions are performed in parallel, and aggregation computes their values of K and W and selects an execution in O(1/σ) rounds. With ε′ = ε/4, the total e 2 ). number of rounds is therefore O((1 + log(1/ε))/σ), and the total space is O(n

6

Constant approximate MST in Euclidean and doubling spaces

In this section, we present fully scalable MPC algorithms for computing an O(1)-approximate MST of a set P of n points in the Euclidean space of dimension d and a doubling space of doubling dimension ddim. For any fixed constant σ ∈ (0, 1), our algorithms use O(1/σ 2 ) and O(ddim/σ 4 ) rounds in Euclidean spaces and doubling metrics, respectively. The corresponding total space e 1+σ ) · 2O(ddim) , respectively. For a point set Q ⊆ P , let OPT(Q) bounds are O(nd + n1+σ ) and O(n denote the weight of an MST of Q. Let G be a graph such that a vertex of G corresponds to a point in P . We use ω(G) to denote the sum of its edge weights, where the weight of an edge is the distance between its endpoints. To avoid heavy notation, we also use ω(G) instead of weight(G) for a graph G. As for general metrics, our algorithm constructs a spanning tree in a bottom-up fashion, starting with the input point set P . At each level, we partition the current point set Q into clusters and construct a spanning tree TC on each cluster C. In the general metric case, we contract each cluster into a single vertex and proceed with the contracted graph. We instead select one representative point per cluster for the next level. We repeat this until the remaining representatives fit on a single machine. At this level, we can compute the MST of the representatives on a single machine. Then we return the tree edges computed at all levels as the output. Here, for d-dimensional Euclidean spaces, we assume d = O(log n); if this is not the case, we apply the Johnson-Lindenstrauss reduction [JL84], which can be implemented in constant MPC rounds [JMNZ24] in the fully scalable MPC model. Here, all pairwise distances are preserved within a constant factor with high probability.

6.1

Overall algorithm

To formulate this idea, we require that the number of representatives decreases by a polynomial factor at each level. To achieve an approximation ratio of O(1), we construct spanning trees for all clusters at every level with expected total weight O(OPT(Q)), where Q is the current representative set. For this, we introduce the notion of a light partition. Definition 6.1 (Light partition). Let b ≥ 2 be an integer, and let λ ≥ 1 be a parameter. Let (X, dist) be a metric space. For a set P of n points in (X, dist), a (b, λ)-randomized light partition is a partition C of P , together with a spanning tree TC on each C ∈ C, satisfying the following properties: (i) The number of clusters in C is O(n/b) + 1. 25

Algorithm 2: Metric MST using light partitions Input: A set P of n points in a metric space (X, dist) b ← nσ/10 ; 2 Q0 ← P , E ← ∅, i ← 0; σ/2 3 while |Qi | > n do 4 Compute a (b, λ)-light partition (Ci , {TC }C∈Ci ) of Qi ; 5 foreach C ∈ Ci do 6 E ← E ∪ E(TC ); choose a representative rC ∈ C; 1

7 8 9 10

Qi+1 ← {rC : C ∈ Ci }; i ← i + 1; Compute an MST of Qi on one machine and add its edges to E; return (P, E);

(ii) E

C∈C ω(TC )

P



≤ λ · OPT(P ).

The first property holds for every outcome of the random choices. A main technical contribution of this section is a randomized MPC construction of a light partition, which is stated in the following lemma. Lemma 6.2. Fix a constant σ ∈ (0, 1). Let n and m be two integers with m ≤ n, and let b = nσ/10 . Given a set P of m points in the Euclidean space of dimension d, one can construct a (b, O(1/σ 3 ))randomized light partition of P with high probability in O(1/σ) MPC rounds, using O(nσ ) local space per machine and O(md + n1+σ ) total space. Lemma 6.3. Fix a constant σ ∈ (0, 1). Let n and m be two integers with m ≤ n, and let b = nσ/10 . Given a set P of m points in a doubling metric space of doubling dimension ddim where σ log n ≥ Ω(ddim), one can construct a (b, O(1))-randomized light partition of P with high probability in O(ddim/σ 3 ) MPC rounds, using O(nσ ) local space per machine and Õ(n1+σ )·2O(ddim) total space. We first prove Theorem 1.2 and Theorem 1.3 using Lemma 6.2 and Lemma 6.3. To simplify the presentation, we describe only the Euclidean case. Notice that Theorem 1.2 depends only on a light partition and the triangle inequality. The doubling metric case follows directly, and thus we defer the proof of Theorem 1.3 to Appendix B. We then describe the construction of a light partition and its MPC implementation in Section 6.2. Proof of Theorem 1.2 assuming Lemma 6.2. We first describe our algorithm. For pseudocode, see Algorithm 2. Let L = ⌈20/σ⌉, and keep b = nσ/10 fixed throughout the algorithm. Starting with P = Q0 , we repeatedly compute a (b, O(1/σ 3 ))-randomized light partition. At level i, we are given a set Qi ⊆ P of representative points. Let (Ci , {TC }C∈Ci ) be a (b, O(1/σ 3 ))-randomized light partition of Qi obtained by using Lemma 6.2. We choose an arbitrary representative point per cluster in Ci , and let Qi+1 be the set of chosen representative points, which will be passed to the next level. Once nσ/2 representative points remain, we can construct their MST on a single machine. On every successful call, the number of points becomes O(m/b) + 1; while m > nσ/2 , this is at most m/nσ/20 for sufficiently large n. Thus L successful calls suffice. The union of the trees constructed at all levels forms a spanning tree on P . We denote it by T . We now show that T is an O(1)-approximate MST in expectation. Suppose that there are ℓ < L levels. For each 0 ≤ i ≤ ℓ, let mi = |Qi |. For every i < ℓ, the trees constructed within the clusters in Ci form a spanning forest on Qi , and Qi+1 contains exactly one representative from each tree. 26

Therefore, adding the spanning forest of Qi+1 merges those trees in the forest of Qi without creating P P a cycle, and thus T is a spanning tree of P . Note that |E(T )| = ℓ−1 i=0 ( C∈Ci (|C| − 1)) + (mℓ − 1) = Pℓ−1 i=0 (mi − mi+1 ) + (mℓ − 1) = n − 1. Consider an MST T ∗ of P and an Euler tour of the multigraph obtained by duplicating all edges of T ∗ . The length of the Euler tour is 2·ω(T ∗ ). For each 0 ≤ i ≤ ℓ, let (q1 , q2 , . . . , qmi ) be the points P i ∗ in Qi ordered by their first occurrence in the Euler tour. Then, m j=1 dist(qj , qj+1 ) ≤ 2 · ω(T ) by ∗ the triangle inequality, where qmi +1 = q1 . This implies that OPT(Qi ) ≤ 2 · ω(T ) = 2OPT(P ). At each executed level, the second property of a randomized light partition bounds the expected total weight of the cluster trees by O((1/σ 3 )OPT(Qi )), conditional on the preceding iterations and using fresh random choices at that level. Thus, summing over the O(1/σ) possible levels and including the final MST, we have E[ω(T )] = E

ℓ−1 X hX

i

ω(TC ) + OPT(Qℓ )

i=0 C∈Ci 4

≤ O((1/σ ) · OPT(P )) + 2OPT(P ) = O((1/σ 4 ) · OPT(P )). Each iteration constructs a randomized light partition in O(1/σ) MPC rounds. Moreover, we can select representatives locally and update the representative and edge records in O(1/σ) MPC rounds. The MST on Qℓ is computed locally. Since there are ℓ = O(1/σ) iterations, the algorithm takes O(1/σ 2 ) MPC rounds in total. By the Markov inequality, the probability that ω(T ) > 2c · OPT(P ) is at most 1/2 for some constant c. Thus, by applying Algorithm 2 independently to O(log n) copies of P in parallel and returning the tree of minimum total weight, we can construct an O(1)-approximate MST with high probability. By reusing space across iterations and applying the above algorithm with σ/2 local memory parameter, the bounds in Lemma 6.2 also give nσ/2 local space per machine, and O(n1+σ/2 ) total space. The parallel copies and the selection take O(1/σ) MPC rounds and O(n1+σ/2 log n) = O(n1+σ ) total space.

6.2

Proof of Lemma 6.2 and Lemma 6.3: Computing a light partition

In this subsection, we prove Lemma 6.2 and Lemma 6.3 by showing how to compute a (b, λ)-light partition of a point set, with λ = O(1/σ 3 ) in d-dimensional Euclidean space and λ = O(1) in a metric space of doubling dimension ddim. Our approach is similar to that used to construct a light contraction in the general metric case. However, unlike in the general metric case, the input consists of the points rather than pairwise distances, making it hard to compute exact balls centered at the points in a constant number of MPC rounds. We therefore use consistent hashing to approximate the corresponding radii; see Section 2. Since these approximate radii need not satisfy the property required by ForestCutting, we define a new value for each point x ∈ P that satisfies this property. Moreover, Merging-via-Leader-Compression, which we use in the general metric case, cannot be directly applied here in a constant number of MPC rounds since we cannot compute the nearest root without consistent hashing. Nevertheless, Merging-viaSampling suffices to obtain a constant approximation factor. Throughout this subsection, we are given a set P of m points in a metric space with distance dist. We first describe how to construct a light partition on P and how to implement this using consistent hashing. Moreover, we assume polynomial spread: the ratio of the largest to the smallest nonzero pairwise distance is polynomial in n. We show how to get rid of this assumption in Appendix A. We also assume that the minimum nonzero distance is at least one; if this is not the case, we can normalize the distances in O(1/σ) MPC rounds. Let k = ⌈cb log n⌉ = Θ(b log n), 27

where c is a sufficiently large fixed constant. If m ≤ k, we compute an exact MST of P on a single machine and return it as a single cluster. We first construct a light spanning forest using TruncatedPrim on all points in P . In the general metric case, we compute, for each point x, a radius such that the ball centered at x with this radius contains at most k points, and apply the exact ball to TruncatedPrim. However, in this case, it is unclear how to compute the exact ball centered at every point in constant MPC rounds. Therefore, we use the estimate of this radius and the set of points that approximates the exact ball. Let rx for every point x ∈ P be the smallest radius such that |B(x, r) ∩ P | ≥ k, i.e., rx = min{r : |B(x, r) ∩ P | ≥ k}. We use estimates r̂x such that rx ≤ r̂x ≤ 2γrx , where γ > 1 is a constant determined later. For each point x ∈ P , suppose that we have r̂x and a set, denoted by Sx , of points containing B(x, εr̂x ) ∩ P and contained in B(x, γεr̂x ) ∩ P , where ε = 4γ1 2 is a constant. Note that |Sx | ≤ k = O(b log n) = O(nσ/2 ) since 2εγ 2 < 1. For every point x ∈ P , we suppose that Sx is stored on a single machine. We then run TruncatedPrim(x, Sx , εr̂x /2, 0) on the machine Mx for every point x ∈ P . Let F be the union of the edge sets returned by the calls of TruncatedPrim. As in the general metric case, we remove the duplicated edges of F in O(1/σ) MPC rounds using Sorting. Since for every x ∈ P , Sx contains B(x, εr̂x ), the resulting edge set Ex is a subset of the MST from Prim’s algorithm by Lemma 4.1. Therefore, F ⊆ T and ω(F ) = O(OPT(P )). Moreover, condition (ii) holds immediately by taking a partition as the vertex sets of the connected components of (P, E(F )) and each spanning tree in a cluster as the corresponding component tree. However, we still have two issues: (i) we need to identify the component of F , and (ii) there may still be too many components in F . To resolve the first issue, we apply ForestCutting described in Section 4, and to resolve the second issue, we merge several components so that we have O(m/b) + 1 components at the end. 6.2.1

Forest cutting

We first apply ForestCutting on F . However, r̂x does not necessarily satisfy the assumption of Lemma 4.3, although the exact radius rx does. We therefore define a local radius hx = ε miny∈P {dist(x, y) + 100 r̂y } for each point x ∈ P . To compute hx for each point x ∈ P , it suffices to check the points in Sx , since hx ≤ (ε/100) · r̂x . Recall that Sx is stored in a single machine, and thus we can compute hx only using local computation. We then apply ForestCutting on F with av := hv /8 and ℓuv := dist(u, v) for every vertex v ∈ V (F ) and edge (u, v) ∈ E(F ) in O(1/σ) MPC rounds. Recall that the subroutine ForestCutting requires that for a point x, ax ≤ ay + distF (x, y)/8, where y is a point in the same tree of F . This holds since the following lemma implies that hx /8 ≤ hy /8 + distF (x, y)/8. Lemma 6.4. For any two points x, y ∈ P , |hx − hy | ≤ dist(x, y). Moreover, for every x ∈ P , εγ ε 100 rx ≤ hx ≤ 50 rx , and εr̂x ≥ 100hx . Proof. For a candidate z ∈ P , | dist(x, z) + εr̂z /100 − (dist(y, z) + εr̂z /100)| = | dist(x, z) − dist(y, z)| ≤ dist(x, y). Let z ∗ be the point realizing hy . We then have hx ≤ dist(x, z ∗ )+εr̂z ∗ /100 ≤ hy + dist(x, y). We now show the upper and lower bounds of hx for each x ∈ P . Note that hx ≤ dist(x, x) + εr̂x /100 ≤ εγrx /50 since r̂x ≤ 2γrx , and thus 100hx ≤ εr̂x . For any point y ∈ P , we have ry ≥ rx − dist(x, y), since the ball of radius ry centered at y is contained in the ball of radius ry + dist(x, y) centered at x. We then have dist(x, y) + εr̂y /100 ≥ dist(x, y) + εry /100 ≥ εrx /100 + (1 − ε/100) · dist(x, y) ≥ εrx /100, since ε < 1. Thus, hx ≥ εrx /100. 28

Moreover, ForestCutting requires that, for each x ∈ V (F ), the subgraph Fx induced by {y ∈ V (F ) : distF (x, y) ≤ hx /8} be stored on a single machine. By Lemma 6.4 and our choice of ε < 1/(2γ 2 ), we have hx /8 < rx , so Fx contains at most k = O(nσ ) vertices. Furthermore, since hx /8 ≤ εr̂x /800, every vertex of Fx belongs to Sx , which is stored on a single machine. We locally compute an MST Tx of Sx using the same edge ordering as in TruncatedPrim. Since F [Sx ] ⊆ Tx , we identify the edges of F [Sx ] using Aggregation and Broadcasting, and then compute Fx locally. These steps take O(1/σ) MPC rounds within the stated space bounds. We now have a low-cost forest partition F of F consisting of oriented trees such that "

E



# X

z∈R

hz /8 ≤

X C∈cc(F )

min hv /8 + O  v∈C

 X

dist(u, v) ,

(4)

(u,v)∈E(F )

where cc(F ) denotes the connected components of F before any edges are removed and R denotes the roots of the trees of F , by Definition 4.2 and Lemma 4.3. Moreover, each vertex v has the identifier of its root r(v) of the tree containing v in F , which allows us to identify the component of F containing v. Also, condition (ii) still holds, since the edges retained by ForestCutting are contained in an MST of P . The following lemma will be used to show that condition (ii) continues to hold after the second step. Since its proof follows the same argument as that of Lemma 5.4 in the general metric case, we defer it to Appendix C. Lemma 6.5. E[ 6.2.2

z∈R hz ] = O(OPT(P )), where R denotes the set of the roots of the trees of F .

P

Forest merging

We now merge components of F into O(m/b) + 1 components by adding edges, while keeping the approximation factor. For a root z ∈ R, we let Tz be the component in F rooted at z. We first sample independently each root z ∈ R with probability min{1, |Tz |/2⌈log b⌉ }. These sampled roots will determine how components in F are merged. Recall that each vertex v has the identifier of its root r(v) of the tree containing v in F , and thus we can compute |Tz | in O(1/σ) MPC rounds using Aggregation. We then sample z independently using local computation. The P expected number of initially sampled components is at most m/b, since z∈R |Tz | = m. If no root is sampled, we choose an arbitrary root and treat it as sampled. For each non-sampled root z, suppose that we have a 2γ-approximate nearest sampled root, denoted by ann(z). For each sampled root z, we set ann(z) = z. For every sampled root z, we add the edges between the roots whose 2γ-approximate nearest sampled root is z as follows. Let (T1 , T2 , . . . , Tℓ ) be the components in F whose roots are assigned P to z, ordered by lexicographic order. For every 1 ≤ i ≤ ℓ, we compute the prefix sum si = j<i |Tj | in O(1/σ) rounds using PrefixSum. We form clusters by grouping together the trees Ti with the same value of ⌊2si /b4 ⌋. Let C be the resulting collection of clusters. We now construct TC for each cluster C ∈ C. Let z(C) be the sampled root used to construct C. Note that C may not contain z(C). We first compute the root q in C closest to z(C). This can be done in O(1/σ) MPC rounds, since the roots in the cluster already have z(C). We then add the edge between q and all the other roots in C in O(1/σ) MPC rounds by sending q to them. We can do this in parallel for all clusters. By the following lemma, we can conclude Lemma 6.2 in the same way as in the proof of Lemma 5.2. Lemma 6.6. The expected total weight of added edges is O((γ/ε)OPT(P )). 29

Proof. Let E be the event that, for every non-sampled root z, there exists at least one sampled root q such that Tq intersects B(z, rz ). For each root z, the probability that there is no sampled root whose component intersects B(z, rz ) is at most (1 − px ) ≤ exp(−|B(z, rz ) ∩ P |/2⌈log2 b⌉ ) ≤ exp(−(c/2) log n).

Y x∈R:Tx ∩B(z,rz )̸=∅

The first inequality holds since the size sum of the components intersecting B(z, rz ) is at least |B(z, rz ) ∩ P |, and the second inequality holds since |B(z, rz ) ∩ P | ≥ k and k = ⌈cb log n⌉. A union bound over at most m ≤ n roots gives Pr[E c ] ≤ n1−c/2 . Fix an outcome in E and a non-sampled root z. There is a sampled root z ′ such that Tz ′ contains a vertex v ∈ B(z, rz ). Therefore, dist(z, z ′ ) ≤ dist(z, v) + dist(v, z ′ ) ≤ rz +

hv rv 3 ≤ rz + ≤ rz ≤ 2rz . 8 4 2

The second inequality holds by Lemma 4.7, and the third inequality holds by Lemma 6.4. The last inequality holds since for a point v in B(z, rz ), rv ≤ rz + dist(z, v) ≤ 2rz . In the case that every root z ∈ R satisfies that dist(z, ann(z)) ≤ 4γrz , consider a cluster C ∈ C. Let q be the root in C closest to z(C). By the choice of q, every other root x in C satisfies dist(x, q) ≤ dist(x, z(C)) + dist(z(C), q) ≤ 2 · dist(x, z(C)). Therefore, the total weight of added P P P edges for all clusters is at most 2 · z∈R dist(z, ann(z)) ≤ 8γ · z∈R rz ≤ (800γ/ε) z∈R hz by Lemma 6.4. Otherwise, the total added weight is at most n · OPT(P ) when E does not hold. Therefore, the expected total added weight is at most X 800γ E hz + n · Pr[E c ] · OPT(P ) ≤ O((γ/ε)OPT(P )). ε z∈R "

6.2.3

#

MPC implementation using consistent hashing

The above construction uses O(1/σ) MPC rounds in addition to those needed to compute r̂x and Sx for every point x ∈ P for TruncatedPrim and ForestCutting, and ann(z) for every root z of F for Merging-via-Sampling. Now, we describe how to compute them using consistent hashing for Euclidean spaces of dimension d and doubling metric spaces of doubling dimension ddim. Specifically, we will utilize Lemma 2.2 and Lemma 2.3 to construct a (Γ, Λ)-hash for a constant Γ. We choose γ = 2Γ + 1, where Γ is the constant from Lemma 2.2 or Lemma 2.3. Then, combining Lemma 6.6, we conclude Lemma 6.2 and Lemma 6.3. Computing r̂x . To compute r̂x for every point x ∈ P , we first compute a 2-approximation D of the diameter of P in O(1/σ) MPC rounds by computing the maximum distance from an arbitrary point. More specifically, we choose an arbitrary point and send it to all machines using Broadcasting, and then we can compute D using Sorting. Let I = {20 , 21 , . . . , 2⌈log D⌉ }. Each machine constructs I. Since |I| = O(log n), I fits in a single machine. In Euclidean spaces, for every scale t ∈ I, we construct a (Γ, Λ)-hash φt of P with diameter bound 2Γt using Lemma 2.2. Here, Γ = O(1/σ) and Λ = O(nσ ). In particular, we create one copy of P for each of the O(log n) scales and construct all hashes in parallel. For a scale t and each point x ∈ P , let Nt (x) = φ−1 t (φt (B(x, t))) ∩ P . For each point x ∈ P , we compute the minimum scale tx = min{t ∈ I : |Nt (x)| ≥ k}. To do this, for every t ∈ I, we aggregate the number of 30

points in Nt (x). Then, we set r̂x := γtx . Since Ntx (x) ⊆ B(x, (1 + 2Γ)tx ) ∩ P ⊆ B(x, r̂x ) ∩ P , |B(x, r̂x ) ∩ P | ≥ k. Therefore, rx ≤ r̂x . Moreover, by the choice of tx , r̂x ≤ 2γrx . In doubling metric spaces, we compute r̂x similarly. For every scale t ∈ I, we construct a (Γ, Λ)-hash φt of P with diameter bound Γt and its corresponding approximate neighborhood hash pairs in parallel using Lemma 2.3. Here, Γ = O(1) and Λ = 2O(ddim/Γ) in a doubling metric space. In this case, we cannot obtain Nt (x) immediately from Lemma 2.3. For each point x ∈ P , we count the number of points in AP (x, t) in O(1/σ) MPC rounds using Aggregation. Then, we compute the minimum scale tx = min{t ∈ I : |AP (x, t)| ≥ k}, and set r̂x := γtx . Since AP (x, tx ) ⊆ B(x, 2Γtx ) ∩ P ⊆ B(x, r̂x ) ∩ P , we have rx ≤ r̂x . Moreover, by the choice of tx , r̂x ≤ 2γrx . Computing Sx and collecting it on a single machine. Recall that for a point x ∈ P , Sx is the set of points containing B(x, εr̂x ) ∩ P and contained in B(x, γεr̂x ) ∩ P . We construct Sx similarly to how we compute r̂x . In particular, we collect Sx into a single machine. Let I ′ = εγI = {εγ20 , εγ21 , . . .}. Note that for every point x ∈ P , εr̂x ∈ I ′ . We first construct Sx . In Euclidean spaces, for each t ∈ I ′ , we construct a (Γ, Λ)-hash φt with diameter bound 2Γt. We set Sx := Nεr̂x (x). In doubling metric spaces, for each t ∈ I ′ , we construct a (Γ, Λ)-hash φt with diameter bound Γt and its corresponding approximate neighborhood hash pairs. We set Sx := AP (x, εr̂x ). Note that in both cases, B(x, εr̂x ) ∩ P ⊆ Sx ⊆ B(x, εγ r̂x ) ∩ P ⊆ B(x, 2εγ 2 rx ). Therefore, |Sx | ≤ k, since 2εγ 2 < 1. We now collect Sx on a single machine in parallel in O(1/σ) MPC rounds, using Broadcasting. In Euclidean spaces, we assign O(mkd) = O(n1+σ/2 ) additional space for the collected sets. We allocate O(kd) space to each point x, and let Mx denote its assigned machine, ensuring that the total allocated space on each machine is O(nσ ). For every t ∈ I ′ and y ∈ P , we create a record ((t, φt (y)), y). For each x ∈ P , we create a request ((εr̂x , q), Mx ) for every q ∈ φεr̂x (B(x, εr̂x )). Using Aggregation, we compute the number of points in a cluster and associate this count with every candidate request. We remove all candidate requests with count zero. This takes O(1/σ) MPC rounds. For each request ((t, q), Mx ), we send y to Mx for every record ((t, q), y) using Broadcasting.9 This collects exactly Sx for each x. Since |Sx | ≤ k, the collection respects the allocated space and takes O(1/σ) MPC rounds. Similar to the Euclidean case, in doubling metric spaces, we assign O(mk) = O(n1+σ/2 ) additional space for the collected sets, and allocate O(k) space to each point and create a record (t, φt (y), y) for every point y ∈ P . For each x ∈ P , we create a request (εr̂x , q, x, Mx ) for every approximate neighborhood hash pair (x, q) of φεr̂x . Then, we can collect Sx as in the Euclidean case. Computing nearest sampled root. To compute ann(z) for every root z ∈ R, we use a consistent hash φt for every t ∈ I as we compute r̂x . We first compute the minimum scale tz such that Ntz (z) in the Euclidean case and AP (z, tz ) in the doubling metric space contain at least one sampled root. We then choose an arbitrary sampled root in Ntz (z) or AP (z, tz ) as ann(z). Note that dist(z, ann(z)) ≤ γtz ≤ 2γ dist(z, X), where X is the set of sampled roots. 9 Broadcasting requires a unique value for each key. Using Sorting, we rank the points sharing each key (t, q) and assign the key (t, q, j) to the jth point. For every q ∈ φεr̂x (B(x, εr̂x )), we send the number of points with key (εr̂x , q) to Mx . The machine Mx then expands the corresponding request into one request for each point index. These steps take O(1/σ) MPC rounds within the stated total space bound.

31

7

Approximate TSP in constant rounds

In this section, we present fully scalable MPC algorithms for constructing an approximate TSP in general metric spaces, Euclidean spaces, and doubling metric spaces. More specifically, we prove the following theorem. Theorem 7.1. Fix constants σ, ε ∈ (0, 1). There are randomized MPC algorithms that return an approximate TSP with the following guarantees. • For a general metric on n points given by all pairwise distances, the algorithm returns a e 2) (2 + ε)-approximate TSP tour in O(log(1/(σε))/σ 2 ) rounds, using nσ local space and O(n total space. • For a set of n points in Rd , the algorithm returns an O(1/σ 4 )-approximate TSP tour in O(1/σ 2 ) rounds, using (dn)σ local space and O(nd + n1+σ ) total space. • For a set of n points in a metric space of doubling dimension ddim satisfying σ log n ≥ Ω(ddim), the algorithm returns an O(1/σ)-approximate TSP tour in O(ddim/σ 4 ) rounds, e 1+σ ) · 2O(ddim) total space. using nσ local space and O(n Each algorithm succeeds with probability at least 1 − n−Ω(1) . To this end, we construct an Euler tour of an approximate MST as a directed cycle. Then, if the MST has an approximation factor α, we can construct a 2α-approximate TSP in O(1/σ) MPC rounds by computing the first occurrence in the Euler tour of every point using Sorting. Therefore, it suffices to construct an Euler tour of an approximate MST while applying the algorithms in Section 5 and Section 6. Recall that our approximate MST algorithms construct a forest consisting of MST edges and merge its components in a bottom-up manner. Within each level, after applying ForestCutting, we merge each group of trees in a low-cost forest partition by designating one as the leader and attaching the others directly to it. Across levels, we merge the spanning trees of the clusters in a light contraction or light partition using the tree edges constructed at the next level. To merge multiple trees, we will use the algorithm in [JMNZ24]. Lemma 7.2 ([JMNZ24]). Let σ ∈ (0, 1) be a fixed constant. Suppose that we are given • a partition C over a set V of n vertices, • for each cluster in C, a spanning tree of the cluster and its Euler tour, • a spanning tree T , and its Euler tour where each vertex corresponds to a cluster in C, and an edge between two clusters corresponds to a pair of vertices, one from each cluster. Then, there is an MPC algorithm that computes an Euler tour of a spanning tree obtained by merging all spanning trees in the clusters of C using the edges of T . It takes O(1/σ) MPC rounds, using O(nσ ) local space and O(n) total space. Merging the trees in a low-cost forest partition. Consider constructing a light contraction or light partition at a given level. For each tree in the low-cost forest partition F obtained by Lemma 4.3, we first construct an Euler tour A starting at the root and visiting the children of each vertex in lexicographical order. We first compute the number s(v) of vertices in the subtree of F rooted at each vertex v. Let Pv denote the path from the root r(v) to v in F. By the assumption in Lemma 4.3, Fv = {u ∈ V (F ) : distF (v, u) ≤ av } is stored in a single machine. Therefore, Pv is stored in a single machine since Pv ⊆ Fv by the definition of a low-cost forest partition. For each vertex u ∈ Pv , we construct a record (v, u). The number of records whose second vertex is v equals s(v). Hence, we can compute all subtree sizes in O(1/σ) MPC rounds using Sorting and Aggregation. 32

We next determine the position of each directed edge in A using s(·). For every non-root vertex v, let B(v) be the total number of vertices in the subtrees rooted at the siblings before visiting v in A. Specifically, if c1 , . . . , ck are the children of a vertex in lexicographical order, then B(ci ) =

X

s(cj ).

j<i

We compute these values by sorting vertices by their parent and lexicographical order and taking exclusive prefix sums of the subtree sizes s(·) within the children of each vertex. We then broadcast s(v) and B(v) to every machine storing a neighborhood Fu that contains v. These take O(1/σ) MPC rounds by using Sorting, PrefixSum, and Broadcasting. Suppose that Pv = (r(v) = v0 , v1 , v2 , . . . , vk = v). Note that, after first visiting vi , the tour A visits the subtrees rooted at the siblings preceding vi+1 and then moves to vi+1 , traversing 1 + 2B(vi+1 ) edges in total. Therefore, P the directed edge from the parent of v to v has position u∈Pv \{r(v)} (1 + 2B(u)) in A. After first visiting v, the tour traverses the 2(s(v) − 1) directed edges within its subtree before returning to P its parent. Consequently, the reverse edge has position (( u∈Pv \{r(v)} (1 + 2B(u))) + 2s(v) − 1) in A. Since Pv is stored in a single machine, we can determine the position of each edge using local computation. We now have an Euler tour of each tree in F. When we merge some trees by Merging-viaLeader-Compression and Merging-via-Sampling, we choose the leader tree among the trees. We also choose the edge to merge the leader tree and each other tree. These edges form a star whose vertices correspond to the trees and whose center corresponds to the leader tree. Therefore, we can construct an Euler tour of this star in O(1/σ) MPC rounds using Sorting. Hence, we can apply Lemma 7.2 to construct an Euler tour of the tree obtained by Merging-via-LeaderCompression and Merging-via-Sampling. Lemma 7.3. Given a low-cost forest partition F constructed by Lemma 4.3, we can compute an Euler tour of each tree of F in O(1/σ) MPC rounds. Moreover, these tours can be updated after each merging iteration of Merging-via-Leader-Compression or Merging-via-Sampling in O(1/σ) MPC rounds. Merging the trees across the levels. We now merge the Euler tours constructed at different levels in a bottom-up manner. For each current vertex, we maintain an Euler tour of the tree on the original vertices represented by it. Initially, each original vertex represents a singleton tree with an empty tour. Consider a cluster C in the light contraction or light partition at a given level. The vertices of C represent vertex-disjoint trees whose Euler tours have already been computed: in the general metric case, a vertex corresponds to a contracted tree, and in the Euclidean and doubling metric cases, it is the representative point of a tree. The spanning tree TC specifies how these trees are joined, and its Euler tour is available from the construction above. Moreover, for each edge of TC , the endpoints of the connecting edge in the original vertex set are known. Therefore, we can apply Lemma 7.2 to construct an Euler tour of the tree obtained by adding these connecting edges to the represented trees. We do this in parallel for all clusters and associate each resulting tour with the contracted vertex or representative point at the next level. Each merging step takes O(1/σ) MPC rounds. Since there are O(1/σ) levels, this merging procedure takes O(1/σ 2 ) additional MPC rounds, using O(nσ ) local space and O(n) total space. Therefore, we conclude Theorem 7.1.

33

8

Conclusion

In this paper, we present randomized MPC algorithms that construct an approximate MST, with high probability, in general metric spaces, Euclidean spaces of arbitrary dimension, and doubling metric spaces of bounded doubling dimension. These algorithms improve the round complexities of the best-known MPC algorithms for general metrics and high-dimensional Euclidean spaces [ABJ+ 25, JMNZ24]. The round complexity for general metrics matches the dependence on ε in the known lower bound [ABJ+ 25] under the 1-vs-2-cycles conjecture. Our results also lead to several open questions. • (1 + ε)-approximate Euclidean MST. Our algorithm constructs a constant-factor approximate Euclidean MST in O(1) rounds, whereas the MST cost can already be estimated within a factor of (1 + ε) in O(1) rounds using near-linear total space [CCAJ+ 23]. Applying our general-metric algorithm after computing all pairwise distances also yields a (1 + ε)e approximate tree, but requires O(nd + n2 ) total space. Can a (1 + ε)-approximate Euclidean MST be constructed in O(1) rounds using (nd)σ local space per machine and subquadratic additional total space? • Near-linear total space for Euclidean spaces. Even for a constant approximation factor, e our constant-round algorithm uses O(nd + n1+σ ) total space. Can this be reduced to O(nd) σ while retaining O(1) rounds and (nd) local space? Our implementation stores overlapping neighborhoods separately to support local forest construction and cutting. • Improved approximation for metric Steiner tree. By constructing an approximate MST on the terminals, our algorithms yield fully scalable MPC algorithms for computing a (2 + ε)-approximate Steiner tree in general metric spaces and an O(1)-approximate Steiner tree in Euclidean and doubling metric spaces [GP68, MRTV25]. A recent fully scalable MPC algorithm [WHJ25] computes a (2(1 − 1/|R|))-approximate Steiner tree in weighted graphs in O(σ −1 log n + D) MPC rounds, using O(n3−σ/2 ) total space, where R is the terminal set and D is the shortest-path diameter. However, in the sequential setting, a (ln 4+ε)-approximation is known [BGRS13]. This leaves open whether a better approximation can be achieved while retaining constant round complexity. • Exact Euclidean MST with low dimension. Chang and Zheng [CZ24] present a constantround fully scalable MPC algorithm for constructing an exact Euclidean MST in two dimensions using linear total space. As noted in [CZ24], it remains open whether the same guarantees can be achieved even in three dimensions. • Distributed model. Our algorithms gather overlapping neighborhoods and redistribute component information, which may require sending the same point to several machines. Thus, their small local-memory bounds do not by themselves ensure near-linear total messages. In the related Congested Clique model, exact MSTs can be computed in constant rounds using O(n2 ) messages, when each node initially knows its incident edges and their weights [Now21]. Pemmaraju and Sardeshmukh [PS16] give an exact MST algorithm using e 1+ρ /ρ) messages, for any 0 < ρ ≤ 1. Moreover, [HPS14] presented O(log∗ n/ρ) rounds and O(n a constant-factor approximate MST algorithm for doubling metric spaces with ddim = O(1), using constant rounds and O(n2 ) messages. Coordinate input has also been studied: for n distinct points in {0, 1}n given one per node, Lingas [Lin24] constructs a constant-factor approximate Hamming MST in O(log3 n) rounds. Can we construct a constant-factor approximate MST in high-dimensional Euclidean space in the Congested Clique model using e constant rounds and O(n) messages when each node initially holds only the coordinates of one point? 34

AI methodology The authors developed the ideas underlying Theorem 1.1 and Theorem 1.2 through discussions with ChatGPT-6 Astra. They also used ChatGPT-6 Astra to improve the writing of the paper. The authors verified the correctness and originality of all content, including references.

References [ABJ+ 25]

Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram, Jakub Łącki, Vahab Mirrokni, and Peilin Zhong. Massively parallel minimum spanning tree in general metric spaces. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 143–174, 2025. doi:10.1137/1.9781611978322.5.

[ANOY14] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pages 574–583, 2014. doi: 10.1145/2591796.2591805. [ARD+ 14] Mehmet Alpaslan, Aaron S. G. Robotham, Simon Driver, Peder Norberg, Ivan Baldry, Amanda E. Bauer, Joss Bland-Hawthorn, Michael Brown, Michelle Cluver, Matthew Colless, Caroline Foster, Andrew Hopkins, Eelco Van Kampen, Lee Kelvin, Maritza A. Lara-Lopez, Jochen Liske, Angel R. Lopez-Sanchez, Jon Loveday, Tamsyn McNaught-Roberts, Alexander Merson, and Kevin Pimbblet. Galaxy And Mass Assembly (GAMA): the large-scale structure of galaxies and comparison to mock universes. Monthly Notices of the Royal Astronomical Society, 438(1):177–194, 2014. doi:10.1093/mnras/stt2136. [ASS+ 18]

Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS 2018), pages 674–685, 2018. doi:10.1109/FOCS.2018.00070.

[ASW19]

Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well-connected components in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 461–470, 2019. doi:10.1145/3293611.3331596.

[BDE+ 19]

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab Mirrokni. Near-optimal massively parallel graph connectivity. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 1615–1636, 2019. doi:10.1109/FOCS.2019.00095.

[BDE+ 20]

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Vahab Mirrokni, and Warren Schudy. Parallel graph algorithms in constant adaptive rounds: theory meets practice. Proceedings of the VLDB Endowment, 13(13):3588–3602, 2020. doi:10.14778/3424573.3424579.

[BFO+ 26]

Sujoy Bhore, Arnold Filtser, Eunjin Oh, Hyeonjun Shin, and Himanshi Singh. Geometric hashing in MPC with applications to clustering and stochastic embeddings, 2026. To appear in SODA 2027. arXiv:2610.21371, doi:10.48550/arXiv.2610.21371. 35

[BGRS13]

Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM, 60(1):6:1–6:33, 2013. doi:10.1145/2432622.2432628.

[BLM+ 23] Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Optimal deterministic massively parallel connectivity on forests. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 2589–2631, 2023. doi:10.1137/1.9781611977554.CH99. [CC23]

Sam Coy and Artur Czumaj. Deterministic massively parallel connectivity. SIAM Journal on Computing, 52(5):1269–1318, 2023. doi:10.1137/22M1520177.

[CCAJ+ 23] Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Streaming Euclidean MST to a constant factor. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 156–169, 2023. doi: 10.1145/3564246.3585168. [CEF+ 05]

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, and Christian Sohler. Approximating the weight of the Euclidean minimum spanning tree in sublinear time. SIAM Journal on Computing, 35(1):91–109, 2005. doi:10.1137/S0097539703435297.

[CFJ+ 23]

Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing, 2023. Full version; a preliminary version appeared in FOCS 2022. arXiv:2204.02095, doi:10.48550/arXiv.2204.02095.

[CGJ+ 24]

Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-scalable MPC algorithms for clustering in high dimension. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), pages 50:1–50:20, 2024. doi:10.4230/LIPIcs.ICALP.2024.50.

[CJK+ 22]

Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. In Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 450–461, 2022. doi:10.1109/FOCS54457.2022.00050.

[CJLW22]

Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. New streaming algorithms for high dimensional EMD and MST. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), pages 222–233, 2022. doi:10.1145/3519935.3519979.

[CRT05]

Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on Computing, 34(6):1370–1379, 2005. doi:10.1137/S0097539702403244.

[CS09]

Artur Czumaj and Christian Sohler. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, 39(3):904–922, 2009. doi:10.1137/060672121.

36

[CZ24]

Yi-Jun Chang and Da Wei Zheng. Fully scalable massively parallel algorithms for embedded planar graphs. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 4410–4450, 2024. doi:10.1137/ 1.9781611977912.155.

[DG04]

Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI 2004), pages 137–150, 2004. URL: https://www.usenix.org/ conference/osdi-04/mapreduce-simplified-data-processing-large-clusters.

[DG08]

Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008. doi:10.1145/1327452. 1327492.

[DMO+ 25] Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, and David P. Woodruff. Range counting oracles for geometric problems. In Proceedings of the 41st International Symposium on Computational Geometry (SoCG 2025), pages 42:1–42:16, 2025. doi:10.4230/LIPIcs.SoCG.2025.42. [Gha19]

Mohsen Ghaffari. Massively parallel algorithms. Lecture Notes from ETH Zurich, 2019. URL: http://people.csail.mit.edu/ghaffari/MPA19/Notes/MPA.pdf.

[Goo99]

Michael T. Goodrich. Communication-efficient parallel sorting. SIAM Journal on Computing, 29(2):416–432, 1999. doi:10.1137/S0097539795294141.

[GP68]

Edgar N. Gilbert and Henry O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1–29, 1968. doi:10.1137/0116001.

[GSZ11]

Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the MapReduce framework. In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), pages 374–383, 2011. doi: 10.1007/978-3-642-25591-5_39.

[GWZ25]

Junhao Gan, Anthony Wirth, and Zhuo Zhang. O(1)-round MPC algorithms for multidimensional grid graph connectivity, Euclidean MST and DBSCAN. In Proceedings of the 28th International Conference on Database Theory (ICDT 2025), pages 7:1–7:20, 2025. doi:10.4230/LIPIcs.ICDT.2025.7.

[HGNK20] Christoph Hofer, Florian Graf, Marc Niethammer, and Roland Kwitt. Topologically densified distributions. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), pages 4304–4313, 2020. URL: https://proceedings.mlr. press/v119/hofer20a.html. [HPS14]

James W. Hegeman, Sriram V. Pemmaraju, and Vivek B. Sardeshmukh. Nearconstant-time distributed algorithms on a Congested Clique. In Proceedings of the 28th International Symposium on Distributed Computing (DISC 2014), pages 514–530, 2014. doi:10.1007/978-3-662-45174-8_35.

[IBY+ 07]

Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 (EuroSys 2007), pages 59–72, 2007. doi:10.1145/1272996.1273005. 37

[JJLW26]

Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, and Weicheng Wang. Round-efficient fully-scalable MPC algorithms for k-means, 2026. arXiv:2604.00954, doi:10.48550/ arXiv.2604.00954.

[JL84]

William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in Modern Analysis and Probability, volume 26 of Contemporary Mathematics, pages 189–206, 1984. doi:10.1090/conm/026/737400.

[JLN+ 05]

Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for TSP, Steiner tree, and set cover. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pages 386–395, 2005. doi:10.1145/1060590.1060649.

[JMNZ24]

Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Massively parallel algorithms for high-dimensional Euclidean minimum spanning tree. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 3960–3996, 2024. doi:10.1137/1.9781611977912.139.

[KSV10]

Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 938–948, 2010. doi:10.1137/1.9781611973075.76.

[Lin24]

Andrzej Lingas. Boolean matrix multiplication for highly clustered data on the Congested Clique. In Proceedings of the 30th European Conference on Parallel Processing (Euro-Par 2024), pages 45–58, 2024. doi:10.1007/978-3-031-69583-4_4.

[LRN09]

Chih Lai, Taras Rafa, and Dwight E. Nelson. Approximate minimum spanning tree clustering in high-dimensional space. Intelligent Data Analysis, 13(4):575–597, 2009. doi:10.3233/IDA-2009-0382.

[MHRB20] Michael Moor, Max Horn, Bastian Rieck, and Karsten Borgwardt. Topological autoencoders. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), pages 7045–7054, 2020. URL: https://proceedings.mlr.press/v119/ moor20a.html. [MLKO25] Julie Mordacq, David Loiseaux, Vicky Kalogeiton, and Steve Oudot. T-REGS: minimum spanning tree regularization for self-supervised learning. In Proceedings of the 39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025), pages 12184–12214, 2025. doi:10.52202/085713-0408. [MRG10]

William B. March, Parikshit Ram, and Alexander G. Gray. Fast Euclidean minimum spanning tree: algorithm, analysis, and applications. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2010), pages 603–612, 2010. doi:10.1145/1835804.1835882.

[MRTV25] Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian. Sublinear metric Steiner tree via improved bounds for set cover. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), pages 74:1– 74:24, 2025. doi:10.4230/LIPIcs.ITCS.2025.74. [Now21]

Krzysztof Nowicki. A deterministic algorithm for the MST problem in constant rounds of Congested Clique. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021), pages 1154–1165, 2021. doi:10.1145/3406325.3451136. 38

[NS22]

Danupon Nanongkai and Michele Scquizzato. Equivalence classes and conditional hardness in massively parallel computations. Distributed Computing, 35(2):165–183, 2022. doi:10.1007/s00446-021-00418-2.

[OS26]

Eunjin Oh and Hyeonjun Shin. Fully scalable MPC algorithms for WSPD in doubling and Euclidean spaces. In Proceedings of the 34th Annual European Symposium on Algorithms (ESA 2026), pages 88:1–88:16, 2026. doi:10.4230/LIPIcs.ESA.2026.88.

[PS16]

Sriram V. Pemmaraju and Vivek B. Sardeshmukh. Super-fast MST algorithms in the Congested Clique using o(m) messages. In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), pages 47:1–47:15, 2016. doi:10.4230/LIPIcs.FSTTCS.2016.47.

[PvdB25]

Gryphon Patlin and Jan van den Brand. Sublinear-time algorithm for MST-weight revisited. In Proceedings of the 2025 Symposium on Simplicity in Algorithms (SOSA 2025), pages 46–53, 2025. doi:10.1137/1.9781611978315.3.

[SGM+ 24] Stephen-John Sammut, Jacob D. Galson, Ralph Minter, Bo Sun, Suet-Feung Chin, Leticia De Mattos-Arruda, Donna K. Finch, Sebastian Schätzle, Jorge Dias, Oscar M. Rueda, Joan Seoane, Jane Osbourn, Carlos Caldas, and Rachael J. M. Bashford-Rogers. Predictability of B cell clonal persistence and immunosurveillance in breast cancer. Nature Immunology, 25(5):916–924, 2024. doi:10.1038/ s41590-024-01821-0. [TCG+ 14] Cole Trapnell, Davide Cacchiarelli, Jonna Grimsby, Prapti Pokharel, Shuqiang Li, Michael Morse, Niall J. Lennon, Kenneth J. Livak, Tarjei S. Mikkelsen, and John L. Rinn. The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells. Nature Biotechnology, 32(4):381–386, 2014. doi:10.1038/nbt. 2859. [Whi12]

Tom White. Hadoop: the definitive guide. O’Reilly Media, Inc., 3rd edition, 2012. URL: https://www.oreilly.com/library/view/hadoop-the-definitive/ 9781449328917/.

[WHJ25]

Chilei Wang, Qiang-Sheng Hua, and Hai Jin. Massively parallel approximate Steiner tree algorithms. In Proceedings of the 31st International Computing and Combinatorics Conference (COCOON 2025), pages 110–124, 2025. doi:10.1007/ 978-981-95-0218-9_9.

[YTW+ 20] Xingyu Yang, Christopher M. Tipton, Matthew C. Woodruff, Enlu Zhou, F. EunHyung Lee, Iñaki Sanz, and Peng Qiu. GLaMST: grow lineages along minimum spanning tree for b cell receptor sequencing data. BMC Genomics, 21(Suppl 9):583, 2020. doi:10.1186/s12864-020-06936-w. [YV18]

Grigory Yaroslavtsev and Adithya Vadapalli. Massively parallel algorithms and hardness for single-linkage clustering under ℓp distances. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), pages 5600–5609, 2018. URL: https://proceedings.mlr.press/v80/yaroslavtsev18a.html.

39

A

Getting rid of the assumption on bounded spread

In the Euclidean and doubling cases, we assume polynomial spread on an input point set P of size n: the ratio Φ of the largest to the smallest nonzero pairwise distance is polynomial in n. The only place where this assumption is used is to apply consistent hashing. In particular, we construct consistent hashes with O(log Φ) different radius scales in parallel. Then the space complexity becomes O(n log Φ). In this section, we preprocess P so that this assumption is satisfied.

A.1

Euclidean space

In a d-dimensional Euclidean space, we can use a grid as follows. Fix an arbitrary point x ∈ P , and compute ∆ := maxp∈P dist(p, x) in O(1/σ) MPC rounds using O(dn) total space. Then consider a √ grid whose cells have diameter ∆/(n2 d). For every point p ∈ P , we move it to the center of the grid cell containing p. The error induced by the perturbation is at most ∆/n ≤ OPT(P )/n ≤ ε·OPT(P ) for sufficiently large n. In this way, the spread of the resulting point set becomes O(dn2 ) since its diameter is O(∆). Since d = O(log n), the resulting point set has polynomial spread. We retain only one copy of the center of each occupied grid cell. For each such cell C, we also choose an original point pC ∈ P ∩ C and associate its identifier with every point in C. We apply the algorithm in Section 6 to the distinct cell centers. Note that the additional space needed to duplicate the point set across all scales is O(nd log(dn2 )) ≤ O(n1+σ ), since d = O(log n). Therefore, without increasing the space complexity, we can get rid of the polynomial spread assumption. To obtain a spanning tree of P , we replace each tree edge between two cell centers by the edge between their chosen points, and connect every other point in each cell C to pC . Choosing these points and constructing the corresponding edges take O(1/σ) MPC rounds using Sorting, Aggregation, and Broadcasting, with O(nd) total space.

A.2

Doubling space

We show how to preprocess an n-point metric (X, dist) with doubling dimension d ≤ cσ log n, for a sufficiently small constant c > 0, so that the resulting point set has spread O(n8 ) with high probability. The error induced by the preprocessing is at most ε · OPT(X) for any fixed e approximation factor and sufficiently large n. The preprocessing uses O(n) total space, nσ local space per machine, and O(1) rounds for fixed σ. We assume that each point is represented by O(1) words and that its distance to another point can be computed from their representations. As in the Euclidean case, we assign points to representatives, apply the algorithm to the representatives, and then recover a spanning tree of the original point set. We fix an arbitrary point x ∈ X, and compute ∆ := maxp∈X dist(x, p). Then ∆ ≤ OPT(X) and the diameter of X is at most 2∆. Let τ = ∆/n2 and s = nσ . Recall that s is the size of the local space. Instead of computing a net, we adapt the construction of a partition cover tree introduced by Oh and Shin [OS26]. Algorithm. Starting with a single piece X, we process the remaining pieces in parallel in phases. √ For each piece U with |U | > s, take q = Θ(β s log2 n) independent uniform samples from U , keeping multiplicities, where β = 2O(d) is a sufficiently large integer. Since q ≤ s3/4 , we can store the samples in a single machine. On this machine, we recursively partition the sample using the balanced-ball rule: for the current nonempty sample multiset Y , find a smallest-radius ball B(z, r) centered at a point z in Y containing at least ⌈|Y |/β⌉ sampled points. If r > τ , choose the cut radius uniformly from [r, 2r] and recurse on both sides. Otherwise, cut with the ball B(z, τ ), make the inside a final part, and recurse only on the outside. We do this until every part either becomes a final 40

part, or contains a constant number of sample points. Finally, we obtain a partition of the sampled points into subsets. We represent the resulting partition by a recursion tree T whose internal nodes record the centers and radii of the cuts. Each leaf corresponds to the region determined by the cuts along its root-to-leaf path, including regions containing no sampled points. We broadcast T to all the machines holding U . We then partition U according to the recursion tree: each point p ∈ U follows the cuts from the root to a leaf of T , according to whether it lies inside or outside each ball, and is assigned to the piece corresponding to that leaf. For each final part, we choose the center of its τ -ball as its representative. For each other nonempty piece U ′ , if U ′ fits on one machine, we gather U ′ onto a single machine and repeatedly choose an arbitrary remaining point z ∈ U ′ and remove the points in B(z, τ ) from U ′ as a final part with representative z. Otherwise, we recursively process U ′ in the next phase. After O(1/σ) phases, report failure if there is a remaining piece. Otherwise, the final parts form a partition of X, with each part having a representative. Let X ′ be the set of all such representatives, and let f (p) be the representative of the part containing p. By construction, dist(p, f (p)) ≤ τ for every p ∈ X. Analysis. This algorithm is a simplified version of the algorithm in [OS26]. Their analysis immediately implies that our construction uses O(1/σ 2 ) rounds and O(n) total space. We analyze the error induced by the perturbation. The distance between two points increases by at most 2τ since dist(p, f (p)) ≤ τ for every p ∈ X by construction, so OPT(X ′ ) ≤ OPT(X) + 2nτ . Since OPT(X) ≥ ∆ = n2 τ , we have OPT(X ′ ) ≤ (1 + o(1)) · OPT(X). We show that the spread of X ′ is O(n8 ). For two distinct points of X ′ , consider the first cut separating them. There are two cases. In the first case, the cut is B(z, τ ). One representative is its center z and the other lies outside B(z, τ ), so their distance is greater than τ . In the second case, the cut is B(z, r′ ), where r′ is chosen uniformly from [r, 2r] with r > τ . Conditioned on the preceding choices, such a cut separates two fixed input points with probability at most their distance divided by τ . There are O(n) such cuts, since each splits a nonempty piece into two nonempty pieces. A union bound over these cuts and all input pairs shows that, with probability at least 1 − O(n−3 ), no pair at distance less than τ /n6 is separated by a random cut. Together with the sampling guarantee, distinct representatives are therefore at distance at least τ /n6 with high probability. Their maximum distance is at most 2∆, so the spread of X ′ is O(n8 ). Its doubling dimension is at most 2d. Once we can compute a 1 + ε-approximate MST of X ′ , then it yields a 1 + o(1) + ε-approximate MST of X.

B

Proof of Theorem 1.3 assuming Lemma 6.3

We first describe our algorithm. Let L = ⌈20/σ⌉, and keep b = nσ/10 fixed throughout the algorithm. Starting with P = Q0 , we repeatedly compute a (b, O(1))-randomized light partition. At level i, we are given a set Qi ⊆ P of representative points. Let (Ci , {TC }C∈Ci ) be a (b, O(1))randomized light partition of Qi obtained by using Lemma 6.3. We choose an arbitrary representative point per cluster in Ci , and let Qi+1 be the set of chosen representative points, which will be passed to the next level. Once nσ/2 representative points remain, we can construct their MST on a single machine. On every successful call, the number of points becomes O(m/b) + 1; while m > nσ/2 , this is at most m/nσ/20 for sufficiently large n. Thus L successful calls suffice. The union of the trees constructed at all levels forms a spanning tree on P . We denote it by T . We now show that T is an O(1)-approximate MST in expectation. Suppose that there are ℓ < L levels. For each 0 ≤ i ≤ ℓ, let mi = |Qi |. For every i < ℓ, the trees constructed within the clusters 41

in Ci form a spanning forest on Qi , and Qi+1 contains exactly one representative from each tree. Therefore, adding the spanning forest of Qi+1 merges those trees in the forest of Qi without creating P P a cycle, and thus T is a spanning tree of P . Note that |E(T )| = ℓ−1 i=0 ( C∈Ci (|C| − 1)) + (mℓ − 1) = Pℓ−1 i=0 (mi − mi+1 ) + (mℓ − 1) = n − 1. Consider an MST T ∗ of P and an Euler tour of the multigraph obtained by duplicating all edges of T ∗ . The length of the Euler tour is 2·ω(T ∗ ). For each 0 ≤ i ≤ ℓ, let (q1 , q2 , . . . , qmi ) be the points P i ∗ in Qi ordered by their first occurrence in the Euler tour. Then, m j=1 dist(qj , qj+1 ) ≤ 2 · ω(T ) by ∗ the triangle inequality, where qmi +1 = q1 . This implies that OPT(Qi ) ≤ 2 · ω(T ) = 2OPT(P ). At each executed level, the second property of a randomized light partition bounds the expected total weight of the cluster trees by O(OPT(Qi )), conditional on the preceding iterations and using fresh random choices at that level. Thus, summing over the O(1/σ) possible levels and including the final MST, we have E[ω(T )] = E

ℓ−1 X hX

i

ω(TC ) + OPT(Qℓ ) ≤ O((1/σ) · OPT(P )) + 2OPT(P ) = O((1/σ) · OPT(P )).

i=0 C∈Ci

Each iteration constructs a randomized light partition in O(ddim/σ 3 ) MPC rounds. Moreover, we can select representatives locally and update the representative and edge records in O(1/σ) MPC rounds. The MST on Qℓ is computed locally. Since there are ℓ = O(1/σ) iterations, the algorithm takes O(ddim/σ 4 ) MPC rounds in total. By the Markov inequality, the probability that ω(T ) > 2c · OPT(P ) is at most 1/2 for some constant c. Thus, by applying Algorithm 2 independently to O(log n) copies of P in parallel and returning the tree of minimum total weight, we can construct an O(1)-approximate MST with high probability. By reusing space across iterations, the bounds in Lemma 6.3 also give nσ local space e 1+σ · 2O(ddim) ) total space. per machine, and O(n

C

Proof of Lemma 6.5

Lemma 6.5. E[

z∈R hz ] = O(OPT(P )), where R denotes the set of the roots of the trees of F .

P

Proof. It suffices to show that the right-hand side of Equation (4) is O(OPT(P )). The second term of the right-hand side of the equation is O(OPT(P )) since F is contained in the MST of P . Hence, P we focus on proving C∈cc(F ) minv∈C hv = O(OPT(P )). If F has a single component, then C = P , and we have minv∈P hv ≤ εγ 50 · maxx,y∈P dist(x, y) = O(OPT(P )) by Lemma 6.4. Otherwise, let T be the MST of P from Prim’s algorithm. For a component C of F , we can choose an edge (u, v) ∈ E(T ) with u ∈ C and v ∈ P \ C. If v ∈ / Su , hu ≤ εr̂u /100 < dist(u, v)/100. Consider the call TruncatedPrim(u, Su , εr̂u /2, 0). The tree visited by this call is contained in F [C]. There are three cases when the subroutine terminates: either the total weight of the edges and vertices visited by the call is at least εr̂u /2, the next edge has length at least εr̂u /2, or all vertices in Su are visited. In the first case, ω(F [C]) ≥ εr̂u /2, and thus 50 · hu ≤ εr̂u /2 ≤ ω(F [C]) by Lemma 6.4. In the second case, 50 · hu ≤ εr̂u /2 ≤ dist(u, v). In the third case, dist(u, v) > εr̂u since B(u, εr̂u ) ∩ P ⊆ Su . Thus, in all four cases, 50 · hu ≤ ω(F [C]) + dist(u, v). We then have X C∈cc(F )

min hv ≤ v∈C

1 1 X (ω(F [C]) + dist(uC , vC )) ≤ (ω(F ) + 2ω(T )) = O(OPT(P )), 50 C∈cc(F ) 50

where (uC , vC ) is the edge in T chosen for C. The second inequality holds since each edge (u, v) of T is chosen in at most two components of F : one containing u and one containing v. 42

Related documents

• On the Metric Distortion of the Minimum Spanning Tree Problem#1387321
• Closure complexity of Bänsch-type algorithms for tetrahedral mesh refinement#1077544
• On the Support Geometry and Complexity of LABS#1402717
• Algorithms for Computational Biology#67319
• Bidirectional Dijkstra's Algorithm is Instance-Optimal#1014476