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 [41 , 53 ] . In particular, MST-based clustering has been used to identify structures in astronomical data [41 , 3 ] and to cluster high-dimensional datasets in machine learning [38 ] . MSTs also find applications in biology [49 YTW+20, 48 ] as well as in representation learning [29 , 39 , 40 ] .
Such applications often involve processing large data sets. This motivates the use of modern distributed computing frameworks such as MapReduce, Spark, Hadoop, and Dryad [22 , 21 , 50 , 31 ] . 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 [36 ] , 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 [1 , 5 , 8 , 11 , 24 , 53 ] .
In the MPC model, the input of N N N words is distributed across m m m machines, each with s s s words of local memory, giving a total memory of m ⋅ s m \cdot s 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 ) O(s) O ( s ) words. The primary complexity measures of an MPC algorithm are its round complexity, local memory s s s , and the total space m ⋅ s m \cdot s m ⋅ s . In this work, we consider the fully scalable regime where s = N σ s = N^\sigma s = N σ for an arbitrary fixed constant σ ∈ ( 0 , 1 ) \sigma\in(0, 1) σ ∈ ( 0 , 1 ) . Our goal is to minimize the number of rounds, ideally achieving O ( 1 ) O(1) 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 ) O(\log n) O ( log n ) rounds in the fully scalable regime [4 , 6 , 11 ] . However, under the 1-vs-2-cycles conjecture, even computing an approximate MST in a general edge-weighted graph requires Ω ( log n ) \Omega(\log n) Ω ( 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 [2 , 28 , 17 , 1 , 35 ] . A natural question in this direction is whether approximate MSTs can be computed in o ( log n ) o(\log n) 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 = Θ ( n 2 ) N = \Theta(n^2) N = Θ ( n 2 ) . In contrast, in the Euclidean setting, the input consists of the coordinates of n n n points in R d \mathbb{R}^d R d , requiring only Θ ( n d ) \Theta(nd) Θ ( n d ) words. In the doubling metric setting, we assume that each point has an O ( 1 ) O(1) O ( 1 ) -word representation from which pairwise distances can be computed locally, resulting in an input size of Θ ( n ) \Theta(n) Θ ( n ) . Therefore, directly applying MPC algorithms for general metrics to Euclidean and doubling metric spaces may not achieve the desired total space complexity.
Previous work. We review the best-known prior MPC results for MSTs in various metric settings. In the following, we sometimes treat σ \sigma σ and ε \varepsilon ε as fixed constants. Instead, we indicate any hidden dependence on these parameters by subscripts in the O ( ⋅ ) O(\cdot) O ( ⋅ ) notation.
For low-dimensional Euclidean spaces, Andoni, Nikolov, Onak, and Yaroslavtsev [2 ] presented a randomized O σ ( 1 ) O_{\sigma}(1) O σ ( 1 ) -round MPC algorithm that constructs a ( 1 + ε ) (1+\varepsilon) ( 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 ) O(1) O ( 1 ) -dimensional case, their analysis also applies to higher dimensions: d = O ε ( σ log n / log log n ) d = O_{\varepsilon}(\sigma\log n / \log\log n) d = O ε ( σ log n / log log n ) in Euclidean spaces and ddim = O ε ( σ log n ) \operatorname{ddim} = O_{\varepsilon}(\sqrt{\sigma\log n}) ddim = O ε ( σ log n ) in doubling metrics, using O ( n σ ) O(n^{\sigma}) 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, [12 ] presented an MPC algorithm that estimates the MST cost within a factor of ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) in O σ , ε ( 1 ) O_{\sigma,\varepsilon}(1) O σ , ε ( 1 ) rounds using O ( n d ) O(nd) O ( n d ) 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 ) O_{\sigma}(\log n) 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 [35 ] broke this O ( log n ) O(\log n) O ( log n ) barrier by presenting an O σ ( log log n ⋅ log log log n ) O_{\sigma}(\log\log n \cdot\log\log\log n) O σ ( log log n ⋅ log log log n ) -round MPC algorithm that constructs an O σ ( 1 ) O_{\sigma}(1) O σ ( 1 ) -approximate MST using O ( n d + n 1 + σ ) O(nd+n^{1+\sigma}) O ( n d + n 1 + σ ) total space.
For general metric spaces, [1 ] gave a randomized O σ ( log ( 1 / ε ) + log log n ) O_{\sigma}(\log(1/\varepsilon)+\log\log n) O σ ( log ( 1/ ε ) + log log n ) -round MPC algorithm that constructs a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate MST using O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) total space. The total space is thus near-linear in the input size. Under the 1-vs-2-cycles conjecture, they also proved that any MPC algorithm with n 1 − Ω ( 1 ) n^{1-\Omega(1)} n 1 − Ω ( 1 ) local space and polynomial total space requires Ω ( log ( 1 / ε ) ) \Omega(\log(1/\varepsilon)) Ω ( log ( 1/ ε )) rounds to construct a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate MST in a general metric space, for 1 / n ≤ ε ≤ 1 1/n \le\varepsilon\le1 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 ε \varepsilon ε . This raises the following question, which was also explicitly posed in [12 , 32 ] :
Can one construct approximate MSTs in both general metric spaces and high-dimensional Euclidean spaces in O ( 1 ) O(1) 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 [35 ] and of [1 ] 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 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . There is an O ( log ( 1 / ( ε σ ) ) / σ 2 ) O(\log(1/(\varepsilon\sigma))/\sigma^2) O ( log ( 1/ ( ε σ )) / σ 2 ) -round randomized MPC algorithm that, given all pairwise distances of an n n n -point metric ( X , dist ) (X,\operatorname{dist}) ( X , dist ) , returns a spanning tree of X X X whose total weight is at most ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) times the weight of a minimum spanning tree of ( X , dist ) (X,\operatorname{dist}) ( X , dist ) . The algorithm succeeds with probability at least 1 − n − Ω ( 1 ) 1-n^{-\Omega(1)} 1 − n − Ω ( 1 ) and uses n σ n^\sigma n σ local space per machine and O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) total space.
Theorem 1.2. Fix a constant σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) . There is an O ( 1 / σ 2 ) O(1/\sigma^2) O ( 1/ σ 2 ) -round randomized MPC algorithm that, given a set P P P of n n n points in R d \mathbb{R}^{d} R d , returns a spanning tree of P P P whose total weight is O ( 1 / σ 4 ) O(1/\sigma^4) O ( 1/ σ 4 ) times the weight of a minimum spanning tree of P P P . The algorithm succeeds with probability at least 1 − n − Ω ( 1 ) 1-n^{-\Omega(1)} 1 − n − Ω ( 1 ) and uses ( d n ) σ (dn)^{\sigma} ( d n ) σ local space per machine and O ( n d + n 1 + σ ) O(nd+n^{1+\sigma}) O ( n d + n 1 + σ ) total space.
Theorem 1.3. Fix a constant σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) . There is an O ( ddim / σ 4 ) O(\operatorname{ddim}/\sigma^4) O ( ddim / σ 4 ) -round randomized MPC algorithm that, given a set P P P of n n n points in a metric space with doubling dimension ddim \operatorname{ddim} ddim satisfying σ log n ≥ Ω ( ddim ) \sigma\log n\ge\Omega(\operatorname{ddim}) σ log n ≥ Ω ( ddim ) , returns a spanning tree of P P P whose total weight is O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) times the weight of a minimum spanning tree of P P P . The algorithm succeeds with probability at least 1 − n − Ω ( 1 ) 1-n^{-\Omega(1)} 1 − n − Ω ( 1 ) and uses n σ n^{\sigma} n σ local space per machine and O ~ ( n 1 + σ ) ⋅ 2 O ( ddim ) \widetilde{O}(n^{1+\sigma})\cdot2^{O(\operatorname{ddim})} O ( n 1 + σ ) ⋅ 2 O ( ddim ) total space.
Table 1 compares our algorithms with previous MPC algorithms for metric MSTs. For general metrics, we remove the additive O σ ( log log n ) O_{\sigma}(\log\log n) O σ ( log log n ) term in the round complexity of Azarmehr, Behnezhad, Jayaram, Łącki, Mirrokni, and Zhong [1 ] . For high-dimensional Euclidean spaces, we improve the O σ ( log log n ⋅ log log log n ) O_{\sigma}(\log\log n\cdot\log\log\log n) O σ ( log log n ⋅ log log log n ) -round bound of Jayaram, Mirrokni, Narayanan, and Zhong [35 ] to O σ ( 1 ) O_{\sigma}(1) O σ ( 1 ) rounds. For doubling metrics, we extend the dimension range from O ε ( σ log n ) O_{\varepsilon}(\sqrt{\sigma\log n}) O ε ( σ log n ) in [2 ] to O ( σ log n ) O(\sigma\log n) O ( σ log n ) while retaining O σ ( ddim ) O_{\sigma}(\operatorname{ddim}) O σ ( ddim ) rounds. On the other hand, the approximation ratio becomes O σ ( 1 ) O_{\sigma}(1) O σ ( 1 ) while the approximation ratio of [2 ] is 1 + ε 1+\varepsilon 1 + ε .
Table 1. Comparison of previous and our results. The local space per machine is n σ n^{\sigma} n σ for general and doubling metrics and ( n d ) σ (nd)^{\sigma} ( n d ) σ for Euclidean spaces, except that [12 ] uses d O ( 1 ) n σ d^{O(1)}n^{\sigma} d O ( 1 ) n σ local space. The sixth column with label “Tree?” indicates whether the algorithms return an actual spanning tree.
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 ) \Omega(\log n) Ω ( log n ) rounds in the worst case in the fully scalable MPC model [35 ] . We instead use a hierarchical structure of an approximate MST constructed during our MST algorithms to compute an Euler tour. This gives a ( 2 + ε ) (2+\varepsilon) ( 2 + ε ) -approximation in general metric spaces and an O σ ( 1 ) O_{\sigma}(1) 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 § 7 .
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 [18 ] . For a threshold t t t , two points are adjacent in the threshold graph if their distance is at most t t t . By Kruskal’s algorithm, the number of MST edges longer than t t t is exactly one less than the number of connected components of the threshold graph at t t t . Thus, by counting the connected components at thresholds 1 , ( 1 + ε ) , ( 1 + ε ) 2 , … 1,(1+\varepsilon),(1+\varepsilon)^2,\ldots 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 [18 , 19 , 13 , 23 , 12 ] . 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 [1 , 35 ] .
We instead take a different approach based on Prim’s algorithm, inspired by [47 , 7 ] . In particular, [7 ] presented an O ( 1 ) O(1) 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 Prim-based 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 Ω ( σ ) n^{\Omega(\sigma)} n Ω ( σ ) , and thus the algorithm terminates in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) phases. A more detailed technical overview can be found in Section 3.
Preliminaries
Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) be a metric space on n n n points. The doubling dimension of ( X , dist ) (X,\operatorname{dist}) ( X , dist ) is defined as the smallest value d d d such that every ball of radius r > 0 r > 0 r > 0 can be covered by at most 2 d 2^d 2 d balls of radius r / 2 r/2 r /2 . It is known that the doubling dimension of R d \mathbb{R}^d R d is Θ ( d ) \Theta(d) Θ ( d ) . When we speak about doubling metrics, we treat the doubling dimension ddim \operatorname{ddim} ddim as a parameter; we do not assume that it is constant. For two nonempty subsets A , B ⊆ X A, B \subseteq X A , B ⊆ X , we define dist ( A , B ) = min a ∈ A , b ∈ B dist ( a , b ) \operatorname{dist}(A,B) = \min_{a \in A,b \in B} \operatorname{dist}(a,b) dist ( A , B ) = min a ∈ A , b ∈ B dist ( a , b ) . Note that these distances need not satisfy the triangle inequality. We sometimes consider the metric ( X , dist ) (X,\operatorname{dist}) ( X , dist ) as the complete graph with vertex set X X X and edge weight dist ( ⋅ , ⋅ ) \operatorname{dist}(\cdot,\cdot) dist ( ⋅ , ⋅ ) . For a graph G = ( V , E ) G = (V,E) G = ( V , E ) , we use V ( G ) V(G) V ( G ) and E ( G ) E(G) E ( G ) to denote the vertex set and the edge set of G G G , respectively. For a finite set Z Z Z , we use ∣ Z ∣ |Z| ∣ Z ∣ to denote the cardinality of Z Z Z . We sometimes abuse notation and use ∣ G ∣ |G| ∣ G ∣ to denote the total number of edges and vertices of G G G . We use OPT ( X ) \operatorname{OPT}(X) OPT ( X ) to denote the MST cost of X X X . If it is clear from context, we simply write OPT \operatorname{OPT} 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 \lambda> 0 λ > 0 , the exponential distribution with rate λ \lambda λ , denoted by Exp ( λ ) \operatorname{Exp}(\lambda) Exp ( λ ) , is the distribution on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) with probability density function f ( t ) = λ e − λ t f(t) = \lambda e^{-\lambda t} f ( t ) = λ e − λ t for t ≥ 0 t \geq0 t ≥ 0 . In this paper, we use the following standard property of exponential random variables. If X 1 , … , X m X_1,\ldots,X_m X 1 , … , X m are independent random variables with X i ∼ Exp ( λ i ) X_i \sim\operatorname{Exp}(\lambda_i) X i ∼ Exp ( λ i ) , then for any A ⊆ { 1 , … , m } A \subseteq\{1,\ldots,m\} A ⊆ { 1 , … , m } , the probability that arg min 1 ≤ i ≤ m X i \arg\min_{1 \leq i \leq m} X_i arg min 1 ≤ i ≤ m X i belongs to A A A is ∑ i ∈ A λ i / ∑ i = 1 m λ i \sum_{i \in A}\lambda_i / \sum_{i=1}^m \lambda_i ∑ i ∈ A λ i / ∑ i = 1 m λ i .
MPC primitives. The following standard primitives can be done in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using n σ n^\sigma n σ local space per machine and total space linear in the number of input and output records [25 , 27 ] . Here, each record consists of O ( 1 ) O(1) O ( 1 ) words, and the number of input and output records is polynomial in n n 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 S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k and each record in S j S_j S j is stored together with j j j , we can also compute its rank within S j S_j S j 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 v 1 , … , v t v_1,\ldots,v_t v 1 , … , v t distributed across machines, with each value v i v_i v i stored together with its index i i i , we can compute the prefix sum ∑ j = 1 i v j \sum_{j=1}^i v_j ∑ j = 1 i v j or the prefix minimum min 1 ≤ j ≤ i v j \min_{1 \leq j \leq i} v_j min 1 ≤ j ≤ i v j for every i i i and store the result together with v i v_i v i on its original machine. For a prefix minimum, we can also return an index attaining the minimum together with any O ( 1 ) O(1) 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 ) (k,v) ( k , v ) distributed across machines, we can compute the sum, minimum, or maximum of the values v v v for each key k k 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 ) (k,v) ( k , v ) with one value v v v for each key k k k , and requests ( k , i ) (k,i) ( k , i ) distributed across machines, where i i i is a machine ID, we can send a copy of v v v to machine i i i for every request ( k , i ) (k,i) ( k , i ) . We assume that each machine is the destination of at most O ( n σ ) O(n^\sigma) O ( n σ ) requests. All copies are included in the output size.
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 [34 ] . A consistent hash φ : X → I \varphi: X \to\mathcal{I} φ : X → I for an index set I \mathcal{I} I induces a partition of X X X into clusters of diameter at most Δ \Delta Δ such that for any two points x , y ∈ X x,y \in X x , y ∈ X , they are contained in the same cluster if and only if φ ( x ) = φ ( y ) \varphi(x) = \varphi(y) φ ( x ) = φ ( y ) .
Definition 2.1 ([16 Definition 1.6] , [8 Definition 1] ). Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) be a metric space, I \mathcal{I} I an index set, and Δ > 0 \Delta> 0 Δ > 0 . For a distribution H \mathcal{H} H over mappings X → I X \to\mathcal{I} X → I , let supp ( H ) \operatorname{supp}(\mathcal{H}) supp ( H ) denote the set of mappings that can be sampled from H \mathcal{H} H . A random mapping φ ∼ H \varphi\sim\mathcal{H} φ ∼ H is a ( Γ , Λ ) (\Gamma,\Lambda) ( Γ , Λ ) -hash with diameter bound Δ \Delta Δ if:
[Diameter] every cluster of every φ ∈ supp ( H ) \varphi\in\operatorname{supp}(\mathcal{H}) φ ∈ supp ( H ) has diameter at most Δ \Delta Δ .
[Consistency] for every X ′ ⊆ X X' \subseteq X X ′ ⊆ X with diameter at most Δ / Γ \Delta/\Gamma Δ/Γ , we have E φ ∼ H [ ∣ φ ( X ′ ) ∣ ] ≤ Λ \mathbb{E}_{\varphi\sim\mathcal{H}}[|\varphi(X')|] \leq\Lambda E φ ∼ H [ ∣ φ ( X ′ ) ∣ ] ≤ Λ .
For Euclidean spaces, Czumaj, Filtser, Jiang, Krauthgamer, Veselý, and Yang [14 , 16 ] showed that there is a deterministic hash φ : R d → R d \varphi: \mathbb{R}^{d} \to\mathbb{R}^{d} φ : R d → R d whose description requires poly ( d ) \operatorname{poly}(d) poly ( d ) space. Following [15 ] , we use this hash φ \varphi φ so that each machine can evaluate it locally without communication. The geometric aggregation algorithm in [15 ] provides the following lemma.
Lemma 2.2 ([15 ] ). Let σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) be a fixed constant, and let P ⊆ R d P \subseteq\mathbb{R}^{d} P ⊆ R d be a set of n n n points with d = O ( log n ) d = O(\log n) d = O ( log n ) . For any Δ > 0 \Delta> 0 Δ > 0 , there exists a ( Γ , n σ / 2 ) (\Gamma,n^{\sigma/2}) ( Γ , n σ /2 ) -hash φ \varphi φ with diameter bound Δ \Delta Δ and Γ = O ( 1 / σ ) \Gamma= O(1/\sigma) Γ = O ( 1/ σ ) , whose description and evaluation require poly ( d ) \operatorname{poly}(d) 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 Γ ) ) ) ) P \cap\varphi^{-1}(\varphi(B(x,\Delta/(2\Gamma)))) P ∩ φ − 1 ( φ ( B ( x , Δ/ ( 2Γ )))) for every x ∈ P x \in P x ∈ P in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) rounds using n σ n^{\sigma} n σ local space per machine and O ( n d + n 1 + σ ) O(nd+n^{1+\sigma}) O ( n d + n 1 + σ ) total space.
For doubling metrics, Bhore, Filtser, Oh, Shin, and Singh [8 ] construct a randomized consistent hash from the input points, together with approximate neighborhood hash pairs. For Γ > 0 \Gamma> 0 Γ > 0 and a hash φ : P → I \varphi: P \to\mathcal{I} φ : P → I with diameter bound Δ \Delta Δ , a set P ~ φ ⊆ P × I \widetilde{P}_{\varphi} \subseteq P \times\mathcal{I} P φ ⊆ P × I is a set of approximate neighborhood hash pairs if ( x , φ ( y ) ) ∈ P ~ φ (x,\varphi(y)) \in\widetilde{P}_{\varphi} ( x , φ ( y )) ∈ P φ whenever x , y ∈ P x,y \in P x , y ∈ P and dist ( x , y ) ≤ Δ / Γ \operatorname{dist}(x,y) \leq\Delta/\Gamma dist ( x , y ) ≤ Δ/Γ , and φ − 1 ( q ) ⊆ B ( x , 2 Δ ) \varphi^{-1}(q) \subseteq B(x,2\Delta) φ − 1 ( q ) ⊆ B ( x , 2Δ ) for every ( x , q ) ∈ P ~ φ (x,q) \in\widetilde{P}_{\varphi} ( x , q ) ∈ P φ . For each x ∈ P x \in P x ∈ P , define A P ( x , Δ / Γ ) = ⋃ ( x , q ) ∈ P ~ φ φ − 1 ( q ) A_{P}(x,\Delta/\Gamma) = \bigcup_{(x,q)\in\widetilde{P}_{\varphi}}\varphi^{-1}(q) A P ( x , Δ/Γ ) = ⋃ ( x , q ) ∈ P φ φ − 1 ( q ) . Then B ( x , Δ / Γ ) ∩ P ⊆ A P ( x , Δ / Γ ) ⊆ B ( x , 2 Δ ) ∩ P B(x,\Delta/\Gamma) \cap P \subseteq A_{P}(x,\Delta/\Gamma) \subseteq B(x,2\Delta) \cap P B ( x , Δ/Γ ) ∩ P ⊆ A P ( x , Δ/Γ ) ⊆ B ( x , 2Δ ) ∩ P . Their result gives the following lemma.
Lemma 2.3 ([8 ] ). Let σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) be a fixed constant, and let ( P , dist ) (P,\operatorname{dist}) ( P , dist ) be an n n n -point metric space with polynomially bounded aspect ratio and doubling dimension ddim ≤ c σ log n \operatorname{ddim} \leq c\sigma\log n ddim ≤ c σ log n for a sufficiently small constant c > 0 c > 0 c > 0 . Given Δ > 0 \Delta> 0 Δ > 0 and Γ ≥ 16 \Gamma\geq16 Γ ≥ 16 , we can construct a ( Γ , 2 O ( ddim / Γ ) ) (\Gamma,2^{O(\operatorname{ddim}/\Gamma)}) ( Γ , 2 O ( ddim /Γ ) ) -hash φ \varphi φ with diameter bound Δ \Delta Δ and a set of approximate neighborhood hash pairs P ~ φ \widetilde{P}_{\varphi} P φ of size O ( n ⋅ 2 O ( ddim / Γ ) ) O(n\cdot2^{O(\operatorname{ddim}/\Gamma)}) O ( n ⋅ 2 O ( ddim /Γ ) ) , with high probability, in O ( ddim / σ 3 ) O(\operatorname{ddim}/\sigma^{3}) O ( ddim / σ 3 ) rounds using n σ n^{\sigma} n σ local space and O ~ ( n ) ⋅ 2 O ( ddim / Γ ) \widetilde{O}(n)\cdot2^{O(\operatorname{ddim}/\Gamma)} O ( n ) ⋅ 2 O ( ddim /Γ ) total space.
Technical overview
In this section, we give an overview of our algorithms for constructing approximate minimum spanning trees for a metric ( X , dist ) (X,\operatorname{dist}) ( X , dist ) on n n 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 ( n d + n 1 + σ ) O(nd+n^{1+\sigma}) O ( n d + n 1 + σ ) and O ~ ( n 1 + σ ) ⋅ 2 O ( ddim ) \widetilde{O}(n^{1+\sigma})\cdot2^{O(\operatorname{ddim})} O ( n 1 + σ ) ⋅ 2 O ( ddim ) total space, respectively.
Our starting point differs from that of previous work [35 , 1 ] , which uses a threshold-graph-based approach. Motivated by the use of the Prim algorithm for the MST problem in sublinear models [47 , 7 ] , we ask whether a Prim-based approach can be used to construct an approximate MST in the MPC model. For each point x ∈ X x \in X x ∈ X , let S x S_x S x be the set of the n σ n^\sigma n σ points in X X X closest to x x x , including x x x . We run the Prim algorithm starting from x x x on the points in S x S_x S x on a single machine. Since this computation ignores points outside S x S_x S x , it may select edges that do not belong to an MST of X X X . To avoid this, we set τ x : = 1 2 max y ∈ S x dist ( x , y ) \tau_x := \frac{1}{2} \max_{y \in S_x} \operatorname{dist}(x,y) τ x := 2 1 max y ∈ S x dist ( x , y ) . Every point outside S x S_x S x is at distance at least 2 τ x 2\tau_x 2 τ x from x x x . We stop the local computation when the total weight of the current tree reaches τ x \tau_x τ x or the next edge has weight at least τ x \tau_x τ 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 X X , and therefore, using the same tie-breaking rule in all runs, all selected edges belong to the same MST of X X X . We call this procedure TruncatedPrim. Let F F F be the forest on X X X whose edges are the union of the edges selected from all points x ∈ X x \in X x ∈ X .
Does F F F really help? The forest F F F would be useful if it had at most n 1 − σ n^{1-\sigma} n 1 − σ components each with O ( n σ ) O(n^\sigma) O ( n σ ) vertices, and if each component could be identified and gathered on a single machine in O ( 1 ) O(1) 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 n 1 − σ n^{1-\sigma} n 1 − σ vertices. If such a reduction decreases the number of vertices by a factor of n σ n^\sigma n σ at every step, we could repeat it for O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) steps to obtain an exact MST in a general metric and an O ( 1 / σ ) O(1/\sigma) 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 n 1 − σ n^{1-\sigma} n 1 − σ groups of n σ n^\sigma n σ equally spaced points each, where consecutive groups are sufficiently far. For each point x x x , the set S x S_x S x consists of the points in its group. Then the components of F F F are precisely the groups. Thus we may safely reduce the instance size in this case.
In general, however, F F 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 n n points are equally spaced on a line. In this case, F F F can be a single path on all n n 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 1 1 , then τ x = 1 / 2 \tau_x = 1/2 τ x = 1/2 for every x x x . The first candidate edge in each local computation has length 1 1 1 , so no edge is selected. In this case, F F 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 [10 ] . Instead, we cut F F 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 x 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 n n . We connect each unsampled component to 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 x x , its neighborhood S x S_x S x intersects a sampled component with high probability, so the edge added for this component has weight at most 2 τ x 2\tau_x 2 τ x . To see why the total cost is small, choose a representative with the minimum threshold in each component of F F 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 ( O P T ) O(\mathrm{OPT}) O ( OPT ) .5 This implies that the expected total weight of the added edges is also O ( O P T ) O(\mathrm{OPT}) 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 \tau_x τ x for the representatives x x x to ε O P T \varepsilon\mathrm{OPT} ε 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.
Forest cutting (for the first iteration)
Let F F F be the forest obtained by running TruncatedPrim from every vertex x ∈ X x \in X x ∈ X . The edges of F F F are distributed across the machines. For each x ∈ X x \in X x ∈ X , one machine stores the neighborhood S x S_x S x and the subgraph of F F F induced by S x S_x S x . Our goal is to remove edges from F F F so that each vertex can identify the root of its resulting tree using local information, while the expected sum of the thresholds τ x \tau_x τ x over the roots x x x is O ( O P T ) O(\mathrm{OPT}) O ( OPT ) . The forest cutting algorithm consists of two steps. Both steps use the following property, which follows from the definition of τ x \tau_x τ x and the triangle inequality.
Property 3.1. For any x , y ∈ X x,y \in X x , y ∈ X , we have ∣ τ x − τ y ∣ ≤ dist ( x , y ) / 2 |\tau_x-\tau_y| \le\operatorname{dist}(x,y)/2 ∣ τ 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 x x , choose the vertex v ( x ) v(x) v ( x ) with the lexicographically smallest identifier among the vertices at distance at most τ x / 4 \tau_x/4 τ x /4 from x x x in F F F , where distance in F F F is the total weight of the edges on the path. If v ( x ) ≠ x v(x) \ne x v ( x ) = x , orient the first edge on the path from x x x to v ( x ) v(x) v ( x ) towards v ( x ) v(x) v ( x ) . Since the size of S x S_x S x is small, v ( x ) v(x) v ( x ) and the first edge can be computed locally. After all vertices make their choices in F F 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 ) (x,y) ( x , y ) is oriented in opposite directions. By Property 3.1, v ( x ) v(x) v ( x ) lies within the search region of y y y and v ( y ) v(y) v ( y ) lies within the search region of x x x . The choice of the smallest identifier then implies v ( x ) = v ( y ) v(x)=v(y) 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 k k vertices has k − 1 k-1 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.
For forest merging, we need to show that the sum of τ x \tau_x τ x for the roots is O ( OPT ) O(\operatorname{OPT}) O ( OPT ) . Each root x x x chooses itself as v ( x ) v(x) v ( x ) ; therefore, no vertex with a smaller identifier lies within distance τ x / 4 \tau_x/4 τ x /4 from x x x in F F F . Together with Property 3.1, this implies that the neighborhoods in F F F of radius τ x / 16 \tau_x/16 τ x /16 centered at the roots x x x are pairwise disjoint. For the analysis, view each edge of F F F as a line segment of length equal to its weight. For each original component of F F F before Step 1, consider paths π x \pi_x π x from the roots x x x produced by Step 1 in that component towards a vertex u u u of minimum threshold in the component, stopping each path from a root x x x at that vertex or at distance τ x / 16 \tau_x/16 τ x /16 from x x x , whichever comes first. The stopping point may lie in the interior of an edge. Since these path segments π x \pi_x π x are disjoint, their total length is at most the weight of F F F . If π x \pi_x π x has length τ x / 16 \tau_x/16 τ x /16 , we charge τ x \tau_x τ x to the length of π x \pi_x π x . Otherwise, π x \pi_x π x reaches u u u , and Property 3.1 implies that τ x = O ( τ u ) \tau_x = O(\tau_u) τ x = O ( τ u ) . As the paths are disjoint, at most one path in each component reaches u u u ; we charge its threshold to τ u \tau_u τ u . The weight of F F F is O ( OPT ) O(\operatorname{OPT}) O ( OPT ) because F F F is contained in an MST, and the sum of the minimum thresholds of the original components of F F F is O ( OPT ) O(\operatorname{OPT}) O ( OPT ) by the stopping condition of TruncatedPrim. This implies that the sum of τ x \tau_x τ x for all roots is O ( OPT ) O(\operatorname{OPT}) 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 x x , the path in F F F from x x x to its root lies in S x S_x S x , while the expected sum of τ x \tau_x τ x over all roots remains O ( OPT ) O(\operatorname{OPT}) O ( OPT ) . If so, x x 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 x x , let π x ′ \pi'_x π x ′ be the path of length τ x / 8 \tau_x/8 τ x /8 starting at x x 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 x x after cutting must lie on π x ′ \pi'_x π x ′ . Second, each edge ( v , p ( v ) ) (v,p(v)) ( v , p ( v )) is cut with probability O ( dist ( v , p ( v ) ) / τ v ) O(\operatorname{dist}(v,p(v))/\tau_v) O ( dist ( v , p ( v )) / τ v ) , where p ( v ) p(v) p ( v ) denotes the parent of v v v in F F F . The first property allows x x x to identify its root locally. For the second, cutting ( v , p ( v ) ) (v,p(v)) ( v , p ( v )) makes v v v a new root, and its expected contribution to the sum of τ x \tau_x τ x for all roots is O ( τ v ⋅ dist ( v , p ( v ) ) / τ v ) = O ( dist ( v , p ( v ) ) ) O(\tau_v \cdot\operatorname{dist}(v,p(v))/\tau_v)=O(\operatorname{dist}(v,p(v))) O ( τ v ⋅ dist ( v , p ( v )) / τ v ) = O ( dist ( v , p ( v ))) .
We start with the following observation. For every edge ( v , p ( v ) ) (v,p(v)) ( v , p ( v )) , Property 3.1 implies that the total length of the portions belonging to exactly one of π v ′ \pi'_v π v ′ and π p ( v ) ′ \pi'_{p(v)} π p ( v ) ′ is at most 3 dist ( v , p ( v ) ) 3\operatorname{dist}(v,p(v)) 3 dist ( v , p ( v )) . Since the union of the two paths has length at least τ v / 8 \tau_v/8 τ v /8 , the fraction of the union that belongs to exactly one path is at most min { 1 , 24 dist ( v , p ( v ) ) / τ v } \min\{1,24\operatorname{dist}(v,p(v))/\tau_v\} min { 1 , 24 dist ( v , p ( v )) / τ v } . For example, if dist ( v , p ( v ) ) ≤ τ v / 48 \operatorname{dist}(v,p(v)) \le\tau_v/48 dist ( v , p ( v )) ≤ τ v /48 , the two paths share at least half their length. For each edge ( v , p ( v ) ) (v,p(v)) ( v , p ( v )) , we can design a cutting scheme so that the probability of cutting the edge is at most the fraction of π v ′ ∪ π p ( v ) ′ \pi'_v \cup\pi'_{p(v)} π v ′ ∪ π p ( v ) ′ belonging to exactly one of the two paths, which gives the desired bound of O ( dist ( v , p ( v ) ) / τ v ) O(\operatorname{dist}(v,p(v))/\tau_v) O ( dist ( v , p ( v )) / τ v ) .
To see how this observation can be useful, focus on the two paths π v ′ \pi'_v π v ′ and π p ( v ) ′ \pi'_{p(v)} π 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 ℓ \ell ℓ receives an independent random key drawn from Exp ( ℓ ) \operatorname{Exp}(\ell) Exp ( ℓ ) , and each endpoint chooses the smallest key on its path. Then v v v and p ( v ) p(v) 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 I I an independent random key drawn from Exp ( ℓ ( I ) ) \operatorname{Exp}(\ell(I)) Exp ( ℓ ( I )) , where ℓ ( I ) \ell(I) ℓ ( I ) is the length of I I I . Specifically, the fragments are the finite segments obtained by subdividing each edge and ray at the endpoints of the paths π x ′ \pi'_x π x ′ for all vertices x x x . We 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 x x takes the label of the fragment with the smallest key on π x ′ \pi'_x π x ′ . We cut an edge if its endpoints have different labels. By the argument above, the probability that a fixed edge ( v , p ( v ) ) (v,p(v)) ( v , p ( v )) is cut is O ( dist ( v , p ( v ) ) / τ v ) O(\operatorname{dist}(v,p(v))/\tau_v) O ( dist ( v , p ( v )) / τ v ) , as desired. Moreover, for each vertex x x x , let I I I be the fragment with the minimum key in the path π x ′ \pi'_x π x ′ . If I I I lies on a ray, the root of x x x before Step 2 lies on π x ′ \pi'_x π x ′ . Otherwise, let ( u , p ( u ) ) (u,p(u)) ( u , p ( u )) be the edge containing I I I . Since I I I has a unique label, p ( u ) p(u) p ( u ) cannot have the same label as x x x . Thus, we cut an edge on the path from x x x to p ( u ) p(u) p ( u ) . In either case, the root of x x x lies on π x ′ \pi'_x π x ′ , and every vertex on the path from x x x to this root belongs to S x S_x S x .
Forest merging (for the first iteration)
After forest cutting, we have a rooted forest F F F such that, for each vertex x x x , every vertex on the path from x x x to its root belongs to S x S_x S x . Moreover, the expected sum of τ z \tau_z τ z for all roots z z z is O ( O P T ) O(\mathrm{OPT}) O ( OPT ) . Our goal is to merge the trees of F F F by adding edges of total length at most ε O P T \varepsilon\mathrm{OPT} ε OPT , leaving at most n 1 − σ n^{1-\sigma} n 1 − σ 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 \tau_z τ z over all roots z z z , which gives only an O ( O P T ) O(\mathrm{OPT}) O ( OPT ) additive error. This bound is too large for our purpose, as we aim for an additive cost of at most ε O P T \varepsilon\mathrm{OPT} ε OPT . Before sampling, we therefore merge the trees using a different strategy to reduce the sum of τ z \tau_z τ z over their roots.
Merging via leader compression. We first merge the trees of F F 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 1/2 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 [1 ] to reduce the number of components. Here, we use this approach to reduce the expected sum of τ z \tau_z τ 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 / ε ) ) O(\log(1/\varepsilon)) O ( log ( 1/ ε )) iterations, this sum is at most ε O P T \varepsilon\mathrm{OPT} ε 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 C C independently with probability min { 1 , ∣ C ∣ / n σ / 10 } \min\{1, |C|/n^{\sigma/10}\} 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 n 1 − σ / 10 n^{1-\sigma/10} n 1 − σ /10 , and every unsampled component is connected to one of them. For each root z z z , the components intersecting S z S_z S z contain at least n σ n^\sigma n σ points in total. By the sampling probabilities, at least one of these components is sampled with high probability. Since every point in S z S_z S z is within distance 2 τ z 2\tau_z 2 τ z of z z z , the edge added for an unsampled component with root z z z has length at most 2 τ z 2\tau_z 2 τ z . Thus, on this high-probability event, the total length of the added edges is at most twice the sum of τ z \tau_z τ z over the roots before sampling. By the preceding step, this gives an O ( ε O P T ) O(\varepsilon\mathrm{OPT}) 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 ( n 1 − σ / 10 ) O(n^{1-\sigma/10}) O ( n 1 − σ /10 ) while adding edges of total expected length O ( ε O P T ) O(\varepsilon\mathrm{OPT}) O ( ε OPT ) .
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 v v , let C v C_v C v denote its component and let ω v \omega_v ω v be the total weight of its spanning tree. We define the distance between two vertices u u u and v v v by dist ( u , v ) : = min a ∈ C u , b ∈ C v dist ( a , b ) \operatorname{dist}(u,v) := \min_{a\in C_u,b\in C_v} \operatorname{dist}(a,b) dist ( u , v ) := min a ∈ C u , b ∈ C v 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 ) \operatorname{dist}(u,v) \le\operatorname{dist}(u,w) + \omega_w + \operatorname{dist}(w,v) dist ( u , v ) ≤ dist ( u , w ) + ω w + dist ( w , v ) . Indeed, the two points of C w C_w C w realizing the distances to C u C_u C u and C v C_v C v can be connected by a path in its spanning tree of length at most ω w \omega_w ω 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 / σ ) O(1/\sigma) 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 ( σ ε ) O(\sigma\varepsilon) O ( σ ε ) , we obtain a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate MST. Most operations in each iteration, including computing the neighborhoods directly, can be implemented in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using O ( n 2 ) O(n^2) O ( n 2 ) total space. The repeated leader compression takes O ( log ( 1 / ( σ ε ) ) / σ ) O(\log(1/(\sigma\varepsilon))/\sigma) O ( log ( 1/ ( σ ε )) / σ ) rounds per iteration. Overall, the algorithm takes O ( log ( 1 / ( σ ε ) ) / σ 2 ) O(\log(1/(\sigma\varepsilon))/\sigma^2) O ( log ( 1/ ( σ ε )) / σ 2 ) rounds and uses n σ n^\sigma n σ local space per machine and O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) total space.
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 ) O_\sigma(1) O σ ( 1 ) -factor approximation.
Second, most operations can be implemented in O σ ( 1 ) O_\sigma(1) O σ ( 1 ) MPC rounds using O ( n 1 + σ ) O(n^{1+\sigma}) O ( n 1 + σ ) total space, apart from the space needed to store the input points. Computing the exact neighborhoods S x S_x S x 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 factor for fixed σ \sigma σ . The resulting total space is O ( n d + n 1 + σ ) O(nd+n^{1+\sigma}) O ( n d + n 1 + σ ) for points in R d \mathbb{R}^d R d and O ~ ( n 1 + σ ) 2 O ( d d i m ) \widetilde{O}(n^{1+\sigma})2^{O(ddim)} O ( n 1 + σ ) 2 O ( dd im ) for metrics of doubling dimension d d i m ddim dd im .
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 [35 ] . 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 § 4 , we present truncated Prim and forest cutting as common subroutines with parameters that accommodate both settings. We present the general metric algorithm in § 5 and the algorithms using consistent hashing in § 6 . Finally, we describe the construction of TSP tours in § 7 .
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 n n vertices; we do not assume any underlying metric. Here, we provide an MPC implementation using O ( N ) O(N) O ( N ) total space, where N N N is the input size defined below. These subroutines will be used in both the Euclidean and general metric cases.
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 X X for the vertex set of the complete graph to which the subroutine is applied, and dist \operatorname{dist} dist for its edge lengths. Recall that Prim’s algorithm starts from a vertex x ∈ X x \in X x ∈ X and grows a tree one edge at a time. Let U U U denote the set of vertices reached so far, initially U = { x } U = \{x\} U = { x } . At each iteration, we select an edge u v uv uv minimizing dist ( u , v ) \operatorname{dist}(u,v) dist ( u , v ) among all edges with u ∈ U u \in U u ∈ U and v ∈ X ∖ U v \in X \setminus U v ∈ X ∖ U . We then add this edge to the current tree and add v v v to U U U . In our case, we run Prim’s algorithm on a small neighborhood S x S_x S x of x x x that fits in a single machine. Here, an issue is that if a vertex y y y with y ∉ S x y \notin S_x y ∈ / S x has a short edge to a vertex in S x S_x S x , an MST of S x S_x S x obtained by Prim’s algorithm starting from x x x is not necessarily contained in an MST of X X 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 ∖ S x X \setminus S_x X ∖ S x .
More generally, we use the following setting. Each vertex x ∈ X x \in X x ∈ X is associated with a positive threshold τ x \tau_x τ x , a neighborhood S x S_x S x with x ∈ S x ⊆ X x \in S_x \subseteq X x ∈ S x ⊆ X , and a nonnegative vertex weight ω x \omega_x ω x . We denote a call to this subroutine by TruncatedPrim( x , S x , τ x , ω ) (x,S_x,\tau_x,\omega) ( x , S x , τ x , ω ) , where ω \omega ω denotes the vertex weights { ω y } y ∈ S x \{\omega_y\}_{y \in S_x} { ω y } y ∈ S x . Then the algorithm works as follows. For pseudocode, see Algorithm 1. Let U U U be the set of vertices visited so far, and E x E_x E x be the set of chosen edges. Thus the set of the endpoints of the edges of E x E_x E x coincides with U U U unless E x = ∅ E_x = \varnothing E x = ∅ . We use ω ( E x ) \omega(E_x) ω ( E x ) to denote the total length of E x E_x E x plus ∑ v ∈ U ω v \sum_{v \in U}\omega_v ∑ v ∈ U ω v . We terminate the procedure when ω ( E x ) ≥ τ x \omega(E_x) \geq\tau_x ω ( E x ) ≥ τ x or U = S x U = S_x U = S x . At each iteration, we choose an edge ( u , v ) (u,v) ( u , v ) with u ∈ U u \in U u ∈ U and v ∈ S x ∖ U v \in S_x \setminus U v ∈ S x ∖ U minimizing dist ( u , v ) \operatorname{dist}(u,v) dist ( u , v ) . Then we add ( u , v ) (u,v) ( u , v ) to E x E_x E x if its length is less than τ x \tau_x τ x ; otherwise, we immediately terminate the procedure. Then we add v v v to U U U , and ω ( E x ) \omega(E_x) ω ( E x ) increases by dist ( u , v ) + ω v \operatorname{dist}(u,v) + \omega_v dist ( u , v ) + ω v accordingly.
In § 6 for the Euclidean case, we always apply Algorithm 1 by setting X X X as a point set in R d \mathbb{R}^d R d and dist \operatorname{dist} dist as the Euclidean distance in R d \mathbb{R}^d R d . We set ω x = 0 \omega_x = 0 ω x = 0 for all x ∈ X x \in X x ∈ X . For general metrics, however, we contract several vertices into a single vertex before applying Algorithm 1; see § 5 . Here, each vertex x x x represents a set C x C_x C x of vertices of the original metric, and we abuse the notation to denote dist ( x , y ) : = dist ( C x , C y ) \operatorname{dist}(x,y) := \operatorname{dist}(C_x,C_y) dist ( x , y ) := dist ( C x , C y ) . Thus dist ( ⋅ , ⋅ ) \operatorname{dist}(\cdot,\cdot) dist ( ⋅ , ⋅ ) does not satisfy the triangle inequality in general. Instead, by setting the vertex weight ω z \omega_z ω z to the total weight of the tree maintained within C z C_z C z , we will prove the following inequality:
dist ( u , v ) ≤ dist ( u , z ) + ω z + dist ( z , v ) for all u , v , z ∈ X . (1) \operatorname{dist}(u,v) \leq\operatorname{dist}(u,z) + \omega_z + \operatorname{dist}(z,v) \qquad\text{for all } u,v,z \in X. \tag*{(1)} dist ( u , v ) ≤ dist ( u , z ) + ω z + dist ( z , v ) for all u , v , z ∈ X . (1)
Algorithm 1: TruncatedPrim(x x x , S x S_x S x , τ x \tau_x τ x , ω \omega ω )
Input: Root x x x , neighborhood S x ∋ x S_x \ni x S x ∋ x , threshold τ x > 0 \tau_x > 0 τ x > 0 , and vertex weights { ω y } y ∈ S x \{\omega_y\}_{y\in S_x} { ω y } y ∈ S x
U ← { x } U \leftarrow\{x\} U ← { x } ; E x ← ∅ E_x \leftarrow\varnothing E x ← ∅ ;
while ω ( E x ) < τ x \omega(E_x) < \tau_x ω ( E x ) < τ x and U ≠ S x U \ne S_x U = S x do
Let ( u , v ) (u,v) ( u , v ) be an edge with u ∈ U u \in U u ∈ U and v ∈ S x ∖ U v \in S_x \setminus U v ∈ S x ∖ U minimizing dist ( u , v ) \operatorname{dist}(u,v) dist ( u , v ) ;
if dist ( u , v ) ≥ τ x \operatorname{dist}(u,v) \ge\tau_x dist ( u , v ) ≥ τ x then
break;
E x ← E x ∪ { { u , v } } E_x \leftarrow E_x \cup\{\{u,v\}\} E x ← E x ∪ {{ u , v }} ; U ← U ∪ { v } U \leftarrow U \cup\{v\} U ← U ∪ { v } ;
return E x E_x E x ;
This inequality also holds for the Euclidean case where we set ω z : = 0 \omega_z := 0 ω z := 0 and dist ( u , z ) : = ∥ u − z ∥ \operatorname{dist}(u,z) := \lVert u-z\rVert dist ( u , z ) := ∥ u − z ∥ . Therefore, in this subsection, we assume that dist ( ⋅ , ⋅ ) \operatorname{dist}(\cdot,\cdot) dist ( ⋅ , ⋅ ) satisfies (1) .
Analysis. The property we want to achieve is the following: TruncatedPrim returns a subgraph of an MST of X X 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 \omega_x + \operatorname{dist}(x,y) > 2\tau_x ω x + dist ( x , y ) > 2 τ x for every y ∉ S x y \notin S_x y ∈ / S x .
Let T T T be the MST of the complete graph on X X X with edge lengths dist \operatorname{dist} 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 T T is uniquely determined under this rule. In particular, if we apply Prim’s algorithm from any vertex x x x , the algorithm returns T T T .
Lemma 4.1. Let x x x be a vertex in X X X , and let S x S_x S x be a neighborhood with x ∈ S x ⊆ X x \in S_x \subseteq X x ∈ S x ⊆ X such that ω x + dist ( x , y ) > 2 τ x \omega_x + \operatorname{dist}(x,y) > 2\tau_x ω x + dist ( x , y ) > 2 τ x for every y ∈ X ∖ S x y \in X \setminus S_x y ∈ X ∖ S x . Let E x E_x E x be the set of edges returned by TruncatedPrim(x , S x , τ x , ω x,S_x,\tau_x,\omega x , S x , τ x , ω ). Then E x ⊆ E ( T ) E_x \subseteq E(T) E x ⊆ E ( T ) .
Proof. We prove by induction on k k k that the first k k k edges chosen by TruncatedPrim coincide, in the same order, with the first k k k edges chosen by Prim’s algorithm on X X X starting from x x x . The claim holds immediately for k = 0 k = 0 k = 0 . Suppose that the claim holds after k k k edges, and that TruncatedPrim is about to add another edge. Let U U U be the set of vertices visited by TruncatedPrim (and thus by Prim’s algorithm), and E x E_x E x the current edge set.
We have ω ( E x ) < τ x \omega(E_x) < \tau_x ω ( E x ) < τ x . Let ( u , v ) (u,v) ( u , v ) be the next edge chosen by Prim’s algorithm, with u ∈ U u \in U u ∈ U and v ∈ X ∖ U v \in X \setminus U v ∈ X ∖ U . Its length is at most that of the edge added by TruncatedPrim, and hence is less than τ x \tau_x τ x . Then we have the following inequalities:
ω x + dist ( x , v ) ≤ ω ( E x ) + dist ( u , v ) < 2 τ x . \omega_x + \operatorname{dist}(x,v) \le\omega(E_x) + \operatorname{dist}(u,v) < 2\tau_x. ω x + dist ( x , v ) ≤ ω ( E x ) + dist ( u , v ) < 2 τ x .
The first inequality can be obtained by applying (1) along the path from x x x to u u u in the current tree. By the assumption on S x S_x S x , we have v ∈ S x v \in S_x v ∈ S x . Therefore, TruncatedPrim also chooses ( u , v ) (u,v) ( u , v ) . This implies that E x ⊆ E ( T ) E_x \subseteq E(T) E x ⊆ E ( T ) .
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 n n -vertex forest F F F with positive edge weights ℓ e \ell_e ℓ e , non-negative vertex weights ω x \omega_x ω x , and positive vertex costs a x a_x a x . Here, the edge and vertex weights define the distances in F F F , whereas the vertex costs a x a_x a x determine the quality of the partition as we will see later. For distinct vertices x x x and y y y in the same component of F F F , let dist F ( x , y ) \operatorname{dist}_F(x,y) dist F ( x , y ) be the total weight of the edges and vertices on their unique path, including x x x but excluding y y y . We set dist F ( x , x ) = 0 \operatorname{dist}_F(x,x)=0 dist F ( x , x ) = 0 . Notice that dist F ( x , y ) − dist F ( y , x ) = ω x − ω y \operatorname{dist}_F(x,y)-\operatorname{dist}_F(y,x)=\omega_x-\omega_y dist F ( x , y ) − dist F ( y , x ) = ω x − ω y if x x x and y y 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 x x in an oriented forest, we use p ( x ) p(x) p ( x ) to denote its parent. Removing the edge ( x , p ( x ) ) (x,p(x)) ( x , p ( x )) splits its component into two oriented trees, one with the original root and one with the new root x x x .
Our goal is to choose and orient a subset of the edges of F F 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 F F contains at least one root.
Definition 4.2 (Low-cost forest partition). A randomized partition of F F 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 R R be the set of roots of the resulting trees, and let r ( x ) r(x) r ( x ) be the root of the tree containing x x x .
(i) For every vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , we have dist F ( x , r ( x ) ) ≤ a x \operatorname{dist}_F(x,r(x)) \le a_x dist F ( x , r ( x )) ≤ a x for every outcome of the random choices.
(ii) The expected total cost of the roots satisfies
E [ ∑ z ∈ R a z ] ≤ ∑ C ∈ cc ( F ) min v ∈ C a v + O ( ∑ e ∈ E ( F ) ℓ e + ∑ v ∈ V ( F ) ω v ) . \mathbb{E}\left[\sum_{z\in R}a_z\right]\le\sum_{C\in\operatorname{cc}(F)}\min_{v\in C}a_v+O\left(\sum_{e\in E(F)}\ell_e+\sum_{v\in V(F)}\omega_v\right). E [ z ∈ R ∑ a z ] ≤ C ∈ cc ( F ) ∑ v ∈ C min a v + O e ∈ E ( F ) ∑ ℓ e + v ∈ V ( F ) ∑ ω v . where cc ( F ) \operatorname{cc}(F) cc ( F ) denotes the connected components of F F F before any edges are removed.
Input representation for the MPC model. As input, we are given F F F along with its edge weights, vertex weights, and vertex costs. Here, the hop-diameter of F F F may be large. To obtain an O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) -round MPC implementation, we additionally assume that a small neighborhood of each vertex is given as input. More specifically, let F x F_x F x be the subgraph of F F F induced by { y ∈ V ( F ) : dist F ( x , y ) ≤ a x } \{y \in V(F):\operatorname{dist}_F(x,y)\le a_x\} { y ∈ V ( F ) : dist F ( x , y ) ≤ a x } . For each x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , the vertices and edges of F x F_x F x , together with their identifiers, weights, and vertex costs, are stored on a single machine. In this case, the input size N N N is ∑ x ∈ V ( F ) ∣ V ( F x ) ∣ \sum_{x\in V(F)}|V(F_x)| ∑ x ∈ V ( F ) ∣ V ( F x ) ∣ .
In this subsection, we prove the following lemma, which will be used in § 6 and § 5 .
Lemma 4.3. Fix a constant σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) . Let F F F be a forest on at most n n n vertices with positive edge weights ℓ e \ell_e ℓ e , non-negative vertex weights ω x \omega_x ω x , and positive vertex costs a x a_x a x such that a x ≤ a y + dist F ( x , y ) / 8 a_x \le a_y+\operatorname{dist}_F(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 for any two vertices x , y x,y x , y in the same component of F F F . Assume that F F F is stored across machines and that, for each x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , the records of F x F_x F x fit on a single machine with local space n σ n^\sigma n σ . Then there is an O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) -round MPC algorithm that computes a low-cost forest partition of F F F along with the root R ( x ) R(x) R ( x ) for every vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , using n σ n^\sigma n σ local space per machine and O ( N ) O(N) 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 ) R(x) R ( x ) can be computed in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) rounds. In the second step, we remove some edges while keeping condition (ii) so that, for each vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , either its current root lies in F x F_x F x , or an edge on the path from x x x to that root whose endpoint closer to x x x lies in F x F_x F x is removed. Due to this property, condition (i) is satisfied, and R ( x ) R(x) R ( x ) can be computed locally from F x F_x F x once the parent and edge-removal information is available. We describe the first and second steps in § 4.2.1 and § 4.2.2 . Then we provide an MPC implementation in § 4.2.3 .
Step 1. Giving orientations to edges
The idea is simple: For each vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , choose a vertex v ( x ) ∈ V ( F x ) v(x) \in V(F_x) v ( x ) ∈ V ( F x ) with the largest weight ω v ( x ) \omega_{v(x)} ω v ( x ) , breaking ties by a fixed vertex order. If v ( x ) ≠ x v(x) \ne x v ( x ) = x , orient the first edge on the path from x x x to v ( x ) v(x) v ( x ) towards v ( x ) v(x) v ( x ) . All choices of v ( x ) v(x) v ( x ) are made in the initial forest F F 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 x x with ω x ≥ a x / 2 \omega_x \ge a_x/2 ω x ≥ a x /2 , if such an edge exists. We let F ′ F' F ′ be the resulting forest, and keep F F F for the initial forest.
Now we first show that F ′ F' 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 a x ≤ a y + dist F ( x , y ) / 8 a_x \le a_y + \operatorname{dist}_F(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 for any two vertices x , y x,y x , y in the same component of F F F . Then F ′ F' F ′ is oriented.
Proof. We claim that every edge ( x , y ) (x,y) ( x , y ) of F ′ F' F ′ has only one orientation. Assume that ( x , y ) (x,y) ( x , y ) is oriented from x x x to y y y . By construction, y y y is contained in the path in F F F between x x x and v ( x ) v(x) v ( x ) . In this case, v ( x ) ∈ V ( F y ) v(x) \in V(F_y) v ( x ) ∈ V ( F y ) . To see this, observe that dist F ( y , v ( x ) ) = dist F ( x , v ( x ) ) − dist F ( x , y ) ≤ a x − dist F ( x , y ) ≤ a y \operatorname{dist}_F(y,v(x)) = \operatorname{dist}_F(x,v(x)) - \operatorname{dist}_F(x,y) \le a_x - \operatorname{dist}_F(x,y) \le a_y dist F ( y , v ( x )) = dist F ( x , v ( x )) − dist F ( x , y ) ≤ a x − dist F ( x , y ) ≤ a y . The first inequality holds due to v ( x ) ∈ V ( F x ) v(x) \in V(F_x) v ( x ) ∈ V ( F x ) , and the last inequality holds by the assumption that a x ≤ a y + dist F ( x , y ) / 8 a_x \le a_y + \operatorname{dist}_F(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 . Now assume to the contrary that ( x , y ) (x,y) ( x , y ) is oriented in both directions. The argument above implies that v ( x ) ∈ V ( F y ) v(x) \in V(F_y) v ( x ) ∈ V ( F y ) and v ( y ) ∈ V ( F x ) v(y) \in V(F_x) v ( y ) ∈ V ( F x ) . By the choice of v ( ⋅ ) v(\cdot) v ( ⋅ ) , this implies that v ( x ) = v ( y ) v(x) = v(y) v ( x ) = v ( y ) , which is impossible: the unique paths from x x x and y y y to the same target vertex v ( x ) = v ( y ) v(x) = v(y) v ( x ) = v ( y ) cannot both start with ( x , y ) (x,y) ( x , y ) .
Now observe that every vertex of F ′ F' F ′ has at most one outgoing edge. For a component C C C of F ′ F' F ′ , ∣ E ( C ) ∣ = ∣ V ( C ) ∣ − 1 |E(C)| = |V(C)| - 1 ∣ E ( C ) ∣ = ∣ V ( C ) ∣ − 1 . This implies that C C C has only one vertex without outgoing edges, which is the root of C C C . Moreover, since F F F has no undirected cycle, every edge of C C C goes towards its root. This completes the proof of the lemma.
Lemma 4.5. Assume a x ≤ a y + dist F ( x , y ) / 8 a_x \le a_y + \operatorname{dist}_F(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 for any two vertices x , y x,y x , y in the same component of F F F . Let R ′ R' R ′ be the set of roots of F ′ F' F ′ . Then we have
∑ z ∈ R ′ a z ≤ ∑ C ∈ cc ( F ) min v ∈ C a v + O ( ∑ e ∈ E ( F ) ℓ e + ∑ v ∈ V ( F ) ω v ) . \sum_{z \in R'} a_z \le\sum_{C \in\operatorname{cc}(F)} \min_{v \in C} a_v + O\left(\sum_{e \in E(F)} \ell_e + \sum_{v \in V(F)} \omega_v\right). z ∈ R ′ ∑ a z ≤ C ∈ cc ( F ) ∑ v ∈ C min a v + O e ∈ E ( F ) ∑ ℓ e + v ∈ V ( F ) ∑ ω v . Proof. Let z z z be a root in R ′ R' R ′ . By construction, there are two cases: either v ( z ) = z v(z) = z v ( z ) = z , or ω z ≥ a z / 2 \omega_z \ge a_z/2 ω z ≥ a z /2 . For the latter case, the sum of a z a_z a z for all such roots is at most the sum of 2 ω z 2\omega_z 2 ω z for all such roots. Therefore, it suffices to focus on the former case. We now analyze an upper bound on a z a_z a z for each root z ∈ R ′ z \in R' z ∈ R ′ with v ( z ) = z v(z) = z v ( z ) = z . For each component C C C of F F F , choose a vertex u C u_C u C with minimum cost a u C a_{u_C} a u C in C C C . For each root z z z in C C C with v ( z ) = z v(z) = z v ( z ) = z , let π z \pi_z π z be the undirected path in F F F starting at z z z towards u C u_C u C and ending at the first vertex y y y with dist F ( z , y ) > a z / 8 \operatorname{dist}_F(z,y) > a_z/8 dist F ( z , y ) > a z /8 , or at u C u_C u C if no such vertex exists. We use ℓ ( π z ) \ell(\pi_z) ℓ ( π z ) to denote the total weight of its edges and vertices, excluding its last vertex. If dist F ( z , u C ) > a z / 8 \operatorname{dist}_F(z,u_C) > a_z/8 dist F ( z , u C ) > a z /8 , then a z < 8 ℓ ( π z ) a_z < 8\ell(\pi_z) a z < 8 ℓ ( π z ) by construction. Otherwise, π z \pi_z π z ends at u C u_C u C , and the assumption on the vertex costs implies a z ≤ a u C + ℓ ( π z ) / 8 a_z \le a_{u_C} + \ell(\pi_z)/8 a z ≤ a u C + ℓ ( π z ) /8 .
We now claim that for any two distinct roots z , z ′ ∈ R ′ z,z' \in R' z , z ′ ∈ R ′ in the same component of F F F with v ( z ) = z v(z) = z v ( z ) = z and v ( z ′ ) = z ′ v(z') = z' v ( z ′ ) = z ′ , there is no vertex y y y satisfying both dist F ( z , y ) ≤ a z / 8 \operatorname{dist}_F(z,y) \le a_z/8 dist F ( z , y ) ≤ a z /8 and dist F ( z ′ , y ) ≤ a z ′ / 8 \operatorname{dist}_F(z',y) \le a_{z'}/8 dist F ( z ′ , y ) ≤ a z ′ /8 . Assume to the contrary that such a vertex y y y exists. Since y ∈ V ( F z ) ∩ V ( F z ′ ) , v ( z ) = z y \in V(F_z) \cap V(F_{z'}), v(z) = z y ∈ V ( F z ) ∩ V ( F z ′ ) , v ( z ) = z , and v ( z ′ ) = z ′ v(z') = z' v ( z ′ ) = z ′ , we have ω y ≤ min { ω z , ω z ′ } \omega_y \le\min\{\omega_z,\omega_{z'}\} ω y ≤ min { ω z , ω z ′ } . Thus we have
dist F ( z , z ′ ) ≤ dist F ( z , y ) + dist F ( y , z ′ ) = dist F ( z , y ) + dist F ( z ′ , y ) + ω y − ω z ′ ≤ dist F ( z , y ) + dist F ( z ′ , y ) ≤ ( a z + a z ′ ) / 8. \begin{aligned}
\operatorname{dist}_F(z,z') &\le\operatorname{dist}_F(z,y) + \operatorname{dist}_F(y,z') \\
&= \operatorname{dist}_F(z,y) + \operatorname{dist}_F(z',y) + \omega_y - \omega_{z'} \\
&\le\operatorname{dist}_F(z,y) + \operatorname{dist}_F(z',y) \le(a_z + a_{z'})/8.
\end{aligned} dist F ( z , z ′ ) ≤ dist F ( z , y ) + dist F ( y , z ′ ) = dist F ( z , y ) + dist F ( z ′ , y ) + ω y − ω z ′ ≤ dist F ( z , y ) + dist F ( z ′ , y ) ≤ ( a z + a z ′ ) /8.
The last inequality holds by the assumed bounds on dist F ( z , y ) \operatorname{dist}_{F}(z,y) dist F ( z , y ) and dist F ( z ′ , y ) \operatorname{dist}_{F}(z',y) dist F ( z ′ , y ) . Symmetrically, dist F ( z ′ , z ) ≤ ( a z + a z ′ ) / 8 \operatorname{dist}_{F}(z',z) \le(a_z+a_{z'})/8 dist F ( z ′ , z ) ≤ ( a z + a z ′ ) /8 . Assume without loss of generality that z z z is preferred to z ′ z' z ′ when choosing v ( ⋅ ) v(\cdot) v ( ⋅ ) , that is, either ω z > ω z ′ \omega_z > \omega_{z'} ω z > ω z ′ , or ω z = ω z ′ \omega_z = \omega_{z'} ω z = ω z ′ and z z z has a higher priority than z ′ z' z ′ in the fixed vertex order. By the assumption on the vertex costs, we have a z ≤ 2 a z ′ + dist F ( z , z ′ ) / 8 ≤ a z ′ + ( a z + a z ′ ) / 64 a_z \le2a_{z'}+\operatorname{dist}_{F}(z,z')/8 \le a_{z'}+(a_z+a_{z'})/64 a z ≤ 2 a z ′ + dist F ( z , z ′ ) /8 ≤ a z ′ + ( a z + a z ′ ) /64 , which implies a z < 2 a z ′ a_z < 2a_{z'} a z < 2 a z ′ . Therefore, dist F ( z ′ , z ) < 3 a z ′ / 8 < a z ′ \operatorname{dist}_{F}(z',z) < 3a_{z'}/8 < a_{z'} dist F ( z ′ , z ) < 3 a z ′ /8 < a z ′ , and thus z ∈ V ( F z ′ ) z \in V(F_{z'}) z ∈ V ( F z ′ ) . This contradicts v ( z ′ ) = z ′ v(z')=z' v ( z ′ ) = z ′ by the choice of v ( ⋅ ) v(\cdot) v ( ⋅ ) . This proves the claim.
By construction, every vertex y y y of π z \pi_z π z other than its last vertex satisfies dist F ( z , y ) ≤ a z / 8 \operatorname{dist}_{F}(z,y) \le a_z/8 dist F ( z , y ) ≤ a z /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 C C go towards u C u_C u C . If two paths contained the same edge, its endpoint farther from u C u_C u C 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 ) \ell(\pi_z) ℓ ( π z ) over all these roots is at most ∑ e ∈ E ( F ) ℓ e + ∑ v ∈ V ( F ) ω v \sum_{e\in E(F)} \ell_e + \sum_{v\in V(F)} \omega_v ∑ e ∈ E ( F ) ℓ e + ∑ v ∈ V ( F ) ω v . The claim also implies that, in each component C C C , at most one such root z z z satisfies dist F ( z , u C ) ≤ a z / 8 \operatorname{dist}_{F}(z,u_C) \le a_z/8 dist F ( z , u C ) ≤ a z /8 . Hence the term a u C = min v ∈ V ( C ) a v a_{u_C}=\min_{v\in V(C)} a_v a u C = min v ∈ V ( C ) a v is added at most once per component. Summing the bounds on a z a_z a z and adding the costs of the roots with ω z ≥ a z / 2 \omega_z \ge a_z/2 ω z ≥ a z /2 proves the lemma.
Step 2. Cutting additional edges from the oriented forest
Now we have an oriented forest F ′ F' F ′ satisfying condition (ii). Recall that some edges of the initial F F F are removed in the construction of F ′ F' F ′ . But to simplify notation, we simply redefine F : = F ′ F := F' F := F ′ . Our goal in this subsection is to remove additional edges from F F F so that condition (i) also holds. For this, we assign a label i ( x ) i(x) i ( x ) to each vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , and remove every edge of F F F whose endpoints have different labels. In the following, as F F F is oriented, the parent p ( x ) p(x) p ( x ) of a non-root vertex x x x is uniquely defined. We let ℓ x : = dist F ( x , p ( x ) ) = ℓ ( x , p ( x ) ) + ω x \ell_x := \operatorname{dist}_{F}(x,p(x)) = \ell_{(x,p(x))}+\omega_x ℓ x := dist F ( x , p ( x )) = ℓ ( x , p ( x )) + ω x . By the construction in Section 4.2.1, we have ω x < a x / 2 \omega_x < a_x/2 ω x < a x /2 for every non-root vertex x x x .
Algorithm description. We view each edge ( x , p ( x ) ) ∈ E ( F ) (x,p(x)) \in E(F) ( x , p ( x )) ∈ E ( F ) as a segment x p ( x ) xp(x) x p ( x ) of length ℓ x \ell_x ℓ x . This allows us to refer to points in the interiors of edges. A vertex of F F 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 F F . For two points p p p and q q q with q q q on the path from p p p towards its root or on the attached ray, we extend the notation dist F ( p , q ) \operatorname{dist}_{F}(p,q) dist F ( 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 x x , set ρ x = max y { a y / 2 − dist F ( x , y ) } \rho_x = \max_{y}\{a_y/2-\operatorname{dist}_{F}(x,y)\} ρ x = max y { a y /2 − dist F ( x , y )} , where the maximum is taken over x x x and its non-root ancestors. For each root r r r , set ρ r = a r / 2 \rho_r=a_r/2 ρ r = a r /2 . For each vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , let p x p_x p x be the point reached by moving from x x x towards its root for a distance of exactly ρ x \rho_x ρ x , continuing along the attached ray if necessary. The point p x p_x p x is uniquely defined for each x ∈ V ( F ) x \in V(F) x ∈ V ( F ) . We mark the points p x p_x p x for all x ∈ V ( F ) x \in V(F) x ∈ V ( F ) and subdivide every edge and every attached ray at the marked points. Let I \mathcal{I} 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 x x to p x p_x p x is a union of fragments. See Figure 1 (a). For each fragment I ∈ I I \in\mathcal{I} I ∈ I of length ℓ ( I ) \ell(I) ℓ ( I ) , we independently draw a random key ξ I \xi_I ξ I from the exponential distribution with rate ℓ ( I ) \ell(I) ℓ ( I ) , that is, Pr [ ξ I > t ] = e − ℓ ( I ) t \Pr[\xi_I > t] = e^{-\ell(I)t} Pr [ ξ I > t ] = e − ℓ ( I ) t for t ≥ 0 t \ge0 t ≥ 0 .
Figure 1. Fragments used by the forest cutting algorithm. Black dots denote vertices of F F F , and hollow squares denote marked points p z p_z p z . Only an ancestor path is shown; other branches are omitted. (a) We attach a ray to the root, mark p x p_x p x at distance ρ x \rho_x ρ x from x x x , and subdivide at all marked points. The shaded fragments form I x I_x I x . (b) For y = p ( x ) y=p(x) y = p ( x ) , the top and bottom shaded paths consist of I y I_y I y and I x I_x I x , respectively, and the edge ( x , y ) (x,y) ( x , y ) has length ℓ x \ell_x ℓ x .
Now we define the label i ( x ) i(x) i ( x ) of a vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) as follows. We first give a label i ( I ) i(I) i ( I ) to each fragment I ∈ I I \in\mathcal{I} I ∈ I : if I I I is contained in an edge of F F 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 F F . For each vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , let I x I_x I x be the fragment with the smallest key among those on the path from x x x to p x p_x p x , and set i ( x ) = i ( I x ) i(x)=i(I_x) i ( x ) = i ( I x ) . In particular, each root of F F F receives the label of its attached ray. Finally, we remove every edge ( x , p ( x ) ) ∈ E ( F ) (x,p(x)) \in E(F) ( x , p ( x )) ∈ E ( F ) with i ( x ) ≠ i ( p ( x ) ) i(x) \ne i(p(x)) i ( x ) = i ( p ( x )) and return the resulting oriented forest F ′ F' F ′ .
Analysis. We now show that the resulting trees form a low-cost forest partition of F F F if a x ≤ a y + dist F ( x , y ) / 8 a_x \le a_y + \operatorname{dist}_F(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 for any two vertices x , y x,y x , y in the same component of F F F , and ω x < a x / 2 \omega_x < a_x/2 ω x < a x /2 for every non-root vertex x x x .
Lemma 4.6. For a vertex x x x of F F F , we have a x / 2 ≤ ρ x ≤ a x a_x/2 \le\rho_x \le a_x a x /2 ≤ ρ x ≤ a x . If p ( x ) p(x) p ( x ) is not a root, ∣ ρ x − ρ p ( x ) ∣ ≤ ℓ x \lvert\rho_x-\rho_{p(x)}\rvert\le\ell_x ∣ ρ x − ρ p ( x ) ∣ ≤ ℓ x .
Proof. If x x x is a root, a x / 2 ≤ ρ x ≤ a x a_x/2 \le\rho_x \le a_x a x /2 ≤ ρ x ≤ a x by definition. Otherwise, x x x itself is included in the maximum defining ρ x \rho_x ρ x , and hence ρ x ≥ a x / 2 \rho_x \ge a_x/2 ρ x ≥ a x /2 . To prove the upper bound, let y y y be a non-root ancestor of x x x , possibly x x x itself. By the definition of the distance, dist F ( y , x ) = dist F ( x , y ) + ω y − ω x ≤ dist F ( x , y ) + a y \operatorname{dist}_F(y,x) = \operatorname{dist}_F(x,y) + \omega_y - \omega_x \le\operatorname{dist}_F(x,y)+a_y dist F ( y , x ) = dist F ( x , y ) + ω y − ω x ≤ dist F ( x , y ) + a y , since ω y < a y / 2 \omega_y < a_y/2 ω y < a y /2 and ω x ≥ 0 \omega_x \ge0 ω x ≥ 0 . Applying the assumption on the vertex costs to ( y , x ) (y,x) ( y , x ) gives
a y ≤ a x + dist F ( y , x ) / 8 ≤ a x + ( dist F ( x , y ) + a y ) / 2. a_y \le a_x + \operatorname{dist}_F(y,x)/8 \le a_x + \bigl(\operatorname{dist}_F(x,y) + a_y\bigr)/2. a y ≤ a x + dist F ( y , x ) /8 ≤ a x + ( dist F ( x , y ) + a y ) /2.
Rearranging, we obtain a y / 2 − dist F ( x , y ) ≤ a x − dist F ( x , y ) / 2 ≤ a x a_y/2 - \operatorname{dist}_F(x,y) \le a_x - \operatorname{dist}_F(x,y)/2 \le a_x a y /2 − dist F ( x , y ) ≤ a x − dist F ( x , y ) /2 ≤ a x . Taking the maximum over y y y proves ρ x ≤ a x \rho_x \le a_x ρ x ≤ a x . Moreover, if ρ x = a y / 2 − dist F ( x , y ) \rho_x = a_y/2 - \operatorname{dist}_F(x,y) ρ x = a y /2 − dist F ( x , y ) , then a x / 2 ≤ ρ x ≤ a x − dist F ( x , y ) / 2 a_x/2 \le\rho_x \le a_x - \operatorname{dist}_F(x,y)/2 a x /2 ≤ ρ x ≤ a x − dist F ( x , y ) /2 , so dist F ( x , y ) ≤ a x \operatorname{dist}_F(x,y) \le a_x dist F ( x , y ) ≤ a x and y ∈ V ( F x ) y \in V(F_x) y ∈ V ( F x ) .
Now consider the second part of the lemma. Let y = p ( x ) y=p(x) y = p ( x ) be a non-root vertex. The candidates in the maximum defining ρ x \rho_x ρ x are x x x , y y y , and the non-root ancestors of y y y . For each candidate other than x x x , the distance from x x x is ℓ x \ell_x ℓ x larger than the distance from y y y . Therefore,
ρ x = max { a x / 2 , ρ y − ℓ x } . \rho_x = \max\{a_x/2,\rho_y-\ell_x\}. ρ x = max { a x /2 , ρ y − ℓ x } .
This immediately gives ρ x ≥ ρ y − ℓ x \rho_x \ge\rho_y-\ell_x ρ x ≥ ρ y − ℓ x . On the other hand, the assumption on the vertex costs gives a x / 2 ≤ a y / 2 + ℓ x ≤ ρ y + ℓ x a_x/2 \le a_y/2+\ell_x \le\rho_y+\ell_x a x /2 ≤ a y /2 + ℓ x ≤ ρ y + ℓ x . Thus both terms in the maximum are at most ρ y + ℓ x \rho_y+\ell_x ρ y + ℓ x , and hence ρ x ≤ ρ y + ℓ x \rho_x \le\rho_y+\ell_x ρ x ≤ ρ y + ℓ x . Combining the two bounds proves ∣ ρ x − ρ y ∣ ≤ ℓ x \lvert\rho_x-\rho_y\rvert\le\ell_x ∣ ρ x − ρ y ∣ ≤ ℓ x .
Lemma 4.7. For a vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , we have dist F ( x , R ( x ) ) ≤ a x \operatorname{dist}_F(x,R(x)) \le a_x dist F ( x , R ( x )) ≤ a x , where R ( x ) R(x) R ( x ) is the root of the tree containing x x x in F ′ F' F ′ .
Proof. Let I x I_x I x be the fragment with the smallest key among those on the path from x x x to p x p_x p x . Then i ( x ) = i ( I x ) i(x)=i(I_x) i ( x ) = i ( I x ) . If I x I_x I x is contained in the infinite ray attached to the root r r r of the tree in F F F containing x x x , then dist F ( x , r ) ≤ ρ x ≤ a x \operatorname{dist}_F(x,r) \le\rho_x \le a_x dist F ( x , r ) ≤ ρ x ≤ a x by the choice of I x I_x I x . Since dist F ( x , R ( x ) ) ≤ dist F ( x , r ) \operatorname{dist}_F(x,R(x)) \le\operatorname{dist}_F(x,r) dist F ( x , R ( x )) ≤ dist F ( x , r ) , the lemma holds immediately. Now consider the case that an edge ( v , p ( v ) ) (v,p(v)) ( v , p ( v )) of F F F contains I x I_x I x . If i ( v ) ≠ i ( x ) i(v) \ne i(x) i ( v ) = i ( x ) , then r ( x ) r(x) r ( x ) lies on the path between x x x and v v v , and dist F ( x , r ( x ) ) ≤ dist F ( x , v ) ≤ ρ x ≤ a x \operatorname{dist}_{F}(x,r(x)) \le\operatorname{dist}_{F}(x,v) \le\rho_x \le a_x dist F ( x , r ( x )) ≤ dist F ( x , v ) ≤ ρ x ≤ a x . If this is not the case, i ( v ) = i ( x ) = i ( I x ) i(v)=i(x)=i(I_x) i ( v ) = i ( x ) = i ( I x ) , but i ( p ( v ) ) ≠ i ( I x ) i(p(v)) \ne i(I_x) i ( p ( v )) = i ( I x ) . This is because the upward path starting at p ( v ) p(v) p ( v ) does not contain I x I_x I x , and the label of I x I_x I x is unique. In this case, the edge ( v , p ( v ) ) (v,p(v)) ( v , p ( v )) is removed in the construction of F ′ F' F ′ , so r ( x ) r(x) r ( x ) again lies on the path between x x x and v v v . Thus the lemma holds in any case.
Lemma 4.8. Let R R R be the set of the roots of F F F , and R ′ R' R ′ be the set of the roots of F ′ F' F ′ . Then we have
E [ ∑ z ∈ R ′ ∖ R a z ] ≤ ∑ x ∈ V ( F ) ∖ R O ( ℓ x ) . \mathbb{E}\left[\sum_{z\in R'\setminus R} a_z\right] \le\sum_{x\in V(F)\setminus R} O(\ell_x). E z ∈ R ′ ∖ R ∑ a z ≤ x ∈ V ( F ) ∖ R ∑ O ( ℓ x ) . if a x ≤ a y + dist F ( x , y ) / 8 a_x \le a_y+\operatorname{dist}_{F}(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 for any two vertices x , y x,y x , y in the same component of F F F , and ω x < a x / 2 \omega_x<a_x/2 ω x < a x /2 for every non-root vertex x x x .
Proof. Let x x x be a non-root vertex of F F F , and let y = p ( x ) y=p(x) y = p ( x ) . It suffices to show that the probability that ( x , y ) (x,y) ( x , y ) is cut by the algorithm is O ( ℓ x / a x ) O(\ell_x/a_x) O ( ℓ x / a x ) . Indeed, a non-root vertex x x x of F F F becomes a root of F ′ F' F ′ exactly when ( x , y ) (x,y) ( x , y ) is cut. By linearity of expectation, we have
E [ ∑ z ∈ R ′ ∖ R a z ] = ∑ ( x , y ) ∈ E ( F ) a x Pr [ i ( x ) ≠ i ( y ) ] ≤ ∑ x ∈ V ( F ) ∖ R O ( ℓ x ) . \mathbb{E}\left[\sum_{z\in R'\setminus R} a_z\right] = \sum_{(x,y)\in E(F)} a_x\Pr[i(x)\ne i(y)] \le\sum_{x\in V(F)\setminus R} O(\ell_x). E z ∈ R ′ ∖ R ∑ a z = ( x , y ) ∈ E ( F ) ∑ a x Pr [ i ( x ) = i ( y )] ≤ x ∈ V ( F ) ∖ R ∑ O ( ℓ x ) .
Now we focus on analyzing the probability that ( x , y ) (x,y) ( x , y ) is cut. Let I x I_x I x be the set of fragments contained in the path from x x x to p x p_x p x . Similarly, let I y I_y I y be the set of fragments contained in the path from y y y to p y p_y p y . See Figure 1 (b). First suppose that y ∉ R y\notin R y ∈ / R . The event that ( x , y ) (x,y) ( x , y ) is cut by the algorithm happens only when the fragment of I x ∪ I y I_x\cup I_y I x ∪ I y with the smallest key is contained in I x ⊕ I y I_x\oplus I_y I x ⊕ I y , where I x ⊕ I y = ( I x ∖ I y ) ∪ ( I y ∖ I x ) I_x\oplus I_y=(I_x\setminus I_y)\cup(I_y\setminus I_x) I x ⊕ I y = ( I x ∖ I y ) ∪ ( I y ∖ I x ) . Then we have
Pr [ i ( x ) ≠ i ( y ) ] ≤ Pr [ arg min I ∈ I x ∪ I y ξ I ∈ I x ⊕ I y ] = ∑ I ∈ I x ⊕ I y ℓ ( I ) ∑ I ∈ I x ∪ I y ℓ ( I ) ≤ O ( ℓ x / a x ) . \Pr[i(x)\ne i(y)] \le\Pr\left[\underset{I\in I_x\cup I_y}{\arg\min}\ \xi_I\in I_x\oplus I_y\right] = \frac{\sum_{I\in I_x\oplus I_y}\ell(I)}{\sum_{I\in I_x\cup I_y}\ell(I)} \le O(\ell_x/a_x). Pr [ i ( x ) = i ( y )] ≤ Pr [ I ∈ I x ∪ I y arg min ξ I ∈ I x ⊕ I y ] = ∑ I ∈ I x ∪ I y ℓ ( I ) ∑ I ∈ I x ⊕ I y ℓ ( I ) ≤ O ( ℓ x / a x ) .
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 I x ⊕ I y I_x\oplus I_y I x ⊕ I y is at most ℓ x + ∣ ℓ x + ρ y − ρ x ∣ ≤ 3 ℓ x \ell_x+\lvert\ell_x+\rho_y-\rho_x\rvert\le3\ell_x ℓ x + ∣ ℓ x + ρ y − ρ x ∣ ≤ 3 ℓ x by the bound ∣ ρ x − ρ y ∣ ≤ ℓ x \lvert\rho_x-\rho_y\rvert\le\ell_x ∣ ρ x − ρ y ∣ ≤ ℓ x proved above, and the total length of the fragments in I x ∪ I y I_x\cup I_y I x ∪ I y is at least ρ x ≥ a x / 2 \rho_x\ge a_x/2 ρ x ≥ a x /2 .
Now suppose that y ∈ R y\in R y ∈ R . The label i ( y ) i(y) i ( y ) is shared by all fragments on the ray attached to y y y . Thus i ( x ) ≠ i ( y ) i(x)\ne i(y) i ( x ) = i ( y ) exactly when I x I_x I x lies on the edge ( x , y ) (x,y) ( x , y ) . The portion of the path from x x x to p x p_x p x on this edge has length min { ρ x , ℓ x } \min\{\rho_x,\ell_x\} min { ρ x , ℓ x } , and hence Pr [ i ( x ) ≠ i ( y ) ] = min { ρ x , ℓ x } / ρ x ≤ ℓ x / ρ x ≤ 2 ℓ x / a x \Pr[i(x)\ne i(y)]=\min\{\rho_x,\ell_x\}/\rho_x\le\ell_x/\rho_x\le2\ell_x/a_x Pr [ i ( x ) = i ( y )] = min { ρ x , ℓ x } / ρ x ≤ ℓ x / ρ x ≤ 2 ℓ x / a x .
MPC implementation
We now provide an MPC construction of a low-cost forest partition of F F F using the primitives in § 2 . As input, we are given F F F along with its edge weights ℓ e \ell_e ℓ e , vertex weights ω x \omega_x ω x , vertex costs a x a_x a x , and neighborhoods F x F_x F x . For each x ∈ V ( F ) x\in V(F) x ∈ V ( F ) , the vertices and edges of F x F_x F x are stored on a single machine, and the input size is N = ∑ x ∈ V ( F ) ∣ V ( F x ) ∣ N=\sum_{x\in V(F)}\lvert V(F_x)\rvert N = ∑ x ∈ V ( F ) ∣ V ( F x )∣ .
First step. In the first step, we choose v ( x ) ∈ V ( F x ) v(x)\in V(F_x) v ( x ) ∈ V ( F x ) and the parent edge, if any, of each vertex x x x locally, since F x F_x F x contains the path from x x x to v ( x ) v(x) 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 x x with ω x ≥ a x / 2 \omega_x\ge a_x/2 ω x ≥ a x /2 can be done locally. Using Broadcasting, we send the parent and parent-edge length of each vertex, or its root status, to every F x F_x F x containing that vertex. Therefore, the first step can be implemented in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds.
Second step. In the second step, we compute ℓ x \ell_x ℓ x for non-root vertices and ρ x \rho_x ρ x and p x p_x p x for all vertices locally using the parent information received in the first step. The proof above shows that the maximum defining ρ x \rho_x ρ x can be computed using only x x x and its non-root ancestors in F x F_x F x . Using Sorting, we sort the marked points p x p_x p x along each edge and attached ray and obtain O ( n ) O(n) O ( n ) fragments, keeping only the part up to the last marked point on each ray. Then we choose a random key ξ I \xi_I ξ I and the label i ( I ) i(I) i ( I ) of each fragment I I I locally.7 Using the machine ID and a local index, we assign distinct labels to the fragments contained in edges of F F 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 ) i(x) i ( x ) for each vertex x x x as follows. Note that the number of fragments contained in the x x x -p x p_x p x path can be large although the number of edges contained in the path is O ( ∣ V ( F x ) ∣ ) O(|V(F_x)|) O ( ∣ V ( F x ) ∣ ) . To resolve this issue, for each edge e e e of F F 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 F x F_x F x containing e e e . Thus each F x F_x F x receives O ( ∣ V ( F x ) ∣ ) O(|V(F_x)|) O ( ∣ V ( F x ) ∣ ) pairs. Since the total size of the neighborhoods stored on each machine is O ( n σ ) O(n^\sigma) O ( n σ ) , each machine receives O ( n σ ) O(n^\sigma) O ( n σ ) pairs, and the total number of pairs is O ( N ) O(N) O ( N ) .
For each p x p_x p x , we also compute the minimum key and its corresponding label on the part of the last edge or ray on the x x x -p x p_x p x path ending at p x p_x p x . This part starts at the child endpoint of the edge or at the root of the ray. We obtain these O ( n ) O(n) O ( n ) pairs using PrefixSum along each edge and ray, and send the pair for p x p_x p x to the machine containing F x F_x F x using Broadcasting. Then each vertex x x x obtains i ( x ) i(x) i ( x ) locally from the pairs for the complete edges on its path and the part ending at p x p_x p x . 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 F x F_x F x containing its child endpoint. Then each vertex x x x can find its root locally in F x F_x F x by Lemma 4.7. We use a constant number of primitive operations on O ( N ) O(N) O ( N ) records, and thus spend O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds with O ( N ) O(N) 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
In this section, we present a fully scalable MPC algorithm for computing a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate MST of a general metric ( X , dist ) (X,\operatorname{dist}) ( X , dist ) with n n n vertices. For any fixed constants σ , ε ∈ ( 0 , 1 ) \sigma,\varepsilon\in(0,1) σ , ε ∈ ( 0 , 1 ) , the algorithm uses O ( ( 1 + log ( 1 / ( σ ε ) ) / σ 2 ) O((1+\log(1/(\sigma\varepsilon))/\sigma^2) O (( 1 + log ( 1/ ( σ ε )) / σ 2 ) rounds, n σ n^\sigma n σ local space per machine, and O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) total space. Each primitive in Section 2 takes O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) rounds on a polynomial number of records [27 ] . We may consider the metric ( X , dist ) (X,\operatorname{dist}) ( 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 ) (X,\operatorname{dist}) ( X , dist ) . Let G 0 G_0 G 0 be the input metric graph of ( X , dist ) (X,\operatorname{dist}) ( X , dist ) .
We construct a spanning tree of G 0 G_0 G 0 in a bottom-up fashion. At each level, we partition the current set Q Q Q of vertices into clusters and construct a spanning tree T C T_C T C on each cluster C C C . Then we contract each cluster C v C_v C v into a single vertex v v v and proceed with the contracted graph. Thus each current vertex represents a connected component of the forest constructed so far in G 0 G_0 G 0 . Throughout the construction, for each current edge, we store an edge of G 0 G_0 G 0 of minimum weight between the two represented components and use its weight as the current edge weight. Before contracting each cluster C C C , we add the stored edge of G 0 G_0 G 0 corresponding to each edge of T C T_C T C to the final spanning tree. Since distances between contracted vertices need not satisfy the triangle inequality, we assign each vertex v v v a weight w ( v ) w(v) w ( v ) equal to the total edge weight of the tree maintained within its component. With these vertex weights, we have dist ( u , v ) ≤ dist ( u , z ) + ω ( z ) + dist ( z , v ) \operatorname{dist}(u,v) \le\operatorname{dist}(u,z) + \omega(z) + \operatorname{dist}(z,v) dist ( u , v ) ≤ dist ( u , z ) + ω ( z ) + dist ( z , v ) , since the tree within the component represented by z z z connects any two of its points at cost at most ω ( z ) \omega(z) ω ( z ) .
Overall algorithm
To formulate this idea, we introduce the notion of a light contraction . Let G G G be a complete graph with edge weight dist ( ⋅ , ⋅ ) \operatorname{dist}(\cdot,\cdot) dist ( ⋅ , ⋅ ) and nonnegative vertex weight ω ( ⋅ ) \omega(\cdot) ω ( ⋅ ) . We use OPT ( G ) \operatorname{OPT}(G) OPT ( G ) to denote the minimum total edge weight and vertex weight of a spanning tree of G G G . For a partition C \mathcal{C} C of V ( G ) V(G) V ( G ) , the contracted graph G / C G/\mathcal{C} G / C is defined as the complete graph where a vertex v v v corresponds to a partition class C v C_v C v of C \mathcal{C} C . We set the edge weight dist C ( u , v ) : = dist ( C u , C v ) \operatorname{dist}_{\mathcal{C}}(u,v) := \operatorname{dist}(C_u,C_v) dist C ( u , v ) := dist ( C u , C v ) . Consider a spanning tree T C T_C T C of a partition class C C C of C \mathcal{C} C . Its weight weight ( T C ) \operatorname{weight}(T_C) weight ( T C ) is defined as the total edge weight and vertex weight of T C T_C T C . For each vertex v ∈ V ( G / C ) v \in V(G/\mathcal{C}) v ∈ V ( G / C ) , we set the vertex weight ω C ( v ) : = weight ( T C v ) \omega_{\mathcal{C}}(v) := \operatorname{weight}(T_{C_v}) ω C ( v ) := weight ( T C v ) . When the context is clear, we omit the subscript C \mathcal{C} C from dist C ( ⋅ , ⋅ ) \operatorname{dist}_{\mathcal{C}}(\cdot,\cdot) dist C ( ⋅ , ⋅ ) and ω C ( ⋅ ) \omega_{\mathcal{C}}(\cdot) ω C ( ⋅ ) .
Definition 5.1 (Light contraction). Let b ≥ 2 b \ge2 b ≥ 2 and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , and let G G G be an m m m -vertex complete graph with edge-weight function dist ( ⋅ , ⋅ ) \operatorname{dist}(\cdot,\cdot) dist ( ⋅ , ⋅ ) and nonnegative vertex-weight function ω ( ⋅ ) \omega(\cdot) ω ( ⋅ ) . Consider a partition C \mathcal{C} C of V ( G ) V(G) V ( G ) and spanning trees { T C } C ∈ C \{T_C\}_{C\in\mathcal{C}} { T C } C ∈ C . Then we say G / C G/\mathcal{C} G / C is a ( b , ε ) (b,\varepsilon) ( b , ε ) -light contraction of G G G if the following conditions hold:
(i) The number of vertices of G / C G/\mathcal{C} G / C is O ( m / b ) + 1 O(m/b) + 1 O ( m / b ) + 1 .
(ii) The MST cost of the contracted graph satisfies OPT ( G / C ) ≤ ( 1 + ε ) ⋅ OPT ( G ) \operatorname{OPT}(G/\mathcal{C}) \le(1+\varepsilon)\cdot\operatorname{OPT}(G) OPT ( G / C ) ≤ ( 1 + ε ) ⋅ OPT ( G ) .
A main technical contribution of this section is an O ( ( 1 + log ( 1 / ε ) ) / σ ) O((1+\log(1/\varepsilon))/\sigma) O (( 1 + log ( 1/ ε )) / σ ) -round randomized MPC construction of a light contraction G / C G/\mathcal{C} G / C , along with a partition C \mathcal{C} C of V ( G ) V(G) V ( G ) and spanning trees { T C } C ∈ C \{T_C\}_{C\in\mathcal{C}} { T C } C ∈ C , which is stated in the following lemma.
Lemma 5.2. Fix two parameters ε , σ ∈ ( 0 , 1 ) \varepsilon,\sigma\in(0,1) ε , σ ∈ ( 0 , 1 ) . Let n n n and m m m be two integers with m ≤ n m \le n m ≤ n , and let b = n σ / 10 b = n^{\sigma/10} b = n σ /10 . Given an m m m -vertex complete graph G G G with edge weight dist ( ⋅ , ⋅ ) \operatorname{dist}(\cdot,\cdot) dist ( ⋅ , ⋅ ) and vertex weights ω ( ⋅ ) \omega(\cdot) ω ( ⋅ ) satisfying dist ( u , v ) ≤ dist ( u , z ) + ω ( z ) + dist ( z , v ) \operatorname{dist}(u,v) \le\operatorname{dist}(u,z) + \omega(z) + \operatorname{dist}(z,v) dist ( u , v ) ≤ dist ( u , z ) + ω ( z ) + dist ( z , v ) for any three vertices u , v , z ∈ V ( G ) u,v,z \in V(G) u , v , z ∈ V ( G ) , there is a randomized MPC algorithm that computes a partition C \mathcal{C} C and spanning trees { T C } C ∈ C \{T_C\}_{C\in\mathcal{C}} { T C } C ∈ C such that G / C G/\mathcal{C} G / C is a ( b , ε ) (b,\varepsilon) ( b , ε ) -light contraction with probability at least 1 − n − Ω ( 1 ) 1-n^{-\Omega(1)} 1 − n − Ω ( 1 ) . The algorithm uses O ( log ( 1 / ε ) / σ ) O(\log(1/\varepsilon)/\sigma) O ( log ( 1/ ε ) / σ ) rounds, n σ n^\sigma n σ local space per machine, and O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) total space.
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 / σ ⌉ L = \lceil20/\sigma\rceil L = ⌈ 20/ σ ⌉ , and keep b = n σ / 10 b = n^{\sigma/10} b = n σ /10 fixed throughout the algorithm. Initially, the weight ω ( ⋅ ) \omega(\cdot) ω ( ⋅ ) of every vertex of G 0 G_0 G 0 is zero, and the weight of each edge u v uv uv is dist ( u , v ) \operatorname{dist}(u,v) dist ( u , v ) . Starting with G = G 0 G = G_0 G = G 0 , repeatedly compute a ( b , ε / ( 2 L ) ) (b,\varepsilon/(2L)) ( b , ε / ( 2 L )) -light contraction using Lemma 5.2 while ∣ V ( G ) ∣ > n σ / 3 |V(G)| > n^{\sigma/3} ∣ V ( G ) ∣ > n σ /3 . For each cluster C C C , keep the stored original edges corresponding to the edges of T C T_C T C as part of the output and contract C C C . We make at most L L L calls and report failure if more than n σ / 3 n^{\sigma/3} n σ /3 vertices remain.
Each tree T C T_C T C 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 O(m/b)+1 O ( m / b ) + 1 ; while m > n σ / 3 m > n^{\sigma/3} m > n σ /3 , this is at most m / n σ / 20 m/n^{\sigma/20} m / n σ /20 for sufficiently large n n n . Thus L L L successful calls suffice. The remaining complete graph occupies O ( n 2 σ / 3 ) O(n^{2\sigma/3}) O ( n 2 σ /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 T T has w ( T ) = OPT ( G ) w(T) = \operatorname{OPT}(G) w ( T ) = OPT ( G ) for the final graph G G G . If all calls succeed, then
w ( T ) ≤ ( 1 + ε 2 L ) L OPT ( G 0 ) ≤ e ε / 2 OPT ( G 0 ) ≤ ( 1 + ε ) OPT ( G 0 ) . w(T) \le\left(1+\frac{\varepsilon}{2L}\right)^L \operatorname{OPT}(G_0) \le e^{\varepsilon/2}\operatorname{OPT}(G_0) \le(1+\varepsilon)\operatorname{OPT}(G_0). w ( T ) ≤ ( 1 + 2 L ε ) L OPT ( G 0 ) ≤ e ε /2 OPT ( G 0 ) ≤ ( 1 + ε ) OPT ( G 0 ) .
Sorting and aggregation update the vertex weights and the minimum edges between the new components, together with their stored original edges, in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) rounds using O ( n 2 ) O(n^2) O ( n 2 ) total space. With fresh randomness in each call, a union bound over at most L L L calls gives success probability 1 − n − Ω ( 1 ) 1-n^{-\Omega(1)} 1 − n − Ω ( 1 ) . Since L = O ( 1 / σ ) L=O(1/\sigma) L = O ( 1/ σ ) and each call uses error ε / ( 2 L ) \varepsilon/(2L) ε / ( 2 L ) , the total number of rounds is O ( ( L / σ ) ( 1 + log ( 2 L / ε ) ) ) = O ( ( 1 + log ( 1 / ( σ ε ) ) ) / σ 2 ) O((L/\sigma)(1+\log(2L/\varepsilon)))=O((1+\log(1/(\sigma\varepsilon)))/\sigma^2) O (( L / σ ) ( 1 + log ( 2 L / ε ))) = O (( 1 + log ( 1/ ( σ ε ))) / σ 2 ) , and the total space is O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) .
Proof of Lemma 5.2: Computing a light contraction
In this subsection, we prove Lemma 5.2: compute a ( b , ε ) (b,\varepsilon) ( b , ε ) -light contraction of an m m m -vertex complete graph G G G with edge weight dist ( ⋅ , ⋅ ) \operatorname{dist}(\cdot,\cdot) dist ( ⋅ , ⋅ ) and vertex weights ω ( ⋅ ) \omega(\cdot) ω ( ⋅ ) . 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) \operatorname{dist}(u,v) \le\operatorname{dist}(u,z)+\omega(z)+\operatorname{dist}(z,v) \qquad\text{for all }u,v,z\in V(G). \tag*{(2)} dist ( u , v ) ≤ dist ( u , z ) + ω ( z ) + dist ( z , v ) for all u , v , z ∈ V ( G ) . (2)
Here, ε , σ ∈ ( 0 , 1 ) \varepsilon,\sigma\in(0,1) ε , σ ∈ ( 0 , 1 ) , n ≥ m n\ge m n ≥ m , and b = n σ / 10 b=n^\sigma/10 b = n σ /10 . In particular, ( b log n ) 2 (b\log n)^2 ( b log n ) 2 is asymptotically smaller than the local space complexity. We use O ( n σ ) O(n^\sigma) O ( n σ ) local space and O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) total space. For a vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) and a radius r r r , we use B G ( v , r ) : = { u ∈ V ( G ) ∣ ω ( v ) + dist ( v , u ) ≤ r } B_G(v,r):=\{u\in V(G)\mid\omega(v)+\operatorname{dist}(v,u)\le r\} B G ( v , r ) := { u ∈ V ( G ) ∣ ω ( v ) + dist ( v , u ) ≤ r } .
We start by computing the smallest value r v r_v r v with ∣ B G ( v , r v ) ∣ = min { m , ⌈ c b log n ⌉ } |B_G(v,r_v)|=\min\{m,\lceil cb\log n\rceil\} ∣ B G ( v , r v ) ∣ = min { m , ⌈ c b log n ⌉} for every vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) , and we let S v : = B G ( v , r v ) S_v:=B_G(v,r_v) S v := B G ( v , r v ) , where c > 0 c>0 c > 0 is a sufficiently large constant. Since we use Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) total space, we can compute r v r_v r v and S v S_v S v in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) rounds for every vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) using Sorting. Then we apply TruncatedPrim( v , S v , r v / 2 , ω ) (v,S_v,r_v/2,\omega) ( v , S v , r v /2 , ω ) for every vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) . Here, ω \omega ω denotes the vertex weights { ω ( v ) } v ∈ V ( G ) \{\omega(v)\}_{v\in V(G)} { ω ( v ) } v ∈ V ( G ) . We place all vertices of S v S_v S v and all edges in S v × S v S_v\times S_v S v × S v into a single machine for each vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds in total. Then we run TruncatedPrim locally without any communication. Let F F F be the union of the edge sets returned by the calls of TruncatedPrim. Then the edges and vertices of F F F are spread over the machines, and some edges are created multiple times by different calls. We remove duplicate copies in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using Sorting. By Lemma 4.1, F F F is contained in an MST of G G G . Therefore, condition (ii) holds immediately by taking C C C as the vertex sets of the connected components of ( V ( G ) , E ( F ) ) (V(G),E(F)) ( V ( G ) , E ( F )) and each T C T_C T C as the corresponding component tree. Indeed, we have OPT ( G / C ) = OPT ( G ) \operatorname{OPT}(G/C)=\operatorname{OPT}(G) OPT ( G / C ) = OPT ( G ) .
However, we still have two issues: we need to identify the component of F F F containing each vertex, and condition (i) does not necessarily hold. Since each tree of F F F might be large, it is unclear if we can do this in O ( 1 / σ ) O(1/\sigma) 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 O(m/b)+1 O ( m / b ) + 1 components at the end.
Forest cutting
We first apply ForestCutting with a v : = r v / 8 a_v:=r_v/8 a v := r v /8 and ℓ u v : = dist ( u , v ) \ell_{uv}:=\operatorname{dist}(u,v) ℓ uv := dist ( u , v ) for every vertex v ∈ V ( F ) v\in V(F) v ∈ V ( F ) and edge ( u , v ) ∈ E ( F ) (u,v)\in E(F) ( u , v ) ∈ E ( F ) . The subroutine ForestCutting requires F x F_x F x to be stored on a single machine for each x ∈ V ( F ) x\in V(F) x ∈ V ( F ) , where F x F_x F x is the subgraph of F F F induced by { y ∈ V ( F ) : dist F ( x , y ) ≤ r x / 8 } \{y\in V(F):\operatorname{dist}_F(x,y)\le r_x/8\} { y ∈ V ( F ) : dist F ( x , y ) ≤ r x /8 } . By construction, F x F_x F x has O ( b log n ) O(b\log n) O ( b log n ) vertices, and thus we can place all edges and vertices of F x F_x F x on a single machine in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. The total space of F x F_x F x for all vertices x ∈ V ( F ) x\in V(F) x ∈ V ( F ) is within the total space complexity of O ( n 2 ) O(n^2) O ( n 2 ) .
We first show that this satisfies the assumption of Lemma 4.3 in the following lemma. In Section 4, recall that we let dist F ( x , y ) \operatorname{dist}_F(x,y) dist F ( x , y ) be the total weight of the edges and vertices on their unique path, including x x x but excluding y y y , for any two distinct vertices x x x and y y y in the same component of F F F . We set dist F ( x , x ) = 0 \operatorname{dist}_F(x,x)=0 dist F ( x , x ) = 0 .
Lemma 5.3. For any edge ( u , v ) ∈ E ( F ) (u,v)\in E(F) ( u , v ) ∈ E ( F ) , r u ≤ r v + ω ( u ) + dist ( u , v ) r_u\le r_v+\omega(u)+\operatorname{dist}(u,v) r u ≤ r v + ω ( u ) + dist ( u , v ) . Therefore, a x ≤ a y + dist F ( x , y ) / 8 a_x\le a_y+\operatorname{dist}_F(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 for any two vertices x , y ∈ V ( F ) x,y\in V(F) x , y ∈ V ( F ) in the same component of $F.
Proof. Recall that r v r_v r v is the smallest radius such that ∣ B G ( v , r v ) ∣ = min { m , ⌈ c b log n ⌉ } |B_G(v,r_v)|=\min\{m,\lceil c_b\log n\rceil\} ∣ B G ( v , r v ) ∣ = min { m , ⌈ c b log n ⌉} , and S v = B G ( v , r v ) S_v=B_G(v,r_v) S v = B G ( v , r v ) . For every z ∈ S v z\in S_v z ∈ S v , Equation (2) gives
ω ( u ) + dist ( u , z ) ≤ ω ( u ) + dist ( u , v ) + ω ( v ) + dist ( v , z ) ≤ ω ( u ) + dist ( u , v ) + r v . \omega(u)+\operatorname{dist}(u,z)\le\omega(u)+\operatorname{dist}(u,v)+\omega(v)+\operatorname{dist}(v,z)\le\omega(u)+\operatorname{dist}(u,v)+r_v. ω ( u ) + dist ( u , z ) ≤ ω ( u ) + dist ( u , v ) + ω ( v ) + dist ( v , z ) ≤ ω ( u ) + dist ( u , v ) + r v .
Here, the second inequality follows from the fact that z ∈ S v z\in S_v z ∈ S v . Thus S v ⊆ B G ( u , ω ( u ) + dist ( u , v ) + r v ) S_v\subseteq B_G(u,\omega(u)+\operatorname{dist}(u,v)+r_v) S v ⊆ B G ( u , ω ( u ) + dist ( u , v ) + r v ) , so this ball contains at least min { m , ⌈ c b log n ⌉ } \min\{m,\lceil c_b\log n\rceil\} min { m , ⌈ c b log n ⌉} vertices. By the definition of r u r_u r u , we obtain r u ≤ ω ( u ) + dist ( u , v ) + r v r_u\le\omega(u)+\operatorname{dist}(u,v)+r_v r u ≤ ω ( u ) + dist ( u , v ) + r v , which proves the first part of the lemma.
This also immediately gives a u ≤ a v + dist F ( u , v ) / 8 a_u\le a_v+\operatorname{dist}_F(u,v)/8 a u ≤ a v + dist F ( u , v ) /8 by the definition of dist F ( ⋅ , ⋅ ) \operatorname{dist}_F(\cdot,\cdot) dist F ( ⋅ , ⋅ ) and a v a_v a v , for an edge ( u , v ) (u,v) ( u , v ) of F F F . Summing these inequalities along the x x x -y y y path in F F F gives a x ≤ a y + dist F ( x , y ) / 8 a_x\le a_y+\operatorname{dist}_F(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 for any two vertices x , y x,y x , y in the same component of F F F . □
Thus we can apply ForestCutting on F F F in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. Then we have a low-cost forest partition F \mathcal{F} F of F F F consisting of oriented trees such that
E [ ∑ z ∈ R r z 8 ] ≤ ∑ C ∈ cc ( F ) min v ∈ C r v 8 + O ( ∑ ( u , v ) ∈ E ( F ) dist ( u , v ) + ∑ v ∈ V ( F ) ω ( v ) ) . (3) \mathbb{E}\left[\sum_{z\in R}\frac{r_z}{8}\right]\le\sum_{C\in\operatorname{cc}(F)}\min_{v\in C}\frac{r_v}{8}+O\left(\sum_{(u,v)\in E(F)}\operatorname{dist}(u,v)+\sum_{v\in V(F)}\omega(v)\right). \tag*{(3)} E [ z ∈ R ∑ 8 r z ] ≤ C ∈ cc ( F ) ∑ v ∈ C min 8 r v + O ( u , v ) ∈ E ( F ) ∑ dist ( u , v ) + v ∈ V ( F ) ∑ ω ( v ) . (3)
where cc ( F ) \operatorname{cc}(F) cc ( F ) denotes the connected components of F F F before any edges are removed and R R R denotes the roots of the trees of F \mathcal{F} F , by Definition 4.2 and Lemma 4.3. Moreover, each vertex v v v has the identifier of its root r ( v ) r(v) r ( v ) of the tree containing v v v in F \mathcal{F} F , which allows us to identify the component of F \mathcal{F} F containing v v v . Also, condition (ii) still holds, since the edges retained by ForestCutting are contained in an MST of G G 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.
Lemma 5.4. E [ ∑ z ∈ R r z ] = O ( OPT ( G ) ) \mathbb{E}\left[\sum_{z\in R}r_z\right]=O(\operatorname{OPT}(G)) E [ ∑ z ∈ R r z ] = O ( OPT ( G )) , where R R R denotes the set of the roots of the trees of F \mathcal{F} F .
Proof. It suffices to show that the right-hand side of Equation (3) is O ( OPT ( G ) ) O(\operatorname{OPT}(G)) O ( OPT ( G )) . The second term of the right-hand side of the equation is O ( OPT ( G ) ) O(\operatorname{OPT}(G)) O ( OPT ( G )) since F F F is contained in the MST of G G G . Thus we focus on proving ∑ C ∈ cc ( F ) min v ∈ C r v = O ( OPT ( G ) ) \sum_{C\in\operatorname{cc}(F)}\min_{v\in C}r_v=O(\operatorname{OPT}(G)) ∑ C ∈ cc ( F ) min v ∈ C r v = O ( OPT ( G )) .
If F F F has a single component, ω ( v ) + dist ( v , x ) ≤ weight ( F ) \omega(v)+\operatorname{dist}(v,x)\le\operatorname{weight}(F) ω ( v ) + dist ( v , x ) ≤ weight ( F ) for all vertices v , x ∈ V ( F ) v,x\in V(F) v , x ∈ V ( F ) by applying Equation (2) along the v v v -x x x path in F F F . This implies that B G ( v , weight ( F ) ) B_G(v,\operatorname{weight}(F)) B G ( v , weight ( F )) contains all vertices of F F F . By the choice of r v r_v r v , we have r v ≤ weight ( F ) = OPT ( G ) r_v\le\operatorname{weight}(F)=\operatorname{OPT}(G) r v ≤ weight ( F ) = OPT ( G ) , which is the desired bound.
Otherwise, let T T T be an MST of G G G containing F F F . For each component C C C of F F F , choose an edge ( u , v ) ∈ E ( T ) (u,v)\in E(T) ( u , v ) ∈ E ( T ) with u ∈ C u\in C u ∈ C and v ∉ C v\notin C v ∈ / C . If v ∉ S u v\notin S_u v ∈ / S u , r u < ω ( u ) + dist ( u , v ) ≤ weight ( F [ C ] ) + dist ( u , v ) r_u<\omega(u)+\operatorname{dist}(u,v)\le\operatorname{weight}(F[C])+\operatorname{dist}(u,v) r u < ω ( u ) + dist ( u , v ) ≤ weight ( F [ C ]) + dist ( u , v ) . Otherwise, consider the call TruncatedPrim ( u , S u , r u / 2 , ω ) \operatorname{TruncatedPrim}(u,S_u,r_u/2,\omega) TruncatedPrim ( u , S u , r u /2 , ω ) . The tree visited by this call is contained in F [ C ] F[C] 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 r u / 2 r_u/2 r u /2 , or the next edge has length at least r u / 2 r_u/2 r u /2 . In the first case, r u ≤ 2 ⋅ weight ( F [ C ] ) r_u\le2\cdot\operatorname{weight}(F[C]) r u ≤ 2 ⋅ weight ( F [ C ]) . In the second case, r u ≤ 2 ⋅ dist ( u , v ) r_u\le2\cdot\operatorname{dist}(u,v) r u ≤ 2 ⋅ dist ( u , v ) , since u u u is visited and v ∉ C v\notin C v ∈ / C . Thus, in all three cases,
min x ∈ C r x ≤ r u ≤ 2 ⋅ weight ( F [ C ] ) + 2 ⋅ dist ( u , v ) . \min_{x\in C}r_x\le r_u\le2\cdot\operatorname{weight}(F[C])+2\cdot\operatorname{dist}(u,v). x ∈ C min r x ≤ r u ≤ 2 ⋅ weight ( F [ C ]) + 2 ⋅ dist ( u , v ) .
Each edge ( u , v ) (u,v) ( u , v ) of T T T is chosen by at most two components of F F F , one containing u u u and one containing v v v . Therefore,
∑ C ∈ cc ( F ) min x ∈ C r x ≤ ∑ C ∈ cc ( F ) 2 ⋅ weight ( F [ C ] ) + ∑ ( u , v ) ∈ E ( T ) 4 ⋅ dist ( u , v ) ≤ 6 ⋅ OPT ( G ) , \sum_{C\in\operatorname{cc}(F)}\min_{x\in C}r_x\le\sum_{C\in\operatorname{cc}(F)}2\cdot\operatorname{weight}(F[C])+\sum_{(u,v)\in E(T)}4\cdot\operatorname{dist}(u,v)\le6\cdot\operatorname{OPT}(G), C ∈ cc ( F ) ∑ x ∈ C min r x ≤ C ∈ cc ( F ) ∑ 2 ⋅ weight ( F [ C ]) + ( u , v ) ∈ E ( T ) ∑ 4 ⋅ dist ( u , v ) ≤ 6 ⋅ OPT ( G ) ,
which proves the lemma. □
Forest merging
Now we merge components of F \mathcal{F} F by adding edges of G G G , while keeping the additive error induced by this procedure at most ε ⋅ OPT ( G ) \varepsilon\cdot\operatorname{OPT}(G) ε ⋅ 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 G G it contains. As in the Euclidean case analyzed in § 6 , we can show that the additive error induced by this procedure is at most ∑ z ∈ R r z \sum_{z\in R}r_z ∑ z ∈ R r z , which is O ( OPT ( G ) ) O(\operatorname{OPT}(G)) O ( OPT ( G )) in expectation by Lemma 5.4. This is acceptable in § 6 , but our desired approximation ratio is ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) here.
To reduce this expected error, we first merge several components using edges of an MST T T T of G G G before applying Merging-via-Sampling . This reduces the expected sum of r z r_z r z of the roots of the resulting trees to ε ′ ⋅ OPT ( G ) \varepsilon'\cdot\operatorname{OPT}(G) ε ′ ⋅ OPT ( G ) for a sufficiently small constant ε ′ ≤ ε \varepsilon'\le\varepsilon ε ′ ≤ ε . For this, we use the cut property: for each component C C C of F \mathcal{F} F , the minimum-weight edge of G G G leaving C C C is contained in T T 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 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. To resolve this, we use the standard technique of leader compression and call the resulting procedure Merging-via-Leader-Compression .
Merging via leader compression. We repeat the following procedure, starting with the components of F \mathcal{F} F and using their roots as representatives. In each iteration, the expected sum of r z r_z r z for all roots z z z decreases by a constant fraction, counting this sum as zero once only one component remains.
In each iteration, for each current component C C C , we pick an edge e C = ( u , v ) e_C=(u,v) e C = ( u , v ) with u ∈ C u\in C u ∈ C and v ∉ C v\notin C v ∈ / C with minimum dist ( u , v ) \operatorname{dist}(u,v) dist ( u , v ) in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds in total for all components. Then each component becomes a leader independently with probability 1 / 2 1/2 1/2 . For each nonleader component C C C , let e C = ( u , v ) e_C=(u,v) e C = ( u , v ) with u ∈ C u\in C u ∈ C and v ∉ C v\notin C v ∈ / C . If the component containing v v v is a leader, we add e C e_C e C and merge C C C with that component. We do this for all components in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. Each component formed by a merge consists of one leader component, say C l e a d C_{\mathrm{lead}} C lead , 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 C l e a d C_{\mathrm{lead}} C lead . For each new component, we use the root of C l e a d C_{\mathrm{lead}} C lead 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 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds.
We repeat this procedure for a sufficiently large number t = O ( 1 + log ( 1 / ε ′ ) ) t=O(1+\log(1/\varepsilon')) t = O ( 1 + log ( 1/ ε ′ )) of iterations, stopping as soon as only one component remains. Each iteration takes O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds, so the entire procedure takes O ( ( 1 + log ( 1 / ε ′ ) ) / σ ) O((1+\log(1/\varepsilon'))/\sigma) O (( 1 + log ( 1/ ε ′ )) / σ ) rounds.
Lemma 5.5. After applying Merging-via-Leader-Compression , E [ ∑ z ∈ R ′ r z ] ≤ ( ε ′ / 2 ) ⋅ OPT ( G ) \mathbb{E}\left[\sum_{z\in R'}r_z\right]\le(\varepsilon'/2)\cdot\operatorname{OPT}(G) E [ ∑ z ∈ R ′ r z ] ≤ ( ε ′ /2 ) ⋅ OPT ( G ) if there are at least two components, where R ′ R' R ′ denotes the set of roots of the resulting forest.
Proof. Let Φ i \Phi_i Φ i be the sum of r z r_z r z over the roots after i i i iterations. Initially, E [ Φ 0 ] = O ( OPT ( G ) ) \mathbb{E}[\Phi_0]=O(\operatorname{OPT}(G)) 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 C C , the probability that C C C is a nonleader and the component reached by e C e_C e C is a leader is 1 / 4 1/4 1/4 . If this event happens, C C C is merged into the leader component. Thus with probability 1 / 4 1/4 1/4 , each r z r_z r z is removed from Φ i \Phi_i Φ i . Therefore, E [ Φ i + 1 ∣ the current forest ] ≤ ( 3 / 4 ) ⋅ Φ i \mathbb{E}[\Phi_{i+1}\mid\text{the current forest}]\le(3/4)\cdot\Phi_i E [ Φ i + 1 ∣ the current forest ] ≤ ( 3/4 ) ⋅ Φ i . Thus, after a sufficiently large number t = O ( 1 + log ( 1 / ε ′ ) ) t = O(1+\log(1/\varepsilon')) t = O ( 1 + log ( 1/ ε ′ )) of iterations, E [ Φ t ] ≤ ( 3 / 4 ) t ⋅ E [ Φ 0 ] ≤ ( ε ′ / 2 ) ⋅ OPT ( G ) \mathbb{E}[\Phi_t] \le(3/4)^t \cdot\mathbb{E}[\Phi_0] \le(\varepsilon'/2)\cdot\operatorname{OPT}(G) 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 O(m/b)+1 O ( m / b ) + 1 . This is the only step that can increase the MST cost. For each component C C C returned by Merging-via-Leader-Compression, we sample it independently with probability p C = min { 1 , ∣ C ∣ / b } p_C = \min\{1, |C|/b\} p C = min { 1 , ∣ C ∣/ b } , where ∣ C ∣ |C| ∣ C ∣ denotes the number of vertices of G G G in C C C . The expected number of initially sampled components is at most m / b m/b m / b , since ∑ C ∣ C ∣ = m \sum_C |C| = m ∑ 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 C C , we find its closest sampled component NN ( C ) \operatorname{NN}(C) NN ( C ) , that is, we find the edge ( u , v ) (u,v) ( u , v ) with minimum dist ( u , v ) \operatorname{dist}(u,v) dist ( u , v ) such that u ∈ C u \in C u ∈ C and the component NN ( C ) \operatorname{NN}(C) NN ( C ) containing v v v is sampled, and then connect C C C with NN ( C ) \operatorname{NN}(C) NN ( C ) using ( u , v ) (u,v) ( u , v ) . Since we have Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) total space, this can be done in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds for all non-sampled components.
Lemma 5.6. Let A A A be the set of edges added by Merging-via-Sampling. Then
E [ ∑ ( u , v ) ∈ A dist ( u , v ) ] ≤ ε ′ ⋅ OPT ( G ) . \mathbb{E}\left[\sum_{(u,v)\in A}\operatorname{dist}(u,v)\right] \le\varepsilon' \cdot\operatorname{OPT}(G). E ( u , v ) ∈ A ∑ dist ( u , v ) ≤ ε ′ ⋅ OPT ( G ) . Proof. Let E \mathcal{E} E be the event that, for every non-sampled component C C C with root z z z , some sampled component intersects S z S_z S z . Condition on the forest after leader compression. If m ≤ ⌈ c b log n ⌉ m \le\lceil cb\log n\rceil m ≤ ⌈ c b log n ⌉ , then S z = V ( G ) S_z = V(G) S z = V ( G ) for every root z z z , so E \mathcal{E} E holds since at least one component is sampled. Otherwise, for each root z z z , the probability that no initially sampled component intersects S z S_z S z is at most
∏ ( 1 − p C ) ≤ exp ( − ∣ S z ∣ / b ) ≤ exp ( − c log n ) , \prod(1-p_C) \le\exp(-|S_z|/b) \le\exp(-c\log n), ∏ ( 1 − p C ) ≤ exp ( − ∣ S z ∣/ b ) ≤ exp ( − c log n ) , where the product is over the current components C C C intersecting S z S_z S z , whose sizes sum to at least ∣ S z ∣ |S_z| ∣ S z ∣ . A union bound over at most m ≤ n m \le n m ≤ n roots gives Pr [ E c ] ≤ ε ′ / ( 2 n ) \Pr[\mathcal{E}^c] \le\varepsilon'/(2n) Pr [ E c ] ≤ ε ′ / ( 2 n ) for a sufficiently large constant c c c depending on ε ′ \varepsilon' ε ′ , where E c \mathcal{E}^c E c denotes the event that E \mathcal{E} E does not occur.
Fix an outcome in E \mathcal{E} E and a non-sampled component C C C with root z z z . There is a sampled component C ′ C' C ′ containing a vertex x ∈ S z x \in S_z x ∈ S z . Since z ∈ C z \in C z ∈ C , the edge ( z , x ) (z,x) ( z , x ) is a candidate for connecting C C C to a sampled component. Thus, the edge ( u , v ) (u,v) ( u , v ) added for C C C satisfies
dist ( u , v ) ≤ dist ( z , x ) ≤ r z − ω ( z ) ≤ r z , \operatorname{dist}(u,v) \le\operatorname{dist}(z,x) \le r_z-\omega(z) \le r_z, dist ( u , v ) ≤ dist ( z , x ) ≤ r z − ω ( z ) ≤ r z , where the second inequality follows from the definition of S z S_z S z .
For every pair u , v ∈ V ( G ) u,v \in V(G) u , v ∈ V ( G ) , applying Equation (2) along the u u u -v v v path in an MST of G G G gives dist ( u , v ) ≤ OPT ( G ) \operatorname{dist}(u,v) \le\operatorname{OPT}(G) dist ( u , v ) ≤ OPT ( G ) . Since at most m − 1 ≤ n m-1 \le n m − 1 ≤ n edges are added, the total added weight is at most n ⋅ OPT ( G ) n\cdot\operatorname{OPT}(G) n ⋅ OPT ( G ) even when E \mathcal{E} E does not hold. Therefore,
E [ ∑ ( u , v ) ∈ A dist ( u , v ) ] ≤ E [ Φ t ] + n ⋅ Pr [ E c ] ⋅ OPT ( G ) ≤ ε ′ ⋅ OPT ( G ) . \mathbb{E}\left[\sum_{(u,v)\in A}\operatorname{dist}(u,v)\right] \le\mathbb{E}[\Phi_t] + n\cdot\Pr[\mathcal{E}^c]\cdot\operatorname{OPT}(G) \le\varepsilon'\cdot\operatorname{OPT}(G). E ( u , v ) ∈ A ∑ dist ( u , v ) ≤ E [ Φ t ] + n ⋅ Pr [ E c ] ⋅ OPT ( G ) ≤ ε ′ ⋅ OPT ( G ) .
Let C \mathcal{C} C be the final partition of V ( F ) V(F) V ( F ) . Note that each component C C C of C \mathcal{C} C has a spanning tree T C T_C T C , and each vertex v ∈ C v \in C v ∈ C is associated with its root r ( v ) r(v) r ( v ) in T C T_C T C . Therefore, we can compute G / C G/\mathcal{C} G / C in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using O ( n 2 ) O(n^2) O ( n 2 ) total space. We have shown that the expected number of components of C \mathcal{C} C is O ( m / b ) O(m/b) O ( m / b ) . By Lemma 5.6, the expected value of OPT ( G / C ) \operatorname{OPT}(G/\mathcal{C}) OPT ( G / C ) is at most ( 1 + ε ) ⋅ OPT ( G ) (1+\varepsilon)\cdot\operatorname{OPT}(G) ( 1 + ε ) ⋅ OPT ( G ) . By combining these results, we now prove Lemma 5.2.
Proof of Lemma 5.2. We apply the entire construction Θ ( log n ) \Theta(\log n) Θ ( log n ) times independently in parallel with ε ′ = ε / 4 \varepsilon' = \varepsilon/4 ε ′ = ε /4 . For each execution, let K K K be the number of components in C C C , and let W W W be the total weight of the edges added by Merging-via-Sampling. We already showed that E [ K ] ≤ O ( m / b ) \mathbb{E}[K] \le O(m/b) E [ K ] ≤ O ( m / b ) and E [ W ] ≤ ( ε / 4 ) ⋅ OPT ( G ) \mathbb{E}[W] \le(\varepsilon/4) \cdot\operatorname{OPT}(G) E [ W ] ≤ ( ε /4 ) ⋅ OPT ( G ) . By Markov’s inequality and a union bound, the two bounds K ≤ O ( m / b ) K \le O(m/b) K ≤ O ( m / b ) and W ≤ ε ⋅ OPT ( G ) W \le\varepsilon\cdot\operatorname{OPT}(G) W ≤ ε ⋅ OPT ( G ) hold simultaneously with probability at least 1 / 2 1/2 1/2 . Furthermore, we already showed that for every execution, OPT ( G / C ) ≤ OPT ( G ) + W \operatorname{OPT}(G/C) \le\operatorname{OPT}(G) + W OPT ( G / C ) ≤ OPT ( G ) + W .
Among the Θ ( log n ) \Theta(\log n) Θ ( log n ) executions with K ≤ O ( m / b ) K \le O(m/b) K ≤ O ( m / b ) , we return the one with minimum W W W , and report failure if there is no such execution. With probability at least 1 − n − Ω ( 1 ) 1 - n^{-\Omega(1)} 1 − n − Ω ( 1 ) , some execution satisfies both bounds above. The selected execution then also satisfies both bounds, and hence gives a ( b , ε ) (b,\varepsilon) ( b , ε ) -light contraction. The executions are performed in parallel, and aggregation computes their values of K K K and W W W and selects an execution in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) rounds. With ε ′ = ε / 4 \varepsilon' = \varepsilon/4 ε ′ = ε /4 , the total number of rounds is therefore O ( ( 1 + log ( 1 / ε ) ) / σ ) O((1+\log(1/\varepsilon))/\sigma) O (( 1 + log ( 1/ ε )) / σ ) , and the total space is O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) .
Constant approximate MST in Euclidean and doubling spaces
In this section, we present fully scalable MPC algorithms for computing an O ( 1 ) O(1) O ( 1 ) -approximate MST of a set P P P of n n n points in the Euclidean space of dimension d d d and a doubling space of doubling dimension ddim \operatorname{ddim} ddim . For any fixed constant σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) , our algorithms use O ( 1 / σ 2 ) O(1/\sigma^2) O ( 1/ σ 2 ) and O ( ddim / σ 4 ) O(\operatorname{ddim}/\sigma^4) O ( ddim / σ 4 ) rounds in Euclidean spaces and doubling metrics, respectively. The corresponding total space bounds are O ( n d + n 1 + σ ) O(nd+n^{1+\sigma}) O ( n d + n 1 + σ ) and O ~ ( n 1 + σ ) ⋅ 2 O ( ddim ) \widetilde{O}(n^{1+\sigma}) \cdot2^{O(\operatorname{ddim})} O ( n 1 + σ ) ⋅ 2 O ( ddim ) , respectively. For a point set Q ⊆ P Q \subseteq P Q ⊆ P , let OPT ( Q ) \operatorname{OPT}(Q) OPT ( Q ) denote the weight of an MST of Q Q Q . Let G G G be a graph such that a vertex of G G G corresponds to a point in P P P . We use ω ( G ) \omega(G) ω ( 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 ) \omega(G) ω ( G ) instead of weight ( G ) \operatorname{weight}(G) weight ( G ) for a graph G G G .
As for general metrics, our algorithm constructs a spanning tree in a bottom-up fashion, starting with the input point set P P P . At each level, we partition the current point set Q Q Q into clusters and construct a spanning tree T C T_C T C on each cluster C C 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 d d -dimensional Euclidean spaces, we assume d = O ( log n ) d = O(\log n) d = O ( log n ) ; if this is not the case, we apply the Johnson-Lindenstrauss reduction [33 ] , which can be implemented in constant MPC rounds [35 ] in the fully scalable MPC model. Here, all pairwise distances are preserved within a constant factor with high probability.
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 ) O(1) O ( 1 ) , we construct spanning trees for all clusters at every level with expected total weight O ( OPT ( Q ) ) O(\operatorname{OPT}(Q)) O ( OPT ( Q )) , where Q Q Q is the current representative set. For this, we introduce the notion of a light partition.
Definition 6.1 (Light partition). Let b ≥ 2 b \ge2 b ≥ 2 be an integer, and let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a parameter. Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) be a metric space. For a set P P P of n n n points in ( X , dist ) (X,\operatorname{dist}) ( X , dist ) , a ( b , λ ) (b,\lambda) ( b , λ ) -randomized light partition is a partition C \mathcal{C} C of P P P , together with a spanning tree T C T_C T C on each C ∈ C C \in\mathcal{C} C ∈ C , satisfying the following properties:
The number of clusters in C \mathcal{C} C is $O(n/b)+1.
Algorithm 2: Metric MST using light partitions
Input: A set P P P of n n n points in a metric space ( X , dist ) (X, \operatorname{dist}) ( X , dist )
b ← n σ / 10 b \leftarrow n^{\sigma/10} b ← n σ /10 ;
Q 0 ← P Q_0 \leftarrow P Q 0 ← P , E ← ∅ E \leftarrow\emptyset E ← ∅ , i ← 0 i \leftarrow0 i ← 0 ;
while ∣ Q i ∣ > n σ / 2 |Q_i| > n^{\sigma/2} ∣ Q i ∣ > n σ /2 do
Compute a ( b , λ ) (b,\lambda) ( b , λ ) -light partition ( C i , { T C } C ∈ C i ) (\mathcal{C}_i, \{T_C\}_{C\in\mathcal{C}_i}) ( C i , { T C } C ∈ C i ) of Q i Q_i Q i ;
foreach C ∈ C i C \in\mathcal{C}_i C ∈ C i do
E ← E ∪ E ( T C ) E \leftarrow E \cup E(T_C) E ← E ∪ E ( T C ) ; choose a representative r C ∈ C r_C \in C r C ∈ C ;
Q i + 1 ← { r C : C ∈ C i } Q_{i+1} \leftarrow\{r_C : C \in\mathcal{C}_i\} Q i + 1 ← { r C : C ∈ C i } ;
i ← i + 1 i \leftarrow i+1 i ← i + 1 ;
Compute an MST of Q i Q_i Q i on one machine and add its edges to E E E ;
return ( P , E ) (P,E) ( P , E ) ;
(ii) E [ ∑ C ∈ C ω ( T C ) ] ≤ λ ⋅ OPT ( P ) \mathbb{E}\left[\sum_{C\in\mathcal{C}}\omega(T_C)\right] \leq\lambda\cdot\operatorname{OPT}(P) E [ ∑ C ∈ C ω ( T C ) ] ≤ λ ⋅ 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 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) . Let n n n and m m m be two integers with m ≤ n m \leq n m ≤ n , and let b = n σ / 10 b = n^{\sigma/10} b = n σ /10 . Given a set P P P of m m m points in the Euclidean space of dimension d d d , one can construct a ( b , O ( 1 / σ 3 ) ) (b,O(1/\sigma^3)) ( b , O ( 1/ σ 3 )) -randomized light partition of P P P with high probability in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds, using O ( n σ ) O(n^\sigma) O ( n σ ) local space per machine and O ( m d + n 1 + σ ) O(md+n^{1+\sigma}) O ( m d + n 1 + σ ) total space.
Lemma 6.3. Fix a constant σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) . Let n n n and m m m be two integers with m ≤ n m \leq n m ≤ n , and let b = n σ / 10 b = n^{\sigma/10} b = n σ /10 . Given a set P P P of m m m points in a doubling metric space of doubling dimension ddim \operatorname{ddim} ddim where σ log n ≥ Ω ( ddim ) \sigma\log n \geq\Omega(\operatorname{ddim}) σ log n ≥ Ω ( ddim ) , one can construct a ( b , O ( 1 ) ) (b,O(1)) ( b , O ( 1 )) -randomized light partition of P P P with high probability in O ( ddim / σ 3 ) O(\operatorname{ddim}/\sigma^3) O ( ddim / σ 3 ) MPC rounds, using O ( n σ ) O(n^\sigma) O ( n σ ) local space per machine and O ~ ( n 1 + σ ⋅ 2 O ( ddim ) ) \widetilde{O}(n^{1+\sigma}\cdot2^{O(\operatorname{ddim})}) O ( n 1 + σ ⋅ 2 O ( 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 / σ ⌉ L = \lceil20/\sigma\rceil L = ⌈ 20/ σ ⌉ , and keep b = n σ / 10 b = n^{\sigma/10} b = n σ /10 fixed throughout the algorithm. Starting with P = Q 0 P = Q_0 P = Q 0 , we repeatedly compute a ( b , O ( 1 / σ 3 ) ) (b,O(1/\sigma^3)) ( b , O ( 1/ σ 3 )) -randomized light partition. At level i i i , we are given a set Q i ⊆ P Q_i \subseteq P Q i ⊆ P of representative points. Let ( C i , { T C } C ∈ C i ) (\mathcal{C}_i,\{T_C\}_{C\in\mathcal{C}_i}) ( C i , { T C } C ∈ C i ) be a ( b , O ( 1 / σ 3 ) ) (b,O(1/\sigma^3)) ( b , O ( 1/ σ 3 )) -randomized light partition of Q i Q_i Q i obtained by using Lemma 6.2. We choose an arbitrary representative point per cluster in C i \mathcal{C}_i C i , and let Q i + 1 Q_{i+1} Q i + 1 be the set of chosen representative points, which will be passed to the next level. Once n σ / 2 n^{\sigma/2} 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 O(m/b)+1 O ( m / b ) + 1 ; while m > n σ / 2 m > n^{\sigma/2} m > n σ /2 , this is at most m / n σ / 20 m/n^{\sigma/20} m / n σ /20 for sufficiently large n n n . Thus L L L successful calls suffice. The union of the trees constructed at all levels forms a spanning tree on P P P . We denote it by T T T .
We now show that T T T is an O ( 1 ) O(1) O ( 1 ) -approximate MST in expectation. Suppose that there are ℓ < L \ell< L ℓ < L levels. For each 0 ≤ i ≤ ℓ 0 \leq i \leq\ell 0 ≤ i ≤ ℓ , let m i = ∣ Q i ∣ m_i = |Q_i| m i = ∣ Q i ∣ . For every i < ℓ i < \ell i < ℓ , the trees constructed within the clusters in C i \mathcal{C}_i C i form a spanning forest on Q i Q_i Q i , and Q i + 1 Q_{i+1} Q i + 1 contains exactly one representative from each tree. Therefore, adding the spanning forest of Q i + 1 Q_{i+1} Q i + 1 merges those trees in the forest of Q i Q_i Q i without creating a cycle, and thus T T T is a spanning tree of P P P . Note that ∣ E ( T ) ∣ = ∑ i = 0 ℓ − 1 ( ∑ C ∈ C i ( ∣ C ∣ − 1 ) ) + ( m ℓ − 1 ) = ∑ i = 0 ℓ − 1 ( m i − m i + 1 ) + ( m ℓ − 1 ) = n − 1 |E(T)| = \sum_{i=0}^{\ell-1}(\sum_{C\in\mathcal{C}_i}(|C|-1))+(m_\ell-1) = \sum_{i=0}^{\ell-1}(m_i-m_{i+1})+(m_\ell-1)=n-1 ∣ E ( T ) ∣ = ∑ i = 0 ℓ − 1 ( ∑ C ∈ C i ( ∣ C ∣ − 1 )) + ( m ℓ − 1 ) = ∑ i = 0 ℓ − 1 ( m i − m i + 1 ) + ( m ℓ − 1 ) = n − 1 .
Consider an MST T ∗ T^* T ∗ of P P P and an Euler tour of the multigraph obtained by duplicating all edges of T ∗ T^* T ∗ . The length of the Euler tour is 2 ⋅ ω ( T ∗ ) 2\cdot\omega(T^*) 2 ⋅ ω ( T ∗ ) . For each 0 ≤ i ≤ ℓ 0\le i\le\ell 0 ≤ i ≤ ℓ , let ( q 1 , q 2 , … , q m i ) (q_1,q_2,\ldots,q_{m_i}) ( q 1 , q 2 , … , q m i ) be the points in Q i Q_i Q i ordered by their first occurrence in the Euler tour. Then, ∑ j = 1 m i dist ( q j , q j + 1 ) ≤ 2 ⋅ ω ( T ∗ ) \sum_{j=1}^{m_i}\operatorname{dist}(q_j,q_{j+1})\le2\cdot\omega(T^*) ∑ j = 1 m i dist ( q j , q j + 1 ) ≤ 2 ⋅ ω ( T ∗ ) by the triangle inequality, where q m i + 1 = q 1 q_{m_i+1}=q_1 q m i + 1 = q 1 . This implies that OPT ( Q i ) ≤ 2 ⋅ ω ( T ∗ ) = 2 OPT ( P ) \operatorname{OPT}(Q_i)\le2\cdot\omega(T^*)=2\operatorname{OPT}(P) OPT ( Q i ) ≤ 2 ⋅ ω ( T ∗ ) = 2 OPT ( 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 ( Q i ) ) O((1/\sigma^3)\operatorname{OPT}(Q_i)) O (( 1/ σ 3 ) OPT ( Q i )) , conditional on the preceding iterations and using fresh random choices at that level. Thus, summing over the O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) possible levels and including the final MST, we have
E [ ω ( T ) ] = E [ ∑ i = 0 ℓ − 1 ∑ C ∈ C i ω ( T C ) + OPT ( Q ℓ ) ] ≤ O ( ( 1 / σ 4 ) ⋅ OPT ( P ) ) + 2 OPT ( P ) = O ( ( 1 / σ 4 ) ⋅ OPT ( P ) ) . \begin{aligned}
\mathbb{E}[\omega(T)] = \mathbb{E}\left[\sum_{i=0}^{\ell-1}\sum_{C\in\mathcal{C}_i}\omega(T_C)+\operatorname{OPT}(Q_\ell)\right] \\
&\le O((1/\sigma^4)\cdot\operatorname{OPT}(P))+2\operatorname{OPT}(P)=O((1/\sigma^4)\cdot\operatorname{OPT}(P)).
\end{aligned} E [ ω ( T )] = E [ i = 0 ∑ ℓ − 1 C ∈ C i ∑ ω ( T C ) + OPT ( Q ℓ ) ] ≤ O (( 1/ σ 4 ) ⋅ OPT ( P )) + 2 OPT ( P ) = O (( 1/ σ 4 ) ⋅ OPT ( P )) .
Each iteration constructs a randomized light partition in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. Moreover, we can select representatives locally and update the representative and edge records in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. The MST on Q ℓ Q_\ell Q ℓ is computed locally. Since there are ℓ = O ( 1 / σ ) \ell=O(1/\sigma) ℓ = O ( 1/ σ ) iterations, the algorithm takes O ( 1 / σ 2 ) O(1/\sigma^2) O ( 1/ σ 2 ) MPC rounds in total.
By the Markov inequality, the probability that ω ( T ) > 2 c ⋅ OPT ( P ) \omega(T)>2c\cdot\operatorname{OPT}(P) ω ( T ) > 2 c ⋅ OPT ( P ) is at most 1 / 2 1/2 1/2 for some constant c c c . Thus, by applying Algorithm 2 independently to O ( log n ) O(\log n) O ( log n ) copies of P P P in parallel and returning the tree of minimum total weight, we can construct an O ( 1 ) O(1) O ( 1 ) -approximate MST with high probability. By reusing space across iterations and applying the above algorithm with σ / 2 \sigma/2 σ /2 local memory parameter, the bounds in Lemma 6.2 also give n σ / 2 n^{\sigma/2} n σ /2 local space per machine, and O ( n 1 + σ / 2 ) O(n^{1+\sigma/2}) O ( n 1 + σ /2 ) total space. The parallel copies and the selection take O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds and O ( n 1 + σ / 2 log n ) = O ( n 1 + σ ) O(n^{1+\sigma/2}\log n)=O(n^{1+\sigma}) O ( n 1 + σ /2 log n ) = O ( n 1 + σ ) total space.
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 , λ ) (b,\lambda) ( b , λ ) -light partition of a point set, with λ = O ( 1 / σ 3 ) \lambda=O(1/\sigma^3) λ = O ( 1/ σ 3 ) in d d d -dimensional Euclidean space and λ = O ( 1 ) \lambda=O(1) λ = O ( 1 ) in a metric space of doubling dimension d d i m d_{\mathrm{dim}} d dim . 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 x\in P 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-via-Sampling suffices to obtain a constant approximation factor.
Throughout this subsection, we are given a set P P P of m m m points in a metric space with distance dist \operatorname{dist} dist . We first describe how to construct a light partition on P P 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 n 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 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. Let k = ⌈ c b log n ⌉ = Θ ( b log n ) k=\lceil c b\log n\rceil=\Theta(b\log n) k = ⌈ c b log n ⌉ = Θ ( b log n ) , where c c c is a sufficiently large fixed constant. If m ≤ k m \le k m ≤ k , we compute an exact MST of P P 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 P P . In the general metric case, we compute, for each point x x x , a radius such that the ball centered at x x x with this radius contains at most k k 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 r x r_x r x for every point x ∈ P x \in P x ∈ P be the smallest radius such that ∣ B ( x , r ) ∩ P ∣ ≥ k |B(x,r) \cap P| \ge k ∣ B ( x , r ) ∩ P ∣ ≥ k , i.e., r x = min { r : ∣ B ( x , r ) ∩ P ∣ ≥ k } r_x = \min\{r : |B(x,r) \cap P| \ge k\} r x = min { r : ∣ B ( x , r ) ∩ P ∣ ≥ k } . We use estimates r ^ x \hat{r}_x r ^ x such that r x ≤ r ^ x ≤ 2 γ r x r_x \le\hat{r}_x \le2\gamma r_x r x ≤ r ^ x ≤ 2 γ r x , where γ > 1 \gamma> 1 γ > 1 is a constant determined later.
For each point x ∈ P x \in P x ∈ P , suppose that we have r ^ x \hat{r}_x r ^ x and a set, denoted by S x S_x S x , of points containing B ( x , ε r ^ x ) ∩ P B(x,\varepsilon\hat{r}_x) \cap P B ( x , ε r ^ x ) ∩ P and contained in B ( x , γ ε r ^ x ) ∩ P B(x,\gamma\varepsilon\hat{r}_x) \cap P B ( x , γ ε r ^ x ) ∩ P , where ε = 1 4 γ 2 \varepsilon= \frac{1}{4\gamma^2} ε = 4 γ 2 1 is a constant. Note that ∣ S x ∣ ≤ k = O ( b log n ) = O ( n σ / 2 ) |S_x| \le k = O(b\log n) = O(n^{\sigma/2}) ∣ S x ∣ ≤ k = O ( b log n ) = O ( n σ /2 ) since 2 ε γ 2 < 1 2\varepsilon\gamma^2 < 1 2 ε γ 2 < 1 . For every point x ∈ P x \in P x ∈ P , we suppose that S x S_x S x is stored on a single machine.
We then run TruncatedPrim( x , S x , ε r ^ x / 2 , 0 ) (x,S_x,\varepsilon\hat{r}_x/2,0) ( x , S x , ε r ^ x /2 , 0 ) on the machine M x M_x M x for every point x ∈ P x \in P x ∈ P . Let F F 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 F F in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using Sorting. Since for every x ∈ P x \in P x ∈ P , S x S_x S x contains B ( x , ε r ^ x ) B(x,\varepsilon\hat{r}_x) B ( x , ε r ^ x ) , the resulting edge set E x E_x E x is a subset of the MST from Prim’s algorithm by Lemma 4.1 . Therefore, F ⊆ T F \subseteq T F ⊆ T and ω ( F ) = O ( OPT ( P ) ) \omega(F) = O(\operatorname{OPT}(P)) ω ( 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 ) ) (P,E(F)) ( 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 F F , and (ii) there may still be too many components in F F F . To resolve the first issue, we apply ForestCutting described in § 4 , and to resolve the second issue, we merge several components so that we have O ( m / b ) + 1 O(m/b) + 1 O ( m / b ) + 1 components at the end.
Forest cutting
We first apply ForestCutting on F F F . However, r ^ x \hat{r}_x r ^ x does not necessarily satisfy the assumption of Lemma 4.3 , although the exact radius r x r_x r x does. We therefore define a local radius h x = min y ∈ P { dist ( x , y ) + ε 100 r ^ y } h_x = \min_{y \in P}\{\operatorname{dist}(x,y) + \frac{\varepsilon}{100}\hat{r}_y\} h x = min y ∈ P { dist ( x , y ) + 100 ε r ^ y } for each point x ∈ P x \in P x ∈ P . To compute h x h_x h x for each point x ∈ P x \in P x ∈ P , it suffices to check the points in S x S_x S x , since h x ≤ ( ε / 100 ) ⋅ r ^ x h_x \le(\varepsilon/100)\cdot\hat{r}_x h x ≤ ( ε /100 ) ⋅ r ^ x . Recall that S x S_x S x is stored in a single machine, and thus we can compute h x h_x h x only using local computation.
We then apply ForestCutting on F F F with a v : = h v / 8 a_v := h_v/8 a v := h v /8 and ℓ u v : = dist ( u , v ) \ell_{uv} := \operatorname{dist}(u,v) ℓ uv := dist ( u , v ) for every vertex v ∈ V ( F ) v \in V(F) v ∈ V ( F ) and edge ( u , v ) ∈ E ( F ) (u,v) \in E(F) ( u , v ) ∈ E ( F ) in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. Recall that the subroutine ForestCutting requires that for a point x x x , a x ≤ a y + dist F ( x , y ) / 8 a_x \le a_y + \operatorname{dist}_F(x,y)/8 a x ≤ a y + dist F ( x , y ) /8 , where y y y is a point in the same tree of F F F . This holds since the following lemma implies that h x / 8 ≤ h y / 8 + dist F ( x , y ) / 8 h_x/8 \le h_y/8 + \operatorname{dist}_F(x,y)/8 h x /8 ≤ h y /8 + dist F ( x , y ) /8 .
Lemma 6.4. For any two points x , y ∈ P x,y \in P x , y ∈ P , ∣ h x − h y ∣ ≤ dist ( x , y ) |h_x-h_y| \le\operatorname{dist}(x,y) ∣ h x − h y ∣ ≤ dist ( x , y ) . Moreover, for every x ∈ P x \in P x ∈ P , ε 100 r x ≤ h x ≤ ε γ 50 r x \frac{\varepsilon}{100}r_x \le h_x \le\frac{\varepsilon\gamma}{50}r_x 100 ε r x ≤ h x ≤ 50 ε γ r x , and ε r ^ x ≥ 100 h x \varepsilon\hat{r}_x \ge100h_x ε r ^ x ≥ 100 h x .
Proof. For a candidate z ∈ P z \in P z ∈ P , ∣ dist ( x , z ) + ε r ^ z / 100 − ( dist ( y , z ) + ε r ^ z / 100 ) ∣ = ∣ dist ( x , z ) − dist ( y , z ) ∣ ≤ dist ( x , y ) |\operatorname{dist}(x,z)+\varepsilon\hat{r}_z/100-(\operatorname{dist}(y,z)+\varepsilon\hat{r}_z/100)| = |\operatorname{dist}(x,z)-\operatorname{dist}(y,z)| \le\operatorname{dist}(x,y) ∣ dist ( x , z ) + ε r ^ z /100 − ( dist ( y , z ) + ε r ^ z /100 ) ∣ = ∣ dist ( x , z ) − dist ( y , z ) ∣ ≤ dist ( x , y ) . Let z ∗ z^* z ∗ be the point realizing h y h_y h y . We then have h x ≤ dist ( x , z ∗ ) + ε r ^ z ∗ / 100 ≤ h y + dist ( x , y ) h_x \le\operatorname{dist}(x,z^*)+\varepsilon\hat{r}_{z^*}/100 \le h_y+\operatorname{dist}(x,y) h x ≤ dist ( x , z ∗ ) + ε r ^ z ∗ /100 ≤ h y + dist ( x , y ) .
We now show the upper and lower bounds of h x h_x h x for each x ∈ P x \in P x ∈ P . Note that h x ≤ dist ( x , x ) + ε r ^ x / 100 ≤ ε γ r x / 50 h_x \le\operatorname{dist}(x,x)+\varepsilon\hat{r}_x/100 \le\varepsilon\gamma r_x/50 h x ≤ dist ( x , x ) + ε r ^ x /100 ≤ ε γ r x /50 since r ^ x ≤ 2 γ r x \hat{r}_x \le2\gamma r_x r ^ x ≤ 2 γ r x , and thus 100 h x ≤ ε r ^ x 100h_x \le\varepsilon\hat{r}_x 100 h x ≤ ε r ^ x . For any point y ∈ P y \in P y ∈ P , we have r y ≥ r x − dist ( x , y ) r_y \ge r_x-\operatorname{dist}(x,y) r y ≥ r x − dist ( x , y ) , since the ball of radius r y r_y r y centered at y y y is contained in the ball of radius r y + dist ( x , y ) r_y+\operatorname{dist}(x,y) r y + dist ( x , y ) centered at x x x . We then have dist ( x , y ) + ε r ^ y / 100 ≥ dist ( x , y ) + ε r y / 100 ≥ ε r x / 100 + ( 1 − ε / 100 ) ⋅ dist ( x , y ) ≥ ε r x / 100 \operatorname{dist}(x,y)+\varepsilon\hat{r}_y/100 \ge\operatorname{dist}(x,y)+\varepsilon r_y/100 \ge\varepsilon r_x/100 +(1-\varepsilon/100)\cdot\operatorname{dist}(x,y) \ge\varepsilon r_x/100 dist ( x , y ) + ε r ^ y /100 ≥ dist ( x , y ) + ε r y /100 ≥ ε r x /100 + ( 1 − ε /100 ) ⋅ dist ( x , y ) ≥ ε r x /100 , since ε < 1 \varepsilon< 1 ε < 1 . Thus, h x ≥ ε r x / 100 h_x \ge\varepsilon r_x/100 h x ≥ ε r x /100 . □ \square □
Moreover, ForestCutting requires that, for each x ∈ V ( F ) x \in V(F) x ∈ V ( F ) , the subgraph F x F_x F x induced by { y ∈ V ( F ) : dist F ( x , y ) ≤ h x / 8 } \{y \in V(F): \operatorname{dist}_F(x,y) \le h_x/8\} { y ∈ V ( F ) : dist F ( x , y ) ≤ h x /8 } be stored on a single machine. By Lemma 6.4 and our choice of ε < 1 / ( 2 γ 2 ) \varepsilon< 1/(2\gamma^2) ε < 1/ ( 2 γ 2 ) , we have h x / 8 < r x h_x/8 < r_x h x /8 < r x , so F x F_x F x contains at most k = O ( n σ ) k = O(n^\sigma) k = O ( n σ ) vertices. Furthermore, since h x / 8 ≤ ε r ^ x / 800 h_x/8 \le\varepsilon\hat{r}_x/800 h x /8 ≤ ε r ^ x /800 , every vertex of F x F_x F x belongs to S x S_x S x , which is stored on a single machine. We locally compute an MST T x T_x T x of S x S_x S x using the same edge ordering as in TruncatedPrim. Since F [ S x ] ⊆ T x F[S_x] \subseteq T_x F [ S x ] ⊆ T x , we identify the edges of F [ S x ] F[S_x] F [ S x ] using Aggregation and Broadcasting, and then compute F x F_x F x locally. These steps take O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds within the stated space bounds.
We now have a low-cost forest partition F \mathcal{F} F of F F F consisting of oriented trees such that
E [ ∑ z ∈ R h z / 8 ] ≤ ∑ C ∈ cc ( F ) min v ∈ C h v / 8 + O ( ∑ ( u , v ) ∈ E ( F ) dist ( u , v ) ) , (4) \mathbb{E}\left[\sum_{z\in R} h_z/8\right] \le\sum_{C\in\operatorname{cc}(F)} \min_{v\in C} h_v/8 + O\left(\sum_{(u,v)\in E(F)} \operatorname{dist}(u,v)\right), \tag*{(4)} E [ z ∈ R ∑ h z /8 ] ≤ C ∈ cc ( F ) ∑ v ∈ C min h v /8 + O ( u , v ) ∈ E ( F ) ∑ dist ( u , v ) , (4)
where cc ( F ) \operatorname{cc}(F) cc ( F ) denotes the connected components of F F F before any edges are removed and R R R denotes the roots of the trees of F \mathcal{F} F , by Definition 4.2 and Lemma 4.3. Moreover, each vertex v v v has the identifier of its root r ( v ) r(v) r ( v ) of the tree containing v v v in F \mathcal{F} F , which allows us to identify the component of F \mathcal{F} F containing v v v . Also, condition (ii) still holds, since the edges retained by ForestCutting are contained in an MST of P P 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 [ ∑ z ∈ R h z ] = O ( O P T ( P ) ) \mathbb{E}[\sum_{z\in R} h_z] = O(OPT(P)) E [ ∑ z ∈ R h z ] = O ( O P T ( P )) , where R R R denotes the set of the roots of the trees of F \mathcal{F} F .
Forest merging
We now merge components of F \mathcal{F} F into O ( m / b ) + 1 O(m/b)+1 O ( m / b ) + 1 components by adding edges, while keeping the approximation factor. For a root z ∈ R z \in R z ∈ R , we let T z T_z T z be the component in F \mathcal{F} F rooted at z z z .
We first sample independently each root z ∈ R z \in R z ∈ R with probability min { 1 , ∣ T z ∣ / 2 ⌈ log b ⌉ } \min\{1, |T_z|/2^{\lceil\log b\rceil}\} min { 1 , ∣ T z ∣/ 2 ⌈ l o g b ⌉ } . These sampled roots will determine how components in F \mathcal{F} F are merged. Recall that each vertex v v v has the identifier of its root r ( v ) r(v) r ( v ) of the tree containing v v v in F \mathcal{F} F , and thus we can compute ∣ T z ∣ |T_z| ∣ T z ∣ in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using Aggregation. We then sample z z z independently using local computation. The expected number of initially sampled components is at most m / b m/b m / b , since ∑ z ∈ R ∣ T z ∣ = m \sum_{z\in R}|T_z|=m ∑ z ∈ R ∣ T z ∣ = m . If no root is sampled, we choose an arbitrary root and treat it as sampled. For each non-sampled root z z z , suppose that we have a 2 γ 2\gamma 2 γ -approximate nearest sampled root, denoted by ANN ( z ) \operatorname{ANN}(z) ANN ( z ) . For each sampled root z z z , we set ANN ( z ) = z \operatorname{ANN}(z)=z ANN ( z ) = z .
For every sampled root z z z , we add the edges between the roots whose 2 γ 2\gamma 2 γ -approximate nearest sampled root is z z z as follows. Let ( T 1 , T 2 , … , T ℓ ) (T_1,T_2,\ldots,T_\ell) ( T 1 , T 2 , … , T ℓ ) be the components in F \mathcal{F} F whose roots are assigned to z z z , ordered by lexicographic order. For every 1 ≤ i ≤ ℓ 1 \le i \le\ell 1 ≤ i ≤ ℓ , we compute the prefix sum s i = ∑ j < i ∣ T j ∣ s_i=\sum_{j<i}|T_j| s i = ∑ j < i ∣ T j ∣ in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) rounds using PrefixSum. We form clusters by grouping together the trees T i T_i T i with the same value of ⌊ 2 s i / b 4 ⌋ \lfloor2s_i/b^4\rfloor ⌊ 2 s i / b 4 ⌋ . Let C \mathcal{C} C be the resulting collection of clusters.
We now construct T C T_C T C for each cluster C ∈ C C \in\mathcal{C} C ∈ C . Let z ( C ) z(C) z ( C ) be the sampled root used to construct C C C . Note that C C C may not contain z ( C ) z(C) z ( C ) . We first compute the root q q q in C C C closest to z ( C ) z(C) z ( C ) . This can be done in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds, since the roots in the cluster already have z ( C ) z(C) z ( C ) . We then add the edge between q q q and all the other roots in C C C in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds by sending q q 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 ( ( γ / ε ) O P T ( P ) ) O((\gamma/\varepsilon)OPT(P)) O (( γ / ε ) O P T ( P )) .
Proof. Let E \mathcal{E} E be the event that, for every non-sampled root z z z , there exists at least one sampled root q q q such that T q T_q T q intersects B ( z , r z ) B(z,r_z) B ( z , r z ) . For each root z z z , the probability that there is no sampled root whose component intersects B ( z , r z ) B(z,r_z) B ( z , r z ) is at most
∏ x ∈ R : T x ∩ B ( z , r z ) ≠ ∅ ( 1 − p x ) ≤ exp ( − ∣ B ( z , r z ) ∩ P ∣ / 2 ⌈ log 2 b ⌉ ) ≤ exp ( − ( c / 2 ) log n ) . \prod_{x\in R:T_x\cap B(z,r_z)\ne\varnothing}(1-p_x)\le\exp\left(-\lvert B(z,r_z)\cap P\rvert/2^{\lceil\log_2 b\rceil}\right)\le\exp\left(-(c/2)\log n\right). x ∈ R : T x ∩ B ( z , r z ) = ∅ ∏ ( 1 − p x ) ≤ exp ( − ∣ B ( z , r z ) ∩ P ∣ / 2 ⌈ l o g 2 b ⌉ ) ≤ exp ( − ( c /2 ) log n ) .
The first inequality holds since the size sum of the components intersecting B ( z , r z ) B(z,r_z) B ( z , r z ) is at least ∣ B ( z , r z ) ∩ P ∣ \lvert B(z,r_z)\cap P\rvert ∣ B ( z , r z ) ∩ P ∣ , and the second inequality holds since ∣ B ( z , r z ) ∩ P ∣ ≥ k \lvert B(z,r_z)\cap P\rvert\ge k ∣ B ( z , r z ) ∩ P ∣ ≥ k and k = ⌈ c b log n ⌉ k=\lceil cb\log n\rceil k = ⌈ c b log n ⌉ . A union bound over at most m ≤ n m\le n m ≤ n roots gives Pr [ E c ] ≤ n 1 − c / 2 \Pr[\mathcal{E}^c]\le n^{1-c/2} Pr [ E c ] ≤ n 1 − c /2 .
Fix an outcome in E \mathcal{E} E and a non-sampled root z z z . There is a sampled root z ′ z' z ′ such that T z ′ T_{z'} T z ′ contains a vertex v ∈ B ( z , r z ) v\in B(z,r_z) v ∈ B ( z , r z ) . Therefore,
dist ( z , z ′ ) ≤ dist ( z , v ) + dist ( v , z ′ ) ≤ r z + h v 8 ≤ r z + r v 4 ≤ 3 2 r z ≤ 2 r z . \operatorname{dist}(z,z')\le\operatorname{dist}(z,v)+\operatorname{dist}(v,z')\le r_z+\frac{h_v}{8}\le r_z+\frac{r_v}{4}\le\frac{3}{2}r_z\le2r_z. dist ( z , z ′ ) ≤ dist ( z , v ) + dist ( v , z ′ ) ≤ r z + 8 h v ≤ r z + 4 r v ≤ 2 3 r z ≤ 2 r z .
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 v v in B ( z , r z ) B(z,r_z) B ( z , r z ) , r v ≤ r z + dist ( z , v ) ≤ 2 r z r_v\le r_z+\operatorname{dist}(z,v)\le2r_z r v ≤ r z + dist ( z , v ) ≤ 2 r z .
In the case that every root z ∈ R z\in R z ∈ R satisfies that dist ( z , ANN ( z ) ) ≤ 4 γ r z \operatorname{dist}(z,\operatorname{ANN}(z))\le4\gamma r_z dist ( z , ANN ( z )) ≤ 4 γ r z , consider a cluster C ∈ C C\in\mathcal{C} C ∈ C . Let q q q be the root in C C C closest to z ( C ) z(C) z ( C ) . By the choice of q q q , every other root x x x in C C C satisfies dist ( x , q ) ≤ dist ( x , z ( C ) ) + dist ( z ( C ) , q ) ≤ 2 ⋅ dist ( x , z ( C ) ) \operatorname{dist}(x,q)\le\operatorname{dist}(x,z(C))+\operatorname{dist}(z(C),q)\le2\cdot\operatorname{dist}(x,z(C)) dist ( x , q ) ≤ dist ( x , z ( C )) + dist ( z ( C ) , q ) ≤ 2 ⋅ dist ( x , z ( C )) . Therefore, the total weight of added edges for all clusters is at most 2 ⋅ ∑ z ∈ R dist ( z , ANN ( z ) ) ≤ 8 γ ⋅ ∑ z ∈ R r z ≤ ( 800 γ / ε ) ∑ z ∈ R h z 2\cdot\sum_{z\in R}\operatorname{dist}(z,\operatorname{ANN}(z))\le8\gamma\cdot\sum_{z\in R}r_z\le(800\gamma/\varepsilon)\sum_{z\in R}h_z 2 ⋅ ∑ z ∈ R dist ( z , ANN ( z )) ≤ 8 γ ⋅ ∑ z ∈ R r z ≤ ( 800 γ / ε ) ∑ z ∈ R h z by Lemma 6.4.
Otherwise, the total added weight is at most n ⋅ OPT ( P ) n\cdot\operatorname{OPT}(P) n ⋅ OPT ( P ) when E \mathcal{E} E does not hold. Therefore, the expected total added weight is at most
800 γ ε E [ ∑ z ∈ R h z ] + n ⋅ Pr [ E c ] ⋅ OPT ( P ) ≤ O ( ( γ / ε ) OPT ( P ) ) . \frac{800\gamma}{\varepsilon}\mathbb{E}\left[\sum_{z\in R}h_z\right]+n\cdot\Pr[\mathcal{E}^c]\cdot\operatorname{OPT}(P)\le O((\gamma/\varepsilon)\operatorname{OPT}(P)). ε 800 γ E [ z ∈ R ∑ h z ] + n ⋅ Pr [ E c ] ⋅ OPT ( P ) ≤ O (( γ / ε ) OPT ( P )) .
MPC implementation using consistent hashing
The above construction uses O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds in addition to those needed to compute r ^ x \hat r_x r ^ x and S x S_x S x for every point x ∈ P x\in P x ∈ P for TruncatedPrim and ForestCutting, and ANN ( z ) \operatorname{ANN}(z) ANN ( z ) for every root z z z of F \mathcal{F} F for Merging-via-Sampling. Now, we describe how to compute them using consistent hashing for Euclidean spaces of dimension d d d and doubling metric spaces of doubling dimension ddim \operatorname{ddim} ddim . Specifically, we will utilize Lemma 2.2 and Lemma 2.3 to construct a ( Γ , Λ ) (\Gamma,\Lambda) ( Γ , Λ ) -hash for a constant Γ \Gamma Γ . We choose γ = 2 Γ + 1 \gamma=2\Gamma+1 γ = 2Γ + 1 , where Γ \Gamma Γ 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 \hat r_x r ^ x . To compute r ^ x \hat r_x r ^ x for every point x ∈ P x\in P x ∈ P , we first compute a 2-approximation D D D of the diameter of P P P in O ( 1 / σ ) O(1/\sigma) 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 D D using Sorting. Let I = { 2 0 , 2 1 , … , 2 ⌈ log D ⌉ } I=\{2^0,2^1,\ldots,2^{\lceil\log D\rceil}\} I = { 2 0 , 2 1 , … , 2 ⌈ l o g D ⌉ } . Each machine constructs I I I . Since ∣ I ∣ = O ( log n ) \lvert I\rvert=O(\log n) ∣ I ∣ = O ( log n ) , I I I fits in a single machine.
In Euclidean spaces, for every scale t ∈ I t\in I t ∈ I , we construct a ( Γ , Λ ) (\Gamma,\Lambda) ( Γ , Λ ) -hash φ t \varphi_t φ t of P P P with diameter bound 2 Γ t 2\Gamma t 2Γ t using Lemma 2.2. Here, Γ = O ( 1 / σ ) \Gamma=O(1/\sigma) Γ = O ( 1/ σ ) and Λ = O ( n σ ) \Lambda=O(n^\sigma) Λ = O ( n σ ) . In particular, we create one copy of P P P for each of the O ( log n ) O(\log n) O ( log n ) scales and construct all hashes in parallel. For a scale t t t and each point x ∈ P x\in P x ∈ P , let N t ( x ) = φ t − 1 ( φ t ( B ( x , t ) ) ∩ P ) N_t(x)=\varphi_t^{-1}(\varphi_t(B(x,t))\cap P) N t ( x ) = φ t − 1 ( φ t ( B ( x , t )) ∩ P ) . For each point x ∈ P x\in P x ∈ P , we compute the minimum scale t x = min { t ∈ I : ∣ N t ( x ) ∣ ≥ k } t_x=\min\{t\in I:\lvert N_t(x)\rvert\ge k\} t x = min { t ∈ I : ∣ N t ( x )∣ ≥ k } . To do this, for every t ∈ I t\in I t ∈ I , we aggregate the number of points in N t x ( x ) N_{t_x}(x) N t x ( x ) . Then, we set r ^ x : = γ t x \hat{r}_x := \gamma t_x r ^ x := γ t x . Since N t x ( x ) ⊆ B ( x , ( 1 + 2 Γ ) t x ) ∩ P ⊆ B ( x , r ^ x ) ∩ P N_{t_x}(x) \subseteq B(x,(1+2\Gamma)t_x) \cap P \subseteq B(x,\hat{r}_x) \cap P N t x ( x ) ⊆ B ( x , ( 1 + 2Γ ) t x ) ∩ P ⊆ B ( x , r ^ x ) ∩ P , ∣ B ( x , r ^ x ) ∩ P ∣ ≥ k |B(x,\hat{r}_x) \cap P| \ge k ∣ B ( x , r ^ x ) ∩ P ∣ ≥ k . Therefore, r x ≤ r ^ x r_x \le\hat{r}_x r x ≤ r ^ x . Moreover, by the choice of t x t_x t x , r ^ x ≤ 2 γ r x \hat{r}_x \le2\gamma r_x r ^ x ≤ 2 γ r x .
In doubling metric spaces, we compute r ^ x \hat{r}_x r ^ x similarly. For every scale t ∈ I t \in I t ∈ I , we construct a ( Γ , Λ ) (\Gamma,\Lambda) ( Γ , Λ ) -hash φ t \varphi_t φ t of P P P with diameter bound Γ t \Gamma t Γ t and its corresponding approximate neighborhood hash pairs in parallel using Lemma 2.3 . Here, Γ = O ( 1 ) \Gamma= O(1) Γ = O ( 1 ) and Λ = 2 O ( d d i m / Γ ) \Lambda= 2^{O(\mathrm{ddim}/\Gamma)} Λ = 2 O ( ddim /Γ ) in a doubling metric space. In this case, we cannot obtain N t ( x ) N_t(x) N t ( x ) immediately from Lemma 2.3 . For each point x ∈ P x \in P x ∈ P , we count the number of points in A P ( x , t ) A_P(x,t) A P ( x , t ) in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using Aggregation. Then, we compute the minimum scale t x = min { t ∈ I : ∣ A P ( x , t ) ∣ ≥ k } t_x = \min\{t \in I : |A_P(x,t)| \ge k\} t x = min { t ∈ I : ∣ A P ( x , t ) ∣ ≥ k } , and set r ^ x : = γ t x \hat{r}_x := \gamma t_x r ^ x := γ t x . Since A P ( x , t x ) ⊆ B ( x , 2 Γ t x ) ∩ P ⊆ B ( x , r ^ x ) ∩ P A_P(x,t_x) \subseteq B(x,2\Gamma t_x) \cap P \subseteq B(x,\hat{r}_x) \cap P A P ( x , t x ) ⊆ B ( x , 2Γ t x ) ∩ P ⊆ B ( x , r ^ x ) ∩ P , we have r x ≤ r ^ x r_x \le\hat{r}_x r x ≤ r ^ x . Moreover, by the choice of t x t_x t x , r ^ x ≤ 2 γ r x \hat{r}_x \le2\gamma r_x r ^ x ≤ 2 γ r x .
Computing S x S_x S x and collecting it on a single machine. Recall that for a point x ∈ P x \in P x ∈ P , S x S_x S x is the set of points containing B ( x , ε r ^ x ) ∩ P B(x,\varepsilon\hat{r}_x) \cap P B ( x , ε r ^ x ) ∩ P and contained in B ( x , γ ε r ^ x ) ∩ P B(x,\gamma\varepsilon\hat{r}_x) \cap P B ( x , γ ε r ^ x ) ∩ P . We construct S x S_x S x similarly to how we compute r ^ x \hat{r}_x r ^ x . In particular, we collect S x S_x S x into a single machine. Let I ′ = ε γ I = { ε γ 2 0 , ε γ 2 1 , … } I' = \varepsilon\gamma I = \{\varepsilon\gamma2^0,\varepsilon\gamma2^1,\ldots\} I ′ = ε γ I = { ε γ 2 0 , ε γ 2 1 , … } . Note that for every point x ∈ P x \in P x ∈ P , ε r ^ x ∈ I ′ \varepsilon\hat{r}_x \in I' ε r ^ x ∈ I ′ .
We first construct S x S_x S x . In Euclidean spaces, for each t ∈ I ′ t \in I' t ∈ I ′ , we construct a ( Γ , Λ ) (\Gamma,\Lambda) ( Γ , Λ ) -hash φ t \varphi_t φ t with diameter bound 2 Γ t 2\Gamma t 2Γ t . We set S x : = N ε r ^ x ( x ) S_x := N_{\varepsilon\hat{r}_x}(x) S x := N ε r ^ x ( x ) . In doubling metric spaces, for each t ∈ I ′ t \in I' t ∈ I ′ , we construct a ( Γ , Λ ) (\Gamma,\Lambda) ( Γ , Λ ) -hash φ t \varphi_t φ t with diameter bound Γ t \Gamma t Γ t and its corresponding approximate neighborhood hash pairs. We set S x : = A P ( x , ε r ^ x ) S_x := A_P(x,\varepsilon\hat{r}_x) S x := A P ( x , ε r ^ x ) . Note that in both cases, B ( x , ε r ^ x ) ∩ P ⊆ S x ⊆ B ( x , ε γ r ^ x ) ∩ P ⊆ B ( x , 2 ε γ 2 r x ) B(x,\varepsilon\hat{r}_x) \cap P \subseteq S_x \subseteq B(x,\varepsilon\gamma\hat{r}_x) \cap P \subseteq B(x,2\varepsilon\gamma^2r_x) B ( x , ε r ^ x ) ∩ P ⊆ S x ⊆ B ( x , ε γ r ^ x ) ∩ P ⊆ B ( x , 2 ε γ 2 r x ) . Therefore, ∣ S x ∣ ≤ k |S_x| \le k ∣ S x ∣ ≤ k , since 2 ε γ 2 < 1 2\varepsilon\gamma^2 < 1 2 ε γ 2 < 1 .
We now collect S x S_x S x on a single machine in parallel in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds, using Broadcasting. In Euclidean spaces, we assign O ( m k d ) = O ( n 1 + σ / 2 ) O(mkd) = O(n^{1+\sigma/2}) O ( mk d ) = O ( n 1 + σ /2 ) additional space for the collected sets. We allocate O ( k d ) O(kd) O ( k d ) space to each point x x x , and let M x M_x M x denote its assigned machine, ensuring that the total allocated space on each machine is O ( n σ ) O(n^\sigma) O ( n σ ) . For every t ∈ I ′ t \in I' t ∈ I ′ and y ∈ P y \in P y ∈ P , we create a record ( ( t , φ t ( y ) ) , y ) ((t,\varphi_t(y)),y) (( t , φ t ( y )) , y ) . For each x ∈ P x \in P x ∈ P , we create a request ( ( ε r ^ x , q ) , M x ) ((\varepsilon\hat{r}_x,q),M_x) (( ε r ^ x , q ) , M x ) for every q ∈ φ ε r ^ x ( B ( x , ε r ^ x ) ) q \in\varphi_{\varepsilon\hat{r}_x}(B(x,\varepsilon\hat{r}_x)) 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 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. For each request ( ( t , q ) , M x ) ((t,q),M_x) (( t , q ) , M x ) , we send y y y to M x M_x M x for every record ( ( t , q ) , y ) ((t,q),y) (( t , q ) , y ) using Broadcasting.9 This collects exactly S x S_x S x for each x x x . Since ∣ S x ∣ ≤ k |S_x| \le k ∣ S x ∣ ≤ k , the collection respects the allocated space and takes O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds.
Similar to the Euclidean case, in doubling metric spaces, we assign O ( m k ) = O ( n 1 + σ / 2 ) O(mk) = O(n^{1+\sigma/2}) O ( mk ) = O ( n 1 + σ /2 ) additional space for the collected sets, and allocate O ( k ) O(k) O ( k ) space to each point and create a record ( t , φ t ( y ) , y ) (t,\varphi_t(y),y) ( t , φ t ( y ) , y ) for every point y ∈ P y \in P y ∈ P . For each x ∈ P x \in P x ∈ P , we create a request ( ε r ^ x , q , x , M x ) (\varepsilon\hat{r}_x,q,x,M_x) ( ε r ^ x , q , x , M x ) for every approximate neighborhood hash pair ( x , q ) (x,q) ( x , q ) of φ ε r ^ x \varphi_{\varepsilon\hat{r}_x} φ ε r ^ x . Then, we can collect S x S_x S x as in the Euclidean case.
Computing nearest sampled root. To compute ANN ( z ) \operatorname{ANN}(z) ANN ( z ) for every root z ∈ R z \in R z ∈ R , we use a consistent hash φ t \varphi_t φ t for every t ∈ I t \in I t ∈ I as we compute r ^ x \hat{r}_x r ^ x . We first compute the minimum scale t z t_z t z such that N t z ( z ) N_{t_z}(z) N t z ( z ) in the Euclidean case and A P ( z , t z ) A_P(z,t_z) A P ( z , t z ) in the doubling metric space contain at least one sampled root. We then choose an arbitrary sampled root in N t z ( z ) N_{t_z}(z) N t z ( z ) or A P ( z , t z ) A_P(z,t_z) A P ( z , t z ) as ANN ( z ) \operatorname{ANN}(z) ANN ( z ) . Note that dist ( z , ANN ( z ) ) ≤ γ t z ≤ 2 γ dist ( z , X ) \operatorname{dist}(z,\operatorname{ANN}(z)) \le\gamma t_z \le2\gamma\operatorname{dist}(z,X) dist ( z , ANN ( z )) ≤ γ t z ≤ 2 γ dist ( z , X ) , where X X X is the set of sampled roots.
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 ) \sigma,\varepsilon\in(0,1) σ , ε ∈ ( 0 , 1 ) . There are randomized MPC algorithms that return an approximate TSP with the following guarantees.
For a general metric on n n n points given by all pairwise distances, the algorithm returns a ( 2 + ε ) (2+\varepsilon) ( 2 + ε ) -approximate TSP tour in O ( log ( 1 / ( σ ε ) ) / σ 2 ) O(\log(1/(\sigma\varepsilon))/\sigma^2) O ( log ( 1/ ( σ ε )) / σ 2 ) rounds, using n σ n^\sigma n σ local space and O ~ ( n 2 ) \widetilde{O}(n^2) O ( n 2 ) total space.
For a set of n n n points in R d \mathbb{R}^d R d , the algorithm returns an O ( 1 / σ 4 ) O(1/\sigma^4) O ( 1/ σ 4 ) -approximate TSP tour in O ( 1 / σ 2 ) O(1/\sigma^2) O ( 1/ σ 2 ) rounds, using ( d n ) σ (dn)^\sigma ( d n ) σ local space and O ( n d + n 1 + σ ) O(nd+n^{1+\sigma}) O ( n d + n 1 + σ ) total space.
For a set of n n n points in a metric space of doubling dimension ddim \operatorname{ddim} ddim satisfying σ log n ≥ Ω ( ddim ) \sigma\log n \ge\Omega(\operatorname{ddim}) σ log n ≥ Ω ( ddim ) , the algorithm returns an O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) -approximate TSP tour in O ( ddim / σ 4 ) O(\operatorname{ddim}/\sigma^4) O ( ddim / σ 4 ) rounds, using n σ n^\sigma n σ local space and O ~ ( n 1 + σ ) ⋅ 2 O ( ddim ) \widetilde{O}(n^{1+\sigma})\cdot2^{O(\operatorname{ddim})} O ( n 1 + σ ) ⋅ 2 O ( ddim ) total space.
Each algorithm succeeds with probability at least 1 − n − Ω ( 1 ) 1-n^{-\Omega(1)} 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 α \alpha α , we can construct a 2 α 2\alpha 2 α -approximate TSP in O ( 1 / σ ) O(1/\sigma) 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 § 5 and § 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 [35 ] .
Lemma 7.2 ([35 ] ). Let σ ∈ ( 0 , 1 ) \sigma\in(0,1) σ ∈ ( 0 , 1 ) be a fixed constant. Suppose that we are given
a partition C \mathcal{C} C over a set V V V of n n n vertices,
for each cluster in C \mathcal{C} C , a spanning tree of the cluster and its Euler tour,
a spanning tree T T T , and its Euler tour where each vertex corresponds to a cluster in C \mathcal{C} 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 \mathcal{C} C using the edges of T T T . It takes O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds, using O ( n σ ) O(n^\sigma) O ( n σ ) local space and O ( n ) O(n) 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 \mathcal{F} F obtained by Lemma 4.3, we first construct an Euler tour A A A starting at the root and visiting the children of each vertex in lexicographical order.
We first compute the number s ( v ) s(v) s ( v ) of vertices in the subtree of F \mathcal{F} F rooted at each vertex v v v . Let P v P_v P v denote the path from the root R ( v ) \mathrm{R}(v) R ( v ) to v v v in F \mathcal{F} F . By the assumption in Lemma 4.3, F v = { u ∈ V ( F ) : dist F ( v , u ) ≤ a v } F_v=\{u\in V(F):\operatorname{dist}_{F}(v,u)\le a_v\} F v = { u ∈ V ( F ) : dist F ( v , u ) ≤ a v } is stored in a single machine. Therefore, P v P_v P v is stored in a single machine since P v ⊆ F v P_v\subseteq F_v P v ⊆ F v by the definition of a low-cost forest partition. For each vertex u ∈ P v u\in P_v u ∈ P v , we construct a record ( v , u ) (v,u) ( v , u ) . The number of records whose second vertex is v v v equals s ( v ) s(v) s ( v ) . Hence, we can compute all subtree sizes in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using Sorting and Aggregation.
We next determine the position of each directed edge in A A A using s ( ⋅ ) s(\cdot) s ( ⋅ ) . For every non-root vertex v v v , let B ( v ) B(v) B ( v ) be the total number of vertices in the subtrees rooted at the siblings before visiting v v v in A A A . Specifically, if c 1 , … , c k c_1,\ldots,c_k c 1 , … , c k are the children of a vertex in lexicographical order, then
B ( c i ) = ∑ j < i s ( c j ) . B(c_i)=\sum_{j<i}s(c_j). B ( c i ) = j < i ∑ s ( c j ) .
We compute these values by sorting vertices by their parent and lexicographical order and taking exclusive prefix sums of the subtree sizes s ( ⋅ ) s(\cdot) s ( ⋅ ) within the children of each vertex. We then broadcast s ( v ) s(v) s ( v ) and B ( v ) B(v) B ( v ) to every machine storing a neighborhood F u F_u F u that contains v v v . These take O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds by using Sorting, PrefixSum, and Broadcasting. Suppose that P v = ( r ( v ) = v 0 , v 1 , v 2 , … , v k = v ) P_v=(r(v)=v_0,v_1,v_2,\ldots,v_k=v) P v = ( r ( v ) = v 0 , v 1 , v 2 , … , v k = v ) . Note that, after first visiting v i v_i v i , the tour A A A visits the subtrees rooted at the siblings preceding v i + 1 v_{i+1} v i + 1 and then moves to v i + 1 v_{i+1} v i + 1 , traversing 1 + 2 B ( v i + 1 ) 1+2B(v_{i+1}) 1 + 2 B ( v i + 1 ) edges in total. Therefore, the directed edge from the parent of v v v to v v v has position ∑ u ∈ P v ∖ { r ( v ) } ( 1 + 2 B ( u ) ) \sum_{u\in P_v\setminus\{r(v)\}}(1+2B(u)) ∑ u ∈ P v ∖ { r ( v )} ( 1 + 2 B ( u )) in A A A . After first visiting v v v , the tour traverses the 2 ( s ( v ) − 1 ) 2(s(v)-1) 2 ( s ( v ) − 1 ) directed edges within its subtree before returning to its parent. Consequently, the reverse edge has position ( ( ∑ u ∈ P v ∖ { r ( v ) } ( 1 + 2 B ( u ) ) ) + 2 s ( v ) − 1 ) \left(\left(\sum_{u\in P_v\setminus\{r(v)\}}(1+2B(u))\right)+2s(v)-1\right) ( ( ∑ u ∈ P v ∖ { r ( v )} ( 1 + 2 B ( u )) ) + 2 s ( v ) − 1 ) in A A A . Since P v P_v P v 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 \mathcal{F} F . When we merge some trees by Merging-via-Leader-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 / σ ) O(1/\sigma) 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-Leader-Compression and Merging-via-Sampling.
Lemma 7.3. Given a low-cost forest partition F \mathcal{F} F constructed by Lemma 4.3, we can compute an Euler tour of each tree of F \mathcal{F} F in O ( 1 / σ ) O(1/\sigma) 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 / σ ) O(1/\sigma) 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 C C in the light contraction or light partition at a given level. The vertices of C C 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 T C T_C T C specifies how these trees are joined, and its Euler tour is available from the construction above. Moreover, for each edge of T C T_C T C , 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 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. Since there are O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) levels, this merging procedure takes O ( 1 / σ 2 ) O(1/\sigma^2) O ( 1/ σ 2 ) additional MPC rounds, using O ( n σ ) O(n^\sigma) O ( n σ ) local space and O ( n ) O(n) O ( n ) total space. Therefore, we conclude Theorem 7.1.
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 [1 , 35 ] . The round complexity for general metrics matches the dependence on ε \varepsilon ε in the known lower bound [1 ] under the 1-vs-2-cycles conjecture. Our results also lead to several open questions.
( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate Euclidean MST. Our algorithm constructs a constant-factor approximate Euclidean MST in O ( 1 ) O(1) O ( 1 ) rounds, whereas the MST cost can already be estimated within a factor of ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) in O ( 1 ) O(1) O ( 1 ) rounds using near-linear total space [12 ] . Applying our general-metric algorithm after computing all pairwise distances also yields a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate tree, but requires O ~ ( n d + n 2 ) \widetilde{O}(nd+n^2) O ( n d + n 2 ) total space. Can a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximate Euclidean MST be constructed in O ( 1 ) O(1) O ( 1 ) rounds using ( n d ) σ (nd)^\sigma ( n d ) σ local space per machine and subquadratic additional total space?
Near-linear total space for Euclidean spaces. Even for a constant approximation factor, our constant-round algorithm uses O ( n d + n 1 + σ ) O(nd+n^{1+\sigma}) O ( n d + n 1 + σ ) total space. Can this be reduced to O ~ ( n d ) \widetilde{O}(nd) O ( n d ) while retaining O ( 1 ) O(1) O ( 1 ) rounds and ( n d ) σ (nd)^\sigma ( n d ) σ 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 + ε ) (2+\varepsilon) ( 2 + ε ) -approximate Steiner tree in general metric spaces and an O ( 1 ) O(1) O ( 1 ) -approximate Steiner tree in Euclidean and doubling metric spaces [26 , 42 ] . A recent fully scalable MPC algorithm [51 ] computes a ( 2 ( 1 − 1 / ∣ R ∣ ) ) (2(1-1/|R|)) ( 2 ( 1 − 1/∣ R ∣ )) -approximate Steiner tree in weighted graphs in O ( σ − 1 log n + D ) O(\sigma^{-1}\log n+D) O ( σ − 1 log n + D ) MPC rounds, using O ( n 3 − σ / 2 ) O(n^{3-\sigma/2}) O ( n 3 − σ /2 ) total space, where R R R is the terminal set and D D D is the shortest-path diameter. However, in the sequential setting, a ( ln 4 + ε ) (\ln4+\varepsilon) ( 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 [20 ] present a constant-round fully scalable MPC algorithm for constructing an exact Euclidean MST in two dimensions using linear total space. As noted in [20 ] , 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 ( n 2 ) O(n^2) O ( n 2 ) messages, when each node initially knows its incident edges and their weights [43 ] . Pemmaraju and Sardeshmukh [46 ] give an exact MST algorithm using O ( log ∗ n / ρ ) O(\log^{*} n/\rho) O ( log ∗ n / ρ ) rounds and O ~ ( n 1 + ρ / ρ ) \widetilde{O}(n^{1+\rho/\rho}) O ( n 1 + ρ / ρ ) messages, for any 0 < ρ ≤ 1 0<\rho\leq1 0 < ρ ≤ 1 . Moreover, [30 ] presented a constant-factor approximate MST algorithm for doubling metric spaces with ddim = O ( 1 ) \operatorname{ddim}=O(1) ddim = O ( 1 ) , using constant rounds and O ( n 2 ) O(n^2) O ( n 2 ) messages. Coordinate input has also been studied: for n n n distinct points in { 0 , 1 } n \{0,1\}^n { 0 , 1 } n given one per node, Lingas [37 ] constructs a constant-factor approximate Hamming MST in O ( log 3 n ) O(\log^3 n) O ( log 3 n ) rounds. Can we construct a constant-factor approximate MST in high-dimensional Euclidean space in the Congested Clique model using constant rounds and O ~ ( n ) \widetilde{O}(n) O ( n ) messages when each node initially holds only the coordinates of one point?
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.
Getting rid of the assumption on bounded spread
In the Euclidean and doubling cases, we assume polynomial spread on an input point set P P P of size n n n : the ratio Φ \Phi Φ of the largest to the smallest nonzero pairwise distance is polynomial in n n n . The only place where this assumption is used is to apply consistent hashing. In particular, we construct consistent hashes with O ( log Φ ) O(\log\Phi) O ( log Φ ) different radius scales in parallel. Then the space complexity becomes O ( n log Φ ) O(n\log\Phi) O ( n log Φ ) . In this section, we preprocess P P P so that this assumption is satisfied.
Euclidean space
In a d d d -dimensional Euclidean space, we can use a grid as follows. Fix an arbitrary point x ∈ P x \in P x ∈ P , and compute Δ : = max p ∈ P dist ( p , x ) \Delta:= \max_{p\in P}\operatorname{dist}(p,x) Δ := max p ∈ P dist ( p , x ) in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using O ( d n ) O(dn) O ( d n ) total space. Then consider a grid whose cells have diameter Δ / ( n 2 d ) \Delta/(n^2\sqrt{d}) Δ/ ( n 2 d ) . For every point p ∈ P p \in P p ∈ P , we move it to the center of the grid cell containing p p p . The error induced by the perturbation is at most Δ / n ≤ OPT ( P ) / n ≤ ε ⋅ OPT ( P ) \Delta/n \leq\operatorname{OPT}(P)/n \leq\varepsilon\cdot\operatorname{OPT}(P) Δ/ n ≤ OPT ( P ) / n ≤ ε ⋅ OPT ( P ) for sufficiently large n n n . In this way, the spread of the resulting point set becomes O ( d n 2 ) O(dn^2) O ( d n 2 ) since its diameter is O ( Δ ) O(\Delta) O ( Δ ) . Since d = O ( log n ) d = O(\log n) 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 C C , we also choose an original point p C ∈ P ∩ C p_C \in P \cap C p C ∈ P ∩ C and associate its identifier with every point in C C C . We apply the algorithm in § 6 to the distinct cell centers. Note that the additional space needed to duplicate the point set across all scales is O ( n d log ( d n 2 ) ) ≤ O ( n 1 + σ ) O(nd\log(dn^2)) \leq O(n^{1+\sigma}) O ( n d log ( d n 2 )) ≤ O ( n 1 + σ ) , since d = O ( log n ) d = O(\log n) 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 P 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 C C to p C p_C p C . Choosing these points and constructing the corresponding edges take O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds using Sorting, Aggregation, and Broadcasting, with O ( n d ) O(nd) O ( n d ) total space.
Doubling space
We show how to preprocess an n n n -point metric ( X , dist ) (X,\operatorname{dist}) ( X , dist ) with doubling dimension d ≤ c σ log n d \leq c\sigma\log n d ≤ c σ log n , for a sufficiently small constant c > 0 c > 0 c > 0 , so that the resulting point set has spread O ( n 8 ) O(n^8) O ( n 8 ) with high probability. The error induced by the preprocessing is at most ε ⋅ OPT ( X ) \varepsilon\cdot\operatorname{OPT}(X) ε ⋅ OPT ( X ) for any fixed approximation factor and sufficiently large n n n . The preprocessing uses O ~ ( n ) \widetilde{O}(n) O ( n ) total space, n σ n^\sigma n σ local space per machine, and O ( 1 ) O(1) O ( 1 ) rounds for fixed σ \sigma σ . We assume that each point is represented by O ( 1 ) O(1) 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 x \in X x ∈ X , and compute Δ : = max p ∈ X dist ( x , p ) \Delta:= \max_{p\in X}\operatorname{dist}(x,p) Δ := max p ∈ X dist ( x , p ) . Then Δ ≤ OPT ( X ) \Delta\leq\operatorname{OPT}(X) Δ ≤ OPT ( X ) and the diameter of X X X is at most 2 Δ 2\Delta 2Δ . Let τ = Δ / n 2 \tau= \Delta/n^2 τ = Δ/ n 2 and s = n σ s = n^\sigma s = n σ . Recall that s s 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 [45 ] .
Algorithm. Starting with a single piece X X X , we process the remaining pieces in parallel in phases. For each piece U U U with ∣ U ∣ > s |U| > s ∣ U ∣ > s , take q = Θ ( β s log 2 n ) q = \Theta(\beta\sqrt{s\log^2 n}) q = Θ ( β s log 2 n ) independent uniform samples from U U U , keeping multiplicities, where β = 2 O ( d ) \beta= 2^{O(d)} β = 2 O ( d ) is a sufficiently large integer. Since q ≤ s 3 / 4 q \leq s^{3/4} q ≤ s 3/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 Y Y , find a smallest-radius ball B ( z , r ) B(z,r) B ( z , r ) centered at a point z z z in Y Y Y containing at least ⌈ ∣ Y ∣ / β ⌉ \lceil|Y|/\beta\rceil ⌈ ∣ Y ∣/ β ⌉ sampled points. If r > τ r > \tau r > τ , choose the cut radius uniformly from [ r , 2 r ] [r,2r] [ r , 2 r ] and recurse on both sides. Otherwise, cut with the ball B ( z , τ ) B(z,\tau) B ( z , τ ) , make the inside a final part, and recurse only on the outside. We do this until every part either becomes a final 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 T 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 T T to all the machines holding U U U . We then partition U U U according to the recursion tree: each point p ∈ U p \in U p ∈ U follows the cuts from the root to a leaf of T T 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 τ \tau τ -ball as its representative. For each other nonempty piece U ′ U' U ′ , if U ′ U' U ′ fits on one machine, we gather U ′ U' U ′ onto a single machine and repeatedly choose an arbitrary remaining point z ∈ U ′ z \in U' z ∈ U ′ and remove the points in B ( z , τ ) B(z,\tau) B ( z , τ ) from U ′ U' U ′ as a final part with representative z z z . Otherwise, we recursively process U ′ U' U ′ in the next phase.
After O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) phases, report failure if there is a remaining piece. Otherwise, the final parts form a partition of X X X , with each part having a representative. Let X ′ X' X ′ be the set of all such representatives, and let f ( p ) f(p) f ( p ) be the representative of the part containing p p p . By construction, dist ( p , f ( p ) ) ≤ τ \operatorname{dist}(p,f(p)) \le\tau dist ( p , f ( p )) ≤ τ for every p ∈ X p \in X p ∈ X .
Analysis. This algorithm is a simplified version of the algorithm in [45 ] . Their analysis immediately implies that our construction uses O ( 1 / σ 2 ) O(1/\sigma^2) O ( 1/ σ 2 ) rounds and O ( n ) O(n) O ( n ) total space. We analyze the error induced by the perturbation. The distance between two points increases by at most 2 τ 2\tau 2 τ since dist ( p , f ( p ) ) ≤ τ \operatorname{dist}(p,f(p)) \le\tau dist ( p , f ( p )) ≤ τ for every p ∈ X p \in X p ∈ X by construction, so OPT ( X ′ ) ≤ OPT ( X ) + 2 n τ \operatorname{OPT}(X') \le\operatorname{OPT}(X) + 2n\tau OPT ( X ′ ) ≤ OPT ( X ) + 2 n τ . Since OPT ( X ) ≥ Δ = n 2 τ \operatorname{OPT}(X) \ge\Delta= n^2\tau OPT ( X ) ≥ Δ = n 2 τ , we have OPT ( X ′ ) ≤ ( 1 + o ( 1 ) ) ⋅ OPT ( X ) \operatorname{OPT}(X') \le(1+o(1)) \cdot\operatorname{OPT}(X) OPT ( X ′ ) ≤ ( 1 + o ( 1 )) ⋅ OPT ( X ) .
We show that the spread of X ′ X' X ′ is O ( n 8 ) O(n^8) O ( n 8 ) . For two distinct points of X ′ X' X ′ , consider the first cut separating them. There are two cases. In the first case, the cut is B ( z , τ ) B(z,\tau) B ( z , τ ) . One representative is its center z z z and the other lies outside B ( z , τ ) B(z,\tau) B ( z , τ ) , so their distance is greater than τ \tau τ . In the second case, the cut is B ( z , r ′ ) B(z,r') B ( z , r ′ ) , where r ′ r' r ′ is chosen uniformly from [ r , 2 r ] [r,2r] [ r , 2 r ] with r > τ r>\tau r > τ . Conditioned on the preceding choices, such a cut separates two fixed input points with probability at most their distance divided by τ \tau τ . There are O ( n ) O(n) 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 ) 1-O(n^{-3}) 1 − O ( n − 3 ) , no pair at distance less than τ / n 6 \tau/n^6 τ / n 6 is separated by a random cut. Together with the sampling guarantee, distinct representatives are therefore at distance at least τ / n 6 \tau/n^6 τ / n 6 with high probability. Their maximum distance is at most 2 Δ 2\Delta 2Δ , so the spread of X ′ X' X ′ is O ( n 8 ) O(n^8) O ( n 8 ) . Its doubling dimension is at most 2 d 2d 2 d . Once we can compute a 1 + ε 1+\varepsilon 1 + ε -approximate MST of X ′ X' X ′ , then it yields a 1 + o ( 1 ) + ε 1+o(1)+\varepsilon 1 + o ( 1 ) + ε -approximate MST of X X X .
Proof of Theorem 1.3 assuming Lemma 6.3
We first describe our algorithm. Let L = ⌈ 20 / σ ⌉ L = \lceil20/\sigma\rceil L = ⌈ 20/ σ ⌉ , and keep b = n σ / 10 b = n^{\sigma/10} b = n σ /10 fixed throughout the algorithm. Starting with P = Q 0 P = Q_0 P = Q 0 , we repeatedly compute a ( b , O ( 1 ) ) (b,O(1)) ( b , O ( 1 )) -randomized light partition. At level i i i , we are given a set Q i ⊆ P Q_i \subseteq P Q i ⊆ P of representative points. Let ( C i , { T C } C ∈ C i ) (\mathcal{C}_i,\{T_C\}_{C\in\mathcal{C}_i}) ( C i , { T C } C ∈ C i ) be a ( b , O ( 1 ) ) (b,O(1)) ( b , O ( 1 )) -randomized light partition of Q i Q_i Q i obtained by using Lemma 6.3. We choose an arbitrary representative point per cluster in C i \mathcal{C}_i C i , and let Q i + 1 Q_{i+1} Q i + 1 be the set of chosen representative points, which will be passed to the next level. Once n σ / 2 n^{\sigma/2} 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 O(m/b)+1 O ( m / b ) + 1 ; while m > n σ / 2 m > n^{\sigma/2} m > n σ /2 , this is at most m / n σ / 10 m/n^{\sigma/10} m / n σ /10 for sufficiently large n n n . Thus L L L successful calls suffice. The union of the trees constructed at all levels forms a spanning tree on P P P . We denote it by T T T .
We now show that T T T is an O ( 1 ) O(1) O ( 1 ) -approximate MST in expectation. Suppose that there are ℓ < L \ell< L ℓ < L levels. For each 0 ≤ i ≤ ℓ 0 \le i \le\ell 0 ≤ i ≤ ℓ , let m i = ∣ Q i ∣ m_i = |Q_i| m i = ∣ Q i ∣ . For every i < ℓ i < \ell i < ℓ , the trees constructed within the clusters in C i C_i C i form a spanning forest on Q i Q_i Q i , and Q i + 1 Q_{i+1} Q i + 1 contains exactly one representative from each tree. Therefore, adding the spanning forest of Q i + 1 Q_{i+1} Q i + 1 merges those trees in the forest of Q i Q_i Q i without creating a cycle, and thus T T T is a spanning tree of P P P . Note that ∣ E ( T ) ∣ = ∑ i = 0 ℓ − 1 ( ∑ C ∈ C i ( ∣ C ∣ − 1 ) ) + ( m ℓ − 1 ) = ∑ i = 0 ℓ − 1 ( m i − m i + 1 ) + ( m ℓ − 1 ) = n − 1 |E(T)| = \sum_{i=0}^{\ell-1}(\sum_{C\in\mathcal{C}_i}(|C|-1))+(m_\ell-1) = \sum_{i=0}^{\ell-1}(m_i-m_{i+1})+(m_\ell-1)=n-1 ∣ E ( T ) ∣ = ∑ i = 0 ℓ − 1 ( ∑ C ∈ C i ( ∣ C ∣ − 1 )) + ( m ℓ − 1 ) = ∑ i = 0 ℓ − 1 ( m i − m i + 1 ) + ( m ℓ − 1 ) = n − 1 .
Consider an MST T ∗ T^* T ∗ of P P P and an Euler tour of the multigraph obtained by duplicating all edges of T ∗ T^* T ∗ . The length of the Euler tour is 2 ⋅ ω ( T ∗ ) 2\cdot\omega(T^*) 2 ⋅ ω ( T ∗ ) . For each 0 ≤ i ≤ ℓ 0\le i\le\ell 0 ≤ i ≤ ℓ , let ( q 1 , q 2 , … , q m i ) (q_1,q_2,\ldots,q_{m_i}) ( q 1 , q 2 , … , q m i ) be the points in Q i Q_i Q i ordered by their first occurrence in the Euler tour. Then, ∑ j = 1 m i dist ( q j , q j + 1 ) ≤ 2 ⋅ ω ( T ∗ ) \sum_{j=1}^{m_i}\operatorname{dist}(q_j,q_{j+1})\le2\cdot\omega(T^*) ∑ j = 1 m i dist ( q j , q j + 1 ) ≤ 2 ⋅ ω ( T ∗ ) by the triangle inequality, where q m i + 1 = q 1 q_{m_i+1}=q_1 q m i + 1 = q 1 . This implies that OPT ( Q i ) ≤ 2 ⋅ ω ( T ∗ ) = 2 OPT ( P ) \operatorname{OPT}(Q_i)\le2\cdot\omega(T^*)=2\operatorname{OPT}(P) OPT ( Q i ) ≤ 2 ⋅ ω ( T ∗ ) = 2 OPT ( 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 ( Q i ) ) O(\operatorname{OPT}(Q_i)) O ( OPT ( Q i )) , conditional on the preceding iterations and using fresh random choices at that level. Thus, summing over the O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) possible levels and including the final MST, we have
E [ ω ( T ) ] = E [ ∑ i = 0 ℓ − 1 ∑ C ∈ C i ω ( T C ) + OPT ( Q ℓ ) ] ≤ O ( ( 1 / σ ) ⋅ OPT ( P ) ) + 2 OPT ( P ) = O ( ( 1 / σ ) ⋅ OPT ( P ) ) . \mathbb{E}[\omega(T)]=\mathbb{E}\left[\sum_{i=0}^{\ell-1}\sum_{C\in\mathcal{C}_i}\omega(T_C)+\operatorname{OPT}(Q_\ell)\right]\le O((1/\sigma)\cdot\operatorname{OPT}(P))+2\operatorname{OPT}(P)=O((1/\sigma)\cdot\operatorname{OPT}(P)). E [ ω ( T )] = E [ i = 0 ∑ ℓ − 1 C ∈ C i ∑ ω ( T C ) + OPT ( Q ℓ ) ] ≤ O (( 1/ σ ) ⋅ OPT ( P )) + 2 OPT ( P ) = O (( 1/ σ ) ⋅ OPT ( P )) .
Each iteration constructs a randomized light partition in O ( ddim / σ 3 ) O(\operatorname{ddim}/\sigma^3) O ( ddim / σ 3 ) MPC rounds. Moreover, we can select representatives locally and update the representative and edge records in O ( 1 / σ ) O(1/\sigma) O ( 1/ σ ) MPC rounds. The MST on Q ℓ Q_\ell Q ℓ is computed locally. Since there are ℓ = O ( 1 / σ ) \ell=O(1/\sigma) ℓ = O ( 1/ σ ) iterations, the algorithm takes O ( ddim / σ 4 ) O(\operatorname{ddim}/\sigma^4) O ( ddim / σ 4 ) MPC rounds in total.
By the Markov inequality, the probability that ω ( T ) > 2 c ⋅ OPT ( P ) \omega(T)>2c\cdot\operatorname{OPT}(P) ω ( T ) > 2 c ⋅ OPT ( P ) is at most 1 / 2 1/2 1/2 for some constant c c c . Thus, by applying Algorithm 2 independently to O ( log n ) O(\log n) O ( log n ) copies of P P P in parallel and returning the tree of minimum total weight, we can construct an O ( 1 ) O(1) O ( 1 ) -approximate MST with high probability. By reusing space across iterations, the bounds in Lemma 6.3 also give n o ( 1 ) n^{o(1)} n o ( 1 ) local space per machine, and O ~ ( n 1 + o ( 1 ) ⋅ 2 O ( ddim ) ) \widetilde{O}(n^{1+o(1)}\cdot2^{O(\operatorname{ddim})}) O ( n 1 + o ( 1 ) ⋅ 2 O ( ddim ) ) total space.
Proof of Lemma 6.5
Lemma 6.5. E [ ∑ z ∈ R h z ] = O ( OPT ( P ) ) \mathbb{E}[\sum_{z\in R}h_z]=O(\operatorname{OPT}(P)) E [ ∑ z ∈ R h z ] = O ( OPT ( P )) , where R R R denotes the set of the roots of the trees of F F F .
Proof. It suffices to show that the right-hand side of Equation (4) is O ( OPT ( P ) ) O(\operatorname{OPT}(P)) O ( OPT ( P )) . The second term of the right-hand side of the equation is O ( OPT ( P ) ) O(\operatorname{OPT}(P)) O ( OPT ( P )) since F F F is contained in the MST of P P P . Hence, we focus on proving ∑ C ∈ cc ( F ) min v ∈ C h v = O ( OPT ( P ) ) \sum_{C\in\operatorname{cc}(F)}\min_{v\in C}h_v=O(\operatorname{OPT}(P)) ∑ C ∈ cc ( F ) min v ∈ C h v = O ( OPT ( P )) .
If F F F has a single component, then C = P C=P C = P , and we have min v ∈ P h v ≤ ε γ 50 ⋅ max x , y ∈ P dist ( x , y ) = O ( OPT ( P ) ) \min_{v\in P}h_v\le\frac{\varepsilon\gamma}{50}\cdot\max_{x,y\in P}\operatorname{dist}(x,y)=O(\operatorname{OPT}(P)) min v ∈ P h v ≤ 50 ε γ ⋅ max x , y ∈ P dist ( x , y ) = O ( OPT ( P )) by Lemma 6.4. Otherwise, let T T T be the MST of P P P from Prim’s algorithm. For a component C C C of F F F , we can choose an edge ( u , v ) ∈ E ( T ) (u,v)\in E(T) ( u , v ) ∈ E ( T ) with u ∈ C u\in C u ∈ C and v ∈ P ∖ C v\in P\setminus C v ∈ P ∖ C . If v ∉ S u v\notin S_u v ∈ / S u , h u ≤ ε r ^ u / 100 < dist ( u , v ) / 100 h_u\le\varepsilon\hat{r}_u/100<\operatorname{dist}(u,v)/100 h u ≤ ε r ^ u /100 < dist ( u , v ) /100 . Consider the call TruncatedPrim ( u , S u , ε r ^ u / 2 , 0 ) \operatorname{TruncatedPrim}(u,S_u,\varepsilon\hat{r}_u/2,0) TruncatedPrim ( u , S u , ε r ^ u /2 , 0 ) . The tree visited by this call is contained in F [ C ] F[C] 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 \varepsilon\hat{r}_u/2 ε r ^ u /2 , the next edge has length at least ε r ^ u / 2 \varepsilon\hat{r}_u/2 ε r ^ u /2 , or all vertices in S u S_u S u are visited. In the first case, ω ( F [ C ] ) ≥ ε r ^ u / 2 \omega(F[C])\ge\varepsilon\hat{r}_u/2 ω ( F [ C ]) ≥ ε r ^ u /2 , and thus 50 ⋅ h u ≤ ε r ^ u / 2 ≤ ω ( F [ C ] ) 50\cdot h_u\le\varepsilon\hat{r}_u/2\le\omega(F[C]) 50 ⋅ h u ≤ ε r ^ u /2 ≤ ω ( F [ C ]) by Lemma 6.4. In the second case, 50 ⋅ h u ≤ ε r ^ u / 2 ≤ dist ( u , v ) 50\cdot h_u\le\varepsilon\hat{r}_u/2\le\operatorname{dist}(u,v) 50 ⋅ h u ≤ ε r ^ u /2 ≤ dist ( u , v ) . In the third case, dist ( u , v ) > ε r ^ u \operatorname{dist}(u,v)>\varepsilon\hat{r}_u dist ( u , v ) > ε r ^ u since B ( u , ε r ^ u ) ∩ P ⊆ S u B(u,\varepsilon\hat{r}_u)\cap P\subseteq S_u B ( u , ε r ^ u ) ∩ P ⊆ S u . Thus, in all four cases, 50 ⋅ h u ≤ ω ( F [ C ] ) + dist ( u , v ) 50\cdot h_u\le\omega(F[C])+\operatorname{dist}(u,v) 50 ⋅ h u ≤ ω ( F [ C ]) + dist ( u , v ) . We then have
∑ C ∈ cc ( F ) min v ∈ C h v ≤ 1 50 ∑ C ∈ cc ( F ) ( ω ( F [ C ] ) + dist ( u C , v C ) ) ≤ 1 50 ( ω ( F ) + 2 ω ( T ) ) = O ( OPT ( P ) ) . \sum_{C\in\operatorname{cc}(F)}\min_{v\in C}h_v\le\frac{1}{50}\sum_{C\in\operatorname{cc}(F)}\left(\omega(F[C])+\operatorname{dist}(u_C,v_C)\right)\le\frac{1}{50}\left(\omega(F)+2\omega(T)\right)=O(\operatorname{OPT}(P)). C ∈ cc ( F ) ∑ v ∈ C min h v ≤ 50 1 C ∈ cc ( F ) ∑ ( ω ( F [ C ]) + dist ( u C , v C ) ) ≤ 50 1 ( ω ( F ) + 2 ω ( T ) ) = O ( OPT ( P )) .
where ( u C , v C ) (u_C,v_C) ( u C , v C ) is the edge in T T T chosen for C C C . The second inequality holds since each edge ( u , v ) (u,v) ( u , v ) of T T T is chosen in at most two components of F F F : one containing u u u and one containing v v v .