## Log Diameter Rounds MST Verification and Sensitivity in MPC

| Sam Coy ∗     | Artur Czumaj †   | Gopinath Mishra ‡      | Anish Mukherjee §   |
|---------------|------------------|------------------------|---------------------|
| University of | University of    | National University of | University of       |
| Warwick       | Warwick          | Singapore              | Warwick             |

## Abstract

We consider two natural variants of the problem of minimum spanning tree (MST) of a graph in the parallel setting: MST verification (verifying if a given tree is an MST) and the sensitivity analysis of an MST (finding the lowest cost replacement edge for each edge of the MST). These two problems have been studied extensively for sequential algorithms and for parallel algorithms in the PRAM model of computation. In this paper, we extend the study to the standard model of Massive Parallel Computation ( MPC ).

It is known that for graphs of diameter D , the connectivity problem can be solved in O (log D + log log n ) rounds on an MPC with low local memory (each machine can store only O n ( δ ) words for an arbitrary constant δ &gt; 0 ) and with linear global memory , that is, with optimal utilization . However, for the related task of finding an MST, we need Ω(log D MST ) rounds, where D MST denotes the diameter of the minimum spanning tree. The state of the art upper bound for MST is O (log n ) rounds; the result follows by simulating existing PRAM algorithms. While this bound may be optimal for general graphs, the benchmark of connectivity and lower bound for MST suggest the target bound of O (log D MST ) rounds, or possibly O (log D MST +log log n ) rounds. As for now, we do not know if this bound is achievable for the MST problem on an MPC with low local memory and linear global memory. In this paper, we show that two natural variants of the MST problem: MST verification and sensitivity analysis of an MST, can be completed in O (log D T ) rounds on an MPC with low local memory and with linear global memory, that is, with optimal utilization; here D T is the diameter of the input 'candidate MST' T . The algorithms asymptotically match our lower bound, conditioned on the 1-vs-2-cycle conjecture.

## 1 Introduction

Over the last decade, the heightened need to solve problems on ever-increasing volumes of data has motivated the successful development of massively parallel computation frameworks, such as MapReduce, Hadoop, Dryad, and Spark, see, e.g., [DG08, Whi12, ZCF + 10]. In turn, the prevalence of these frameworks has led to a huge interest in the design of efficient parallel algorithms.

The Massively Parallel Computing ( MPC ) model is a theoretical model which abstracts these massively parallel computation frameworks. The model was first introduced by Karloff, Suri, and Vassilvitskii [KSV10], and is now the standard theoretical model for these systems (see also, e.g., [ASS + 18a, GSZ11, GLM + 23]).

∗ Department of Computer Science, University of Warwick, UK. E-mail: S.Coy@warwick.ac.uk. Research supported in part by the Centre for Discrete Mathematics and its Applications (DIMAP) and by an EPSRC studentship.

Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP), University of War-

†

wick,

UK. E-mail:

A.Czumaj@warwick.ac.uk.

Research supported in part by the Centre for Discrete Mathematics and its

Applications (DIMAP), by EPSRC award EP/V01305X/1, by a Weizmann-UK Making Connections Grant, by an IBM Award.

§ Department of Computer Science, University of Warwick, UK. E-mail: Anish.Mukherjee@warwick.ac.uk. Research supported in part by the Centre for Discrete Mathematics and its Applications (DIMAP), by EPSRC award EP/V01305X/1.

‡ Department of Computer Science, National University of Singapore, Singapore. E-mail: Gopinath@nus.edu.sg. The work was partly done when the author was a Postdoc at the University of Warwick and the research was supported in part by the Centre for Discrete Mathematics and its Applications (DIMAP) and by EPSRC award EP/V01305X/1.

An MPC is a parallel computing system with m machines . Each of these machines has s words of local memory ; in total the system has m · s = g global memory . The input to an MPC algorithm is arbitrarily distributed among the machines. Computation in the MPC model takes place in synchronous rounds . In each round, each machine does some computation on the data in its local memory. Then, machines exchange messages: each machine may send as many 1 -word messages as it likes to any other machine, as long as in total, each machine sends and receives at most s words in any given round. The complexity of an MPC algorithm is measured in the number of rounds.

The low-space MPC regime, which we consider in this paper, is the most challenging of the local memory regimes usually considered in the MPC model. Nevertheless, it is a more powerful model than the PRAM model: a step of PRAM can be simulated in O (1) rounds of the MPC model and sorting or computing the prefix-sum of N values can be done in O (1) rounds on an MPC with local memory s = O N ( δ ) , see, e.g., [GSZ11].

For graph problems, our input is an edge-weighted graph G = ( V, E ) with n vertices, m edges, and weighting function w : we assume that the weight of any edge can be expressed with O (1) words. In this paper, we focus on the design of low-space (fully scalable) MPC algorithms, where the local memory of each machine is s = O n ( δ ) for some (arbitrary) constant δ ∈ (0 1) , . Our focus is on designing algorithms with optimal utilization , that is, those achieving linear global memory: for graph problems, this means that g = Θ( m + n ) . The goal is to design algorithms that for a given MPC with for local memory s = O n ( δ ) and with linear global memory g minimizes its complexity (the number of rounds performed). Of course, optimally, we would like to achieve a constant number of rounds, but for many problems, the best we could hope for is a sub-logarithmic number of rounds.

In this paper, we study the complexity of important variants of the fundamental graph problem of Minimum Spanning Tree (MST) . The MST problem has been extensively studied for many decades. After many years of extensive research, we know the problem can be solved by a randomized algorithm in O m ( ) -time [KKT95], though we still do not know the exact deterministic complexity of the MST problem (see, e.g., [Cha00, PR02]). Similar efforts have been also taking place for parallel algorithms, largely focusing on PRAM algorithms, where O (log n ) -time algorithms can be achieved with almost optimal total work. Given the importance of the MST problem, there has been also extensive research studying its variations, most prominently the natural variants of MST verification and MST sensitivity problems, see, e.g., [DT97, DRT92, Kin97, KPRS97, Kom84, Pet15].

Definition 1.1 ( MST Verification . ) Given a graph G = ( V, E ) with edges weighted by a function w : E → N , and a tree T ⊆ E , the goal is to determine whether T is an MST of G .

Definition 1.2 ( MST Sensitivity . ) The MST sensitivity problem is for a given graph G = ( V, E ) and an MST T ⊆ E , to calculate a sensitivity value sens ( e ) for all e ∈ E . We define sens ( e ) as:

- · for e ∈ T : the amount by which w e ( ) would have to be increased (with all other edges remaining the same weight) for e to no longer be part of an MST of G ;
- · for e ∈ E \ T : the amount by which w e ( ) would have to be decreased (with all other edges remaining the same weight) for e to be part of an MST of G .

The MST problem has been studied also in the MPC model, extending the earlier research for the sequential model and the PRAM . For super-linear local space ( s = O n ( 1+ δ ) ) and linear local space ( s = O n ( ) ), constant-round algorithms have been developed [LMSV11, JN18, Now21] with optimal utilization. However, for the setting of low-space MPC , which is the main focus of our paper, the situation is fundamentally different. Let D MST denote the smallest diameter of a minimum spanning tree of G . We do not expect a constantrounds MPC algorithm to exist and while there is an O (log D MST ) round algorithm (optimal according to a conditional lower bound) if we are allowed polynomial extra global space [ASS + 18a, CC23, BDE + 19], the best result known with optimal global memory and utilization runs in O (log n ) rounds (e.g., by a simulation of PRAM algorithms). This is quite a large gap, especially for low-diameter network topologies which are common in real-world settings, and whether this gap can be closed is a major open problem in the area of MPC algorithms. In this paper, similarly as it has been done before for sequential and PRAM models, we

study two natural variants of the minimum spanning tree (MST) problem in the MPC model: the MST verification and MST sensitivity problems.

## 1.1 Our Results

We demonstrate that while we do not know whether the MST problem can be solved in an optimal number of rounds on an MPC in the low-memory regime and with optimal utilization, the MST verification and MST sensitivity problems can be solved optimally. 1

Our first main result is an algorithm for the MST verification.

Theorem 3.1 ( MST Verification Algorithm ): Let δ be an arbitrarily small positive constant. Let

G = ( V, E ) be an edge-weighted input graph and let T ⊆ E be a tree. Suppose the diameter of T is D T .

One can decide with high probability whether T is an MST of G in O (log D T ) rounds on an MPC with local memory s = O n ( δ ) and optimal global memory g = O m ( + n ) .

We extend our verification algorithm to the more challenging problem of MST sensitivity, still obtaining a O (log D T ) round algorithm that uses optimal global memory:

Theorem 4.1 ( MST Sensitivity Algorithm ): Let δ be an arbitrarily small positive constant. Let

G = ( V, E ) be an edge-weighted input graph and let T ⊆ E be an MST of G with diameter D T .

The problem of MST sensitivity can be solved in O (log D T ) rounds (with high probability) on an MPC with local memory s = O n ( δ ) and optimal global memory g = O m ( + n ) .

Finally, we complement Theorem 3.1 by showing that this result is optimal: conditioned on the widely believed 1-vs-2-cycle conjecture, Ω(log D T ) rounds are required for MST verification if our input T is an arbitrary set of n -1 edges of G .

Theorem 5.2 ( MST Verification Lower Bound ): Let δ &lt; 1 be an arbitrary positive constant. Let G = ( V, E ) be an edge-weighted graph of diameter D . Let T ⊆ E be a set of n -1 edges of G and let D T be the diameter of T .

Deciding whether T is a minimum spanning forest of G requires Ω(log D T ) rounds, on an MPC with local memory s = O n ( δ ) , unless the 1-vs-2-cycle conjecture is false.

We remark that our algorithms can also deal with the problems above even when the input graph G is not connected, in which case our goal is to study the variants of the minimum spanning forest (MSF) problem. All our algorithms can be easily extended to this more general setting since it is known that finding the connected components in a forest can be solved optimally in the sublinear-memory MPC model; see also Remark 2.4.

## 1.2 Technical Challenges and Contributions

To date, the problem of finding an MST in low-space MPC has been resistant to efficient algorithms with optimal global memory. Our results on the related problems of MST verification and sensitivity overcome several interesting technical challenges. Take MST verification for example: a naive approach to the problem would involve collecting for each vertex u , a path from u to the root of T . Then, we can use prefix-sum in O (1) rounds to, for each ancestor v of u , find the largest edge on a path from u to v in T . Then for all non-tree edges { u, v } , where v is an ancestor of u we can check (using sorting) whether the weight of the non-tree edge is smaller than the largest edge on the path from u to v in T . Doing this for all edges in parallel is the same as checking whether T is an MST.

The problem with this approach, however, is that it requires O D ( T ) memory per vertex, and therefore O m ( + n · D T ) global memory; in the worst case, O n ( 2 ) global memory, which is extremely undesirable, particularly for sparse graphs. To get around this problem, we use an approach of hierarchical clustering

1 Throughout this paper, by high probability we mean the result is correct with probability at least 1 -1 / poly( n ) .

(Section 2.1). Initially, each vertex of the graph is a cluster; for O (log D T ) iterations, we contract an independent set of edges in the tree to form larger and larger clusters. Each iteration reduces the number of clusters by a constant factor (by a result of [BDE + 19, CC23]); after O (log D T ) rounds, the number of clusters has been reduced by a factor of poly( D T ) . Then, we have enough global memory per cluster to execute our more naive approach, after which we can (if necessary) 'un-contract' the clusters and obtain a result for the original graph.

This approach comes with some challenges, however. In particular, we have to be very careful when performing cluster contraction to preserve enough information to solve the problem. For example, for MST verification, for each cluster c , we must preserve the highest weight of an edge on all paths from vertices below c to vertices above it. For MST sensitivity (Section 4) and all-edges LCA (Section 2.2) it is significantly more challenging to preserve the necessary information. We note that our hierarchical clustering is different from a recent clustering employed by [GLM + 23] in a paper on dynamic programming in trees (in particular, our clusters are all of height 2 , relative to previous clusters). We believe that our approach, using clusters to 'compress' an input tree to allow for greater space-flexibility, could have further applications for efficient algorithms involving trees in low-space MPC .

## 1.3 Related Work

The MST problem is a fundamental textbook graph optimization problem that has been extensively studied for many decades (see [GH85] for the historical background of the research before 1985). We know the problem can be solved sequentially by a randomized algorithm in O m ( ) -time [KKT95], but its deterministic complexity still has some small gap (see though [PR02]), with the fastest algorithm to date [Cha00] achieves the running time of mα m,n ( ) , where α is a certain natural inverse of Ackermann's function. This research has been extended to the PRAM model, where, e.g., Cole et al. [CKT96] gave an optimal O (log n ) -time randomized algorithm for the MST problem.

For the MST sensitivity problem, the classical algorithm of Tarjan [Tar82] solves it sequentially in O mα m,n ( ( )) time. Dixon et al. [DRT92] designed two MST sensitivity algorithms, one running in expected linear time and another which is deterministic and provably optimal, but whose complexity is bounded by O mα m,n ( ( )) . Pettie [Pet15] improved this bound and designed a new MST sensitivity analysis algorithm running deterministically in O m ( log α m,n ( )) time.

The problem of verifying if a given spanning tree in an edge-weighted graph is an MST is very closely related to the MST problem, but unlike the latter, we understand its sequential and PRAM complexity very well. Following an early work of Komlos [Kom84], Dixon et al. [DRT92] and King [Kin97] developed deterministic sequential linear-time algorithms for the problem. In parallel setting, Dixon and Tarjan [DT97] gave an optimal O (log n ) -time CREW algorithm which was later extended to the EREW PRAM model [KPRS97].

In the last few years, there has been a series of work extending the study of the MST problem to the MPC model. For the setting of 'super-linear' MPC (where each machine has s = O n ( 1+ δ ) local memory), Lattanzi et al. [LMSV11] gave a O (1) round algorithm for MST.

For low-space MPC , which is the focus of this paper, results for MST and related problems have been limited. A long and celebrated line of work on connectivity culminated in a O (log D + log log n ) round deterministic algorithm for the problem [ASS + 18a, BDE + 19, CC23], and there is a (conditional) Ω(log D ) round lower bound [BDE + 19, CC23]. A recent discovery reveals an optimal O (log D ) rounds algorithm when the input graph is a forest [BLM + 23]. For MST, while there is an algorithm which takes O (log D MST ) rounds [ASS + 18a, CC23], it requires polynomially extra ( g = O m ( 1+ γ ) for any positive constant γ ) global memory, and hence it does not achieve the optimal utilization. It recursively partitions the input instance into O m ( γ/ 2 ) sub-instances of MST, each of which also has (proportionally) polynomial extra global memory. At each level of the recursion, computing the connected components of each sub-instance is required: with

For the setting of linear MPC , where each machine has s = O n ( ) memory, a line of work culminated also in O (1) round algorithms for the problem, first randomized [JN18] and then deterministic [Now21]. Once again, these algorithms relied heavily on the use of connectivity as a subroutine, and these papers also gave randomized and deterministic connectivity algorithms.

extra global memory, this takes O (log D MST ) rounds. Since the algorithm uses O (1) levels of recursion and each level requires a series of connectivity algorithms with extra global memory to be run in parallel (taking O (log D MST ) rounds), the algorithm takes O (log D MST ) rounds in total. The algorithm can be implemented to work with optimal global memory, but then the number of rounds degrades to Ω(log n ) , since the recursion can branch by at most a constant factor. For global space g = O m ( 1+ γ ) for γ = o (1) and γ = Ω( 1 log n ) , one can find MST in O ( 1 γ min log { D MST log( 1 γ ) , log n } ) rounds on an MPC with local memory s = O n ( δ ) (see [ASS + 18a, Theorem I.7]). In particular, if one wants to focus on the regime with global memory at most ( n + m ) polylog( n ) (i.e., γ = O ( log log n log n ) ), then the number of rounds is log n · min log { D MST , log n log log n } . Observe that except when the global memory is large, we do not know of any MPC algorithm (with sublinear local memory) that solves MST exactly in o (log n ) rounds, even for graphs with small diameter. The approaches used in [ASS + 18a] and other related works [ASZ19, BLM + 23, BDE 19, CC23] that lead to + O (log D + log log n ) -rounds MPC connectivity algorithms seem unsuitable to obtain even O (log n ) -rounds algorithms for MST. (Still, notice that an optimal O (log n ) -rounds MPC algorithm can be obtained by simulating PRAM algorithms, e.g., from [CKT96].)

For low-diameter graphs the gap between O (log D MST ) and O (log n ) is potentially huge, and it is not clear how to even obtain (say) an O D ( MST ) round algorithm for the problem. Whether the Ω(log n ) round barrier can be broken with optimal global memory is a major open question in the area.

Similarly to the connectivity conditional lower bound of Ω(log D ) , there is also a conditional Ω(log D MST ) round lower bound for finding an MST [CC23], which, for the sake of completeness, we sketch in Appendix A.

## 2 Preliminaries and Tools

In this section, we present some notation and preliminaries, along with two important technical tools: a hierarchical clustering approach, which transforms a tree T into a set of n poly D T clusters; as well as a procedure for finding the lowest common ancestor in the tree of the endpoints of each non-tree edge.

We introduce a notion of a non-tree edge covering a tree edge:

In a rooted tree, let p v ( ) denote the parent of v ; for the root of the tree r , p r ( ) = r . Further, let p i ( v ) denote the i th ancestor of v , i.e. p 1 ( v ) = p v ( ) and p i ( v ) = p p ( i -1 ( v )) .

Definition 2.1. We say that a non-tree edge e covers a tree edge t if t is one of the edges on the path in T between the endpoints of e .

Observe that the problem of MST verification is the same as asking: is any tree edge t covered by an edge e with lower weight?

We remark that, without loss of generality, we can assume that our input tree T is a rooted spanning tree:

Remark 2.2. Our MST verification and MST sensitivity algorithms can assume that T is a rooted spanning tree of G .

Proof. We can check whether the given tree T is a spanning tree or not by just counting whether the number of vertices in T is n . We can identify the root of the tree in O (log D T ) rounds (deterministically, and using optimal global memory) by using tree rooting algorithm of [BLM + 23].

Furthermore, in the following, we remark that both algorithms can assume knowledge of D T , the diameter of tree T .

Remark 2.3. Our MST verification and MST sensitivity algorithms can assume the value of D T .

Proof. Recall the connectivity algorithm on forest by [BLM + 23]. The algorithm takes O (log D ) rounds, where D is the diameter of the forest (i.e, the diameter of any component of the forest). Moreover, the algorithm can determine a value ̂ D such that D ≤ ̂ D ≤ 2 D . So, by applying the algorithm of [BLM + 23] on input T , we get a 2-approximation to D T (which is good enough for our MST verification algorithm and MST sensitivity algorithm).

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00398v1-figure-7f061e81-9e44-47c0-a965-2f635c45d407.jpg)

(a) An input tree T . Each vertex is its own cluster.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00398v1-figure-77a9bb2d-fb73-4f68-a8d9-b317eaafe681.jpg)

(b) T after one cluster contraction step, giving a set of clusters C 1 . Orange polygons denote the (level1 ) clusters that formed.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00398v1-figure-c4339dcd-044a-40b0-9edb-34ebe713547f.jpg)

(c) The cluster-tree after one contraction step, which we denote as T C 1 .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00398v1-figure-81695925-769c-46e0-b906-eed2bed248c4.jpg)

(d) A second cluster contraction step, forming some level2 clusters. There are four clusters after this step.

Figure 1: A depiction of our hierarchical clustering.

Finally, we remark that all of our algorithms given here can be extended to forests:

Remark 2.4. Our MST verification and MST sensitivity algorithms can be easily extended to the case where G is disconnected and the input tree T is a forest.

Proof. First, we solve connectivity on forest T by using the algorithm in [BLM + 23]. The algorithm takes O (log D T ) rounds. Then, we can partition the edges of G by connected component (all vertices know their connected component since they know which tree in T they are in). Then, since they are independent, it suffices to run in parallel our MST verification or sensitivity algorithm for each component.

## 2.1 Clusters

We now introduce our notion of clusters , which we use to 'compress' our input tree T so that we can run algorithms that require extra global memory per vertex. We give a depiction of our clustering approach in Section 2.1, and they are formally defined as follows:

Definition 2.5 (Clusters) . A cluster is a set of vertices whose induced subgraph in T is connected. The leader of a cluster is the root of the subtree induced by the vertices in it. By ℓ v ( ) we denote the leader of the cluster containing v (and so ℓ u ( ) = ℓ v ( ) iff u and v are in the same cluster).

We denote the set of clusters at some point in time as C . Initially, each vertex forms a singleton cluster: i.e., ℓ v ( ) = v . We maintain as an invariant that the union of the clusters at any time is V ; i.e., the vertices are partitioned into clusters.

Two clusters c 1 and c 2 are connected if some u ∈ c 1 and v ∈ c 2 are connected by an edge in T . Note that there can be at most one such edge, for each pair of clusters.

If T is rooted, the graph on clusters forms a rooted cluster-tree T C , with ancestor/descendant relationships being defined based on the cluster leaders.

We say that a vertex v is a leaf of a cluster c if it is either a leaf of T , or the parent in T of a root of a different cluster.

Next, we introduce cluster contraction , the process by which clusters are created.

Definition 2.6 (Cluster Contraction, Sub-Clusters) . Let c ∈ C be a cluster and let c 1 . . . c k be some nonempty subset of its child clusters in T C .

When we contract c , we make a new cluster c ′ comprised of all vertices in c, c 1 , . . . c k . The leader of c ′ will be the leader of c . We call c, c 1 . . . , c k the sub-clusters of c ′ : in particular we call c the senior sub-cluster and c 1 . . . c k the junior sub-clusters .

Definition 2.7 (Contraction Step) . During our algorithm, we will perform the process described in Definition 2.6 in parallel for a subset of clusters, ensuring that for all c 1 , c 2 , c 3 ∈ C , we do not simultaneously contract both c 1 into c 2 and c 2 into c 3 .

This parallel contraction of a subset of clusters is called a contraction step .

We recall that, as an immediate consequence of [CC23] (derandomizing a result of [BDE + 19]), given a rooted tree, we can contract a set of edges in O (1) rounds to reduce the number of vertices by a constant fraction:

Lemma 2.8 ([CC23, Theorem 3.3]) . Given a rooted tree T with n vertices, there is a deterministic, O (1) -round MPC algorithm which contracts a set of edges, reducing the number of vertices in T to 0 99 . n . The algorithm uses s = O n ( δ ) local memory (for some constant δ ), and g = O m ( + n ) global memory.

We note that given a cluster-tree, Lemma 2.8 performs a contraction step as in Definition 2.7.

Next, we formalize the notion of a hierarchical clustering, a series of contraction steps which we perform in our LCA , MST verification, and MST sensitivity algorithms.

Definition 2.9 (Hierarchical Clustering) . When we perform k contraction steps according to Lemma 2.8, we call clusters formed during the i -th ( i ∈ [ k ]) step leveli clusters .

We denote the set of all clusters present after contraction step i as C i (note that not all of these clusters will necessarily be leveli clusters). The singleton clusters at the beginning of the algorithm are all level0 clusters.

We denote the cluster in C i which contains v as c i ( v ) ; the leader of this cluster is denoted as ℓ i ( v ) .

Finally, we observe that there are a linear number of clusters in total, and the total size of all cluster-trees is linear.

Observation 2.10 (Size of Hierarchical Clustering) . In a hierarchical clustering of the graph as in Definition 2.9, there are at most O n ( ) clusters, across all levels.

Additionally, if each contraction step reduces the number of vertices by a constant fraction (as Lemma 2.8 does), then the total size of the cluster-trees across all contraction steps is O n ( ) .

## 2.2 All-edges LCA and Ancestor-Descendant Graphs

Both of our problems take an input graph G as well as a tree T . We can assume that G is connected.

We will find it useful for our verification and sensitivity algorithms to work with ancestor-descendant graphs : that is, input instances for which all edges in E \ T are between ancestors and descendants in T . Formally, we define them as follows:

Definition 2.11 (Ancestor-Descendant Graphs) . Let G = ( V, E ) be a graph and let T ⊆ E be a rooted spanning tree of G G . is said to be an ancestor-descendant graph with respect to T if all edges in E \ T are between vertices with an ancestor-descendant relationship in T .

In order to transform our input into an ancestor-descendant graph, we split each non-tree edge { u, v } into two edges { u, LCA ( u, v ) } and { v, LCA ( u, v ) } with the same weights, where LCA ( u, v ) is the lowest common ancestor of u and v in T . We are not able to compute the LCA of every pair of vertices, since this requires Θ( n 2 ) global memory. Instead, we compute the LCA for each pair of endpoints of an edge in E \ T , which requires Θ( m ) memory. This computation is the subject of the rest of this section.

First, we remark that we can compute the DFS numbering of a rooted tree using a result of Andoni, Stein, and Zhong:

Theorem 2.12 ([ASZ19, Theorem 3] and [ASS + 18b, Theorem D.22]) . Given a rooted tree T with diameter D , there is an O (log D ) -round MPC algorithm which finds the DFS sequence of T . The algorithm uses s = O n ( δ ) local memory (for some constant δ ), and g = O n ( ) global memory. It succeeds with high probability.

We extend the DFS sequence to a DFS interval labeling, which we define as follows:

Definition 2.13. A DFS interval labeling of a rooted tree T is, for each vertex v ∈ T , an interval I ( v ) = [ v low , v high ] , where v low is the smallest DFS number in the subtree of T rooted at v , and v high is the largest DFS number in the subtree of T rooted at v .

Observe that iff u is an ancestor of v in T , then u low ≤ v low ≤ v high ≤ u high . In other words, I ( v ) ⊂ I ( u ) . If u and v are not in an ancestor-descendant relation in T , then I ( u ) ∩ I ( v ) = ∅ .

We observe that this interval labeling can be computed using recently developed dynamic programming techniques for the MPC model:

Lemma 2.14. Given a rooted tree T with diameter D T , there is an O (log D T ) -round MPC algorithm which produces a DFS interval labeling of T . The algorithm uses s = O n ( δ ) local memory (for some constant δ ), and g = O m ( + n ) global memory. It succeeds with high probability.

Proof. Theorem 2.12 can be applied to produce a DFS sequence of T in O (log D T ) rounds with global memory O m ( + n ) and succeeds with high probability. By definition, v low is the DFS number of v , so it remains for each vertex v to learn v high .

This is easily done as a consequence of arguments in [GLM + 23]: the authors mention computing the maximum of input labels in each subtree as a computation which their approach allows. Their computation requires O (log D T ) rounds, deterministically; overall our algorithm succeeds with high probability (since the DFS numbering succeeds only with high probability).

The goal of the remainder of this section is to prove the following claim:

Theorem 2.15. Given a graph G , and a rooted tree T with diameter D T , there is an O (log D T ) -round MPC algorithm to compute, for each edge { u, v } ∈ E \ T in parallel, LCA ( u, v ) .

The algorithm uses s = O n ( δ ) local memory (for some constant δ ), and g = O m ( + n ) global memory. It succeeds with high probability.

It seems that the above theorem follows from [ASZ19, Section 4.3]. However, we give the proof explicitly here to provide context for the following sections. Though our proof of Theorem 2.15 and the proof of [ASZ19] are fundamentally similar, the details are different.

Algorithm 1 FindLCAClusters ( C ) : Finds, for each edge in E \ T , the cluster containing the LCA of their endpoints.

̸

```
                                                                                                                                                                                                       
                                                                                                                                                                                                       

                                                                                                                                                                                                        }
                                                                                                                                                                                                      

                                                                                                                                                                                                       }

                                                                                                                                                                                                      
	                                                                                                                                                                                                       	                                                                                                                                                                                                      
---------------------------------------------------------------------------------------------------------------------                                                                                                                                                                                                        \
                                                                                                                                                                                                       \

                                                                                                                                                                                                       \
```

## Algorithm 2 UndoClustering ( C, LCA C )

```
Algorithm 2 UndoClustering(C, LCA_{C})
                                                                                                                                                                                                        
  1:  for i in E ( O ( \log D _ { T } ) \dots 2, 1 ) do
  2:        for each level-i cluster c in C in parallel do
  3:             let c _ { 1 } \dots c _ { k } \, be the junior sub-clusters of c; let c _ { p } \, be the senior sub-cluster of c
  4:             for each edge \{ u, v \} in E \, \tilde { T } \, in parallel with LCA _ { C } ( u, v ) = c do
  5:                      if there is a c _ { i } \, such that D ( u ) \, \in I ( \ell ( c _ { i } ) ) \, and \, D ( v ) \, \in I ( \ell ( c _ { i } ) ) \, then LCA _ { C } ( u, v ) \, \leftarrow c _ { i }
  6:                       else LCA _ { C } ( u, v ) \, \leftarrow c _ { p }
  7:              end for
  8:              remove c \, from C \, and \, \text{ad} \, \dots c _ { k } \, \text{ad} \, c _ { p } \, to \, C
  9:        end for
  10:   end for
  11:   for each edge \{ u, v \} \, \in E \, \tilde { T } \, \text{ do LCA ( u, v ) \, \leftarrow \ell ( LCA _ { C } ( u, v ) ) }
  12:   return LCA
```

We start by showing that we can create, for each vertex u in a tree in parallel, edges to the parent of u , the 2 -parent of u , the 4 -parent of u , and so on (as in lines 3-5 of Algorithm 3):

Lemma 2.16. Let T be a tree with n vertices and diameter D T . In O (log D T ) rounds, we can create edges from each vertex v to p 1 ( v , p ) 2 ( v , p ) 4 ( v , p ) 8 ( v ) . . . p n ( v ) . This requires g = O n ( · log D T ) global memory.

Proof. Each vertex v starts with a single edge ( v, p ( v )) . Machines start by appending a 1 to these tuples (our example becomes ( v, p ( v , ) 1) ), and creating a copy of the edge with the direction reversed and with a -1 appended (in our example, ( p v , v, ( ) -1) .

The tuples ending with -1 can then be set aside and the process can be repeated for the edges at distance 2 . This process can be repeated O (log D T ) times (each iteration using edges of distance i to create edges of distance 2 i ), and clearly this creates edges from v to p 1 ( v ) , p 2 ( v ) , p 4 ( v ) , and so on; and requires O (log D T ) rounds and global memory per vertex.

Then all edges are sorted lexicographically across machines in O (1) rounds; this leaves, for each vertex v , the parent and children of v on consecutive machines. Machines can now locally create edges between the parent of v and the children of v , and append 2 to the resulting tuple.

Next, we argue the correctness and implementation of Algorithm 1: the algorithm which finds, for each non-tree edge, the cluster in which the LCA of their endpoints is contained.

Lemma 2.17. Algorithm 1 can be implemented in O (log D T ) rounds of sublinear MPC with O m ( + ) n global memory. After its execution, the cluster containing the LCA in T C of c u ( ) and c v ( ) for each non-tree edge { u, v } ∈ E \ T is correctly computed.

## Algorithm 3 LCA ( V, E, T ) : Computes the LCA in T for all edges in E \ T in parallel.

- 1: Apply Lemma 2.14 to find a DFS interval labeling of T . For each v ∈ V , let I ( v ) be the interval corresponding to v .
- 2: Find a hierarchical clustering using Definition 2.9; let C be the resulting set of clusters.
- 3: for i ∈ (1 , 2 4 8 , , , . . . , D T ) do ▷ Create 'auxiliary' edges between each cluster in C and their parent in T C , 2 -parent in T C , 4 -parent in T C , and so on
- 4: for each cluster c ∈ C in parallel do for each cluster c ′ with p i ( c ′ ) = c , set p 2 i ( c ′ ) ← p i ( c )
- 5: end for
- 6: LCA C ← FindLCAClusters ( C ) ▷ We find the highest i such that I ( p i ( v )) ∩ I ( p i ( u )) = ∅ . This corresponds to the cluster which contains the LCA of u and v
- 7: LCA ← UndoClustering ( C, LCA C ) ▷ We reverse the contraction process and, for each edge in the original graph, we find the vertex which is the LCA of its endpoints

Proof. Consider some non-tree edge { u, v } ∈ E \ T .

It suffices to find the smallest i such that the i -th ancestor of (w.l.o.g.) c u ( ) is also an ancestor of v : we argue that lines 4-8 accomplish this. The approach taken in the for-loop in lines 5-7 moves the candidate χ for the LCA up as much as possible such that χ is not an ancestor of c v ( ) : therefore at the end of the for-loop, the parent of χ is the LCA in T C of c u ( ) and c v ( ) .

First, note that line 2 ensure that if c u ( ) and c v ( ) have an ancestor-descendant relationship in T C , then whichever is the ancestor is selected as LCA ( u, v ) . Therefore, assume that this is not the case.

It remains to show that Algorithm 1 can be implemented in MPC with the specified memory and round requirements. First, note that as a precondition to this algorithm auxiliary edges from each cluster to their parent in T C , 2 -parent in T C , 4 -parent in T C , etc. were established. Suppose (w.l.o.g) the information about the i -parent of c u ( ) is stored as an ( u, i, p i ( u )) triple. We store the relevant information about each non-tree edge as ( χ, c ( v , I ) ( χ , I ) ( c v ( )) tuples. In each iteration of the for-loop we sort the i -parent triples along with the candidate tuples, so that the first element of each are stored on consecutive machines. We use prefix sum to ensure that a copy of each i -parent triple of u is on each machine which has tuples where χ = ( ) c u . With these conditions, machines can perform the necessary computations on line 6 locally. The computation takes O (log D T ) rounds, and the total memory is linear.

Next, we argue the correctness and implementation of Algorithm 2: the algorithm which undoes the contraction steps and finds the LCA s for all non-tree edges.

Lemma 2.18. Algorithm 2 can be implemented in O (log D T ) rounds of sublinear MPC with O m ( + ) n global memory. After its execution, the LCA of the endpoints of each non-tree edge { u, v } ∈ E \ T is correctly computed.

Proof. First, we argue that for each non-tree edge { u, v } ∈ E \ T , LCA C ( u, v ) -the LCA of c u ( ) and c v ( ) in T C , computed in Algorithm 1-contains the LCA of u and v in T , i.e, that c ( LCA ( u, v )) = LCA C ( u, v ) .

We now show that Algorithm 2 finds LCA ( u, v ) . Each of cluster contraction steps is undone in reverse order: a cluster c produces its senior sub-cluster ( c p ), and the junior sub-clusters c 1 . . . c k . In each iteration, for each non-tree edge { u, v } ∈ E \ T , we check (line 5) whether any of the roots of the junior sub-clusters are a common ancestor of u and v . If this is the case for some child cluster c i then by arguments as above c i must contain LCA ( u, v ) , and so we set the candidate LCA of u and v ( LCA C ( u, v ) ) to c i (line 5). If this is not the case, then by elimination LCA ( u, v ) must be in the senior sub-cluster, and so we set LCA C ( u, v )

Note that for any vertex u , ℓ u ( ) (the root of the cluster containing u ) is an ancestor of u in T . If ℓ u ( ) is an ancestor of LCA ( u, v ) then c ( LCA ( u, v )) = c u ( ) and line 2 of Algorithm 1 would return LCA C ( u, v ) = c ( LCA ( u, v )) as required. Suppose otherwise that ℓ u ( ) and ℓ v ( ) are both descendants of LCA ( u, v ) . Recall that Algorithm 1 correctly computes the LCA in T C of c u ( ) and c v ( ) (Lemma 2.17). Therefore there is no c ′ which is an ancestor of c u ( ) and c v ( ) as well as a descendant of LCA C ( u, v ) , and it follows that c ( LCA ( u, v )) = LCA C ( u, v ) .

to c p . One can see that this finds a vertex which is an ancestor of both u and v and that it finds the lowest such vertex (since the child clusters are checked first). After all of the cluster contraction steps have been undone, C = V . Then, there is only one possible value for LCA ( u, v ) , and lines 11 set this value.

Finally, each iteration of the for-loop in lines 1-10 can be implemented using a constant number of sorts and prefix-sums (sorting the interval labels of the roots of the junior sub-clusters along with the non-tree edge endpoints, and using prefix-sum to determine to which junior sub-cluster u and v belong), and therefore Algorithm 2 takes O (log D T ) rounds. It is easy to see that the global memory used is linear.

Finally, we show the main result of this section:

Proof of Theorem 2.15. Correctness, and the implementation of lines 8 and 9 follows immediately from Lemmas 2.17 and 2.18. Implementation of lines 3-5 follows from Lemma 2.16.

By simple applications of sorting and prefix sum (and with only a constant factor increase in global memory), we can use Theorem 2.15 to turn our input graph into an ancestor-descendant graph:

Corollary 2.19. Given a graph G , and a rooted tree T with diameter D T , there is an O (log D T ) -round MPC algorithm which replaces each non-tree edge { u, v } ∈ E \ T with two edges { u, LCA ( u, v ) } and { v, LCA ( u, v ) } . The algorithm uses s = O n ( δ ) local memory (for some constant δ ), and g = O m ( + n ) global memory. It succeeds with high probability.

Finally, we observe that the transformation of the input given by Corollary 2.19 does not affect the computation of verification or sensitivity:

Observation 2.20 ([Pet05, DRT92]) . Let G = ( V, E ) be an edge-weighted graph, and let T ⊆ E be a candidate MST.

Replacing each non-tree edge { u, v } ∈ E \ T with edges { u, LCA ( u, v ) } and { v, LCA ( u, v ) } (of the same weight) does not affect the result of MST verification, or the sensitivity of tree edges. After the replacements, the sensitivity of non-tree edges is equal to the minimum sensitivity of the two replacements.

## 3 MST Verification

In this section we present our algorithm for MST verification, and prove Theorem 3.1.

Theorem 3.1 ( MST Verification Algorithm . ) Let δ be an arbitrarily small positive constant. Let G = ( V, E ) be an edge-weighted input graph and let T ⊆ E be a tree. Suppose the diameter of T be D T . Then one can decide with high probability whether T is an MST of G in O (log D T ) rounds on an MPC with local memory s = O n ( δ ) and optimal global memory g = O m ( + n ) .

We recall that, due to Remark 2.2, T can be assumed to be a rooted spanning tree of G , because we can verify this in O (log D T ) rounds. From Remark 2.3, we can assume that the algorithm knows the value of D T . Also, recalling Remark 2.4, our MST verification algorithm, while stated for trees, can easily be extended to forests. We may also assume that G is an ancestor-descendant graph with respect to T (Definition 2.11). If this is not the case then we can use Corollary 2.19 to transform our input into an ancestor-descendant graph, with asymptotically the same number of edges. By Observation 2.20, this transformation does not affect the output of the MST verification problem.

A naive algorithm for the MST verification problem might be to collect, for each vertex u , the path from u to the root of T . Using prefix-sum in O (1) rounds, we can then compute, for each vertex u ′ on the path from u to T , the highest-weight edge on the path from u to u ′ . Then, for each non-tree edge e = { u, v } in parallel (where v is an ancestor of u in T ), we can use sorting and prefix-sum and the previously computed prefix-sum of the path from u to the root to compute the highest weight of an edge on the path from u to v . Suppose this weight is x e : if x e &lt; w e ( ) (and this is true for all non-tree edges), then T is a minimum spanning tree; otherwise it is not.

There is a problem with this algorithm, which is that to collect the path to the root for all vertices might require Ω( n · D T ) global memory, which might be ω m ( + n ) . If we were able to somehow reduce the number of vertices in the graph to n D T , then this approach would work.

Initially, we have a set of n clusters where each cluster is a singleton vertex and over rounds these clusters are contracted. We need to preserve enough information about the weights of edges in the clusters to check whether any edge in E \ T ought to be in a minimum spanning tree. To do this, we define the notion of a weight preserving labeling to keep track of two labels throughout the cluster contraction process (as formally defined in Definition 3.2). We apply the contraction process on T for O (log D T ) rounds until we have a tree of O n/D ( T ) clusters. Then, we can find the path from every cluster to the root cluster using O n ( ) global space (Lemma 3.7). Finally, we argue that this path information along with the weight preserving labeling of clusters that we have maintained, is enough information to decide whether T is an MST.

The challenge is therefore to preserve the information required to evaluate for each non-tree edge { u, v } , the highest weight of an edge from u to LCA ( u, v ) , while reducing the number of vertices by a factor of D . The (effective) number of vertices/clusters reduces by a constant factor in each round by applying contraction. If we forget about the weights of the tree edges between contracted vertices, we may lose relevant information.

## 3.1 Weight-Preserving Labeling

In this subsection we introduce the notion of a weight-preserving labeling . As already discussed, the intuition is that we need to reduce the number of vertices by a factor of Ω( D T ) so that subsequent steps of the algorithm have Ω( D T ) global memory per vertex to work with. We do this using cluster contraction steps as outlined in Definition 2.6.

Definition 3.2 (Weight-Preserving Labeling) . Let G = ( V, E ) be a graph with an edge-weighting function w : E → [ W ] , T ⊂ E be a candidate MST, and C be a partition of V into a set of clusters. Assume that G is an ancestor-descendant graph with respect to T . A weight-preserving labeling of ( G,w,T,C ) is a pair ( θ, ω ) such that:

- · for each edge { c , c c p } ∈ T C (where c p is the parent of c c in T ), a label θ c , c ( c p ) which takes a value in [ W ] ; and
- · for each edge { u, v } ∈ E \ T , labels ω u, v ( ) and ω v, u ( ) which take values in [ W ] ∪ {-∞} .

These labels represent the following:

- · For each edge { c p , c c } ∈ T C , let c p be the parent cluster and let c c be the child cluster. θ c ( p , c c ) is the highest weight of an edge on the path from ℓ c ( p ) to p ℓ c ( ( c )) in T .
- · For each edge { u, v } ∈ E \ T , let P be the path from u to v in T . ω u, v ( ) is the highest weight edge on P where both endpoints are in c u ( ) ; ω v, u ( ) is defined analogously.

If there are no such edges, then ω u, v ( ) = -∞ . Clearly, if v ∈ c u ( ) , then ω u, v ( ) = ω v, u ( ) .

These labels, along with the weights of some edges which we do not contract, sufficiently capture all information necessary to evaluate the highest weight of an edge in T which some edge { u, v } ∈ E \ T covers:

Observation 3.3. Consider a graph G = ( V, E ) with a weighting function w , a rooted candidate MST T , and a set of clusters C . Suppose that G is an ancestor-descendant graph with respect to T , and let ( θ, ω ) be a weight-preserving labeling of ( G,w,T,C ) .

For any edge { u, v } ∈ E \ T , let u be an ancestor of v and let P C = ( ( c v ) . . . c ( u )) be the path of clusters in T C which the path from u to v in T passes through. Then, the highest weight of an edge on the path from u to v in T is:

̸

$$\max \left \{ \omega ( u, v ), \omega ( v, u ), \max _ { ( c _ { c }, c _ { p } ) \in P _ { C } | c _ { p } \neq c ( u ) } \left \{ \theta ( c _ { p }, c _ { c } ) \right \}, \max _ { ( c _ { c }, c _ { p } ) \in P _ { C } } \left \{ \ w \left ( \left \{ \ell ( c _ { c } ), p ( \ell ( c _ { c } ) ) \right \} \right ) \ \right \} \right \}$$

We now argue that when we perform cluster contraction steps, we are able to efficiently maintain a weight-preserving labeling of the current clustering:

Lemma 3.4. Consider a graph G = ( V, E ) with a weighting function w , a rooted tree T , and a set of clusters C . Suppose that G is an ancestor-descendant graph with respect to T , and let ( θ, ω ) be a weight-preserving labeling of ( G,w,T,C ) .

After a cluster contraction step is performed, returning a new set of clusters C ′ , we can compute a new weight-preserving labeling ( θ , ω ′ ′ ) of ( G,w,T,C ′ ) using only θ , ω , and the weights of edges between vertices in different clusters in C .

Proof. First, note that if some cluster c ∈ C is also a cluster in C ′ (i.e., c is not involved in a contraction), then for all vertices u ∈ c and all non-tree edges { u, v } , ω u, v ( ) = ω ′ ( u, v ) . Also, for each child c i of c in C , θ c , c ( i ) = θ ′ ( c ∗ i , c ) , where c ∗ i is the cluster which the vertices in c i are part of in C ′ .

Let c ′ i be a child cluster of c ′ in T C ′ . We handle each type of label separately and show that they can be properly computed:

So we focus on clusters which have undergone a contraction step. Consider a cluster c ∈ C : suppose it has children c 1 . . . c k in T C , and that it forms cluster c ′ ∈ C ′ when contracted.

- · We show that we can compute θ ′ ( c , c ′ i ′ ) . Recall that θ ′ ( c , c ′ i ′ ) is the highest-weight edge on a path in T from the leader of c ′ to the parent of the leader of c ′ i .
- Since c ′ i is a child of c ′ in T C ′ , it must have been a child of some c i in T C . The path from the leader of c (also the leader of c ′ ) to the leader of c ′ i must pass through c i , and it suffices to take θ ′ ( c , c ′ i ′ ) = max( θ c , c ( ′ i i ) , w ( { ℓ c ( i ) , p ( ℓ c ( i )) } ) θ c , c ( i )) .
- · We show that we can compute ω ′ ( u, v ) . Let { u, v } ∈ E \ T and suppose u ∈ c ′ . Let P be the path from u to v in T . Recall that ω ′ ( u, v ) is the maximum-weight edge on P where both endpoints are in the cluster in C ′ containing u .

Let c i be an arbitrary child of c in T C . There are 5 sub-cases here based on the positions of u and v w.r.t. clusters that we are contracting:

- 1. v ∈ c ′ : In this case, either u and v were in the same cluster in C (in which case ω u, v ( ) = ω ′ ( u, v ) ); or u and v were in different clusters in C . In the latter case note our assumption that all non-tree edges are ancestor-descendant, so suppose w.l.o.g. that u was in c and v was in a child c i of c . Then, since all but one edge had endpoints either both in the cluster containing u or both in the cluster containing v , ω ′ ( u, v ) = max { ω u, v , w ( ) ( ℓ c ( i ) , p ( ℓ c ( i )) , ω ( v, u ) } .
- 2. u ∈ c , and P does not go through any child of c in T C : In this case P must leave c via its leader. This means that the section of the path in the cluster containing u contains the same edges, and so we have ω ′ ( u, v ) = ω u, v ( ) .
- 3. u ∈ c , and P goes through cluster c i in T C . Since c ′ ∈ C ′ contains all vertices in both c and c i , ω ′ ( u, v ) must represent the highest-weight encountered when leaving c , taking the edge between c to c i , and then leaving c i via one of its child clusters (say c ij ) in C . Then ω ′ ( u, v ) = max { ω u, v , w ( ) ( ℓ c ( i ) , p ( ℓ c ( i ))) , θ ( c ij , c i ) } .
- 4. u ∈ c i , and P does not go through c in T C . In this case P must leave c i via one of its children in C . The contraction of c with its children does not affect the edges encountered when leaving c i via one of its children, and so ω ′ ( u, v ) = ω u, v ( ) .
- 5. u ∈ c i , and P goes through c in T C , and exits c via its leader. This case is analogous to case 3: we have ω ′ ( u, v ) = max { ω u, v , w ( ) ( ℓ c ( i ) , ℓ ( p c ( i ))) , θ ( c , c i ) } .

We argue that we are able to implement the above approach in sublinear MPC , using optimal global memory:

Lemma 3.5. Let G be a graph with a set C of clusters and a weight-preserving labeling ( θ, ω ) . There is an MPC algorithm which, in O (1) rounds, outputs a new set of clusters C ′ such that | C ′ | ≤ | C /α | (for some constant α &gt; 1 ), along with a weight-preserving labeling ( θ , ω ′ ′ ) for C ′ . The algorithm uses s = O n ( δ ) and g = O n ( + m ) .

Proof. Observe that the computation of θ ′ ( · , c ) for a cluster c only depends on θ c , c ( i ) and θ ( · , c i ) for all children c i of c ; this computation can be performed locally along with the contractions.

Since there is one θ label for each cluster in C i , and | C i | &lt; n ; and there are two ω labels for each non-tree edge, of which there are m , the algorithm requires O m ( + n ) total memory.

Similarly, the computation of ω ′ ( u, v ) depends on ω u, v ( ) . It also depends on which case of Lemma 3.4 applies, and depending on the case a constant amount of additional information ( θ values and the weight of edges which are being contracted), which can be made locally available using sorting. The applicable case can be computed locally using the interval labeling of the vertices, and the constant amount of additional information for each non-tree edge can be placed on the same machine as the edge and used to compute ω ′ ( u, v ) .

We now argue that we can perform O (log D T ) cluster contraction steps, while keeping track of a weightpreserving labeling, in O (log D T ) rounds of sublinear MPC with optimal global memory.

Corollary 3.6. Applying the algorithm from Lemma 3.5 on the input instance O (log D T ) times gives a graph with a weight-preserving labeling and n poly( D T ) clusters.

## 3.2 The Rest of the Algorithm

We now show that we can use the weight-preserving labeling from the previous section, along with the approach sketched earlier, to solve the problem of MST verification.

First, we argue that we can collect, for each vertex u in a tree, the path from u to the root of the tree, in O (log D T ) rounds with an extra factor of D T global memory:

Lemma 3.7. Let T be a tree with n vertices and diameter D T . In O (log D T ) rounds, we can, in parallel for each vertex v , collect the path from v to the root r of T . This uses g = O n ( · D T ) global memory.

Proof. A similar procedure can be used as in Lemma 2.16, except after each iteration the edges with distance i are not discarded. This still takes O (log D T ) rounds, but now D T global memory per vertex is required, since the entire path to the root is being stored.

Finally, we conclude by proving the main result of the section:

Proof of Theorem 3.1. Westart by computing a clustering using Corollary 3.6, along with a weight-preserving labeling ( θ, ω ) of ( G,w,T,C ) .

For each non-tree edge { u, v } ∈ E \ T , it suffices to collect ω u, v ( ) , ω v, u ( ) , w ( { u, v } ) , one of these maximum θ values, and one of these maximum inter-cluster edge values. Then, it can be determined locally whether { u, v } is of larger weight than all edges on the path from u to v in T . This information can be collected onto a single machine using O (1) rounds of sorting, after which the necessary computation can be performed locally. In total the information required for each non-tree edge { u, v } is of constant size.

Note that the diameter of T C is at most D T . We can execute Lemma 3.7 on T C (taking O (log D T ) rounds and using O C ( | | · D T ) = O n ( ) global memory), and then for each cluster c ∈ C , the path from c to the root of T C is stored on consecutive machines. We can see that, for each cluster c in the path from c u ( ) to r , we can compute the maximum θ value on the path from c u ( ) to c : this can be done with prefix-sum in O (1) rounds. In a similar way, we can compute the maximum inter-cluster edge on the path from c u ( ) to c (for each of the ancestors of u in T C , c ), in O (1) rounds.

Finally, we note that all steps are deterministic, except for the computation of the DFS interval labeling (Lemma 2.14): therefore, the algorithm as a whole succeeds with high probability.

## 4 MST Sensitivity

In this section we present our MST sensitivity algorithm. The conclusion of this section is the following:

Theorem 4.1 ( MST Sensitivity Algorithm . ) Let δ be an arbitrarily small positive constant. Let G = ( V, E ) be an edge-weighted input graph and let T ⊆ E be an MST of G with diameter D T .

The problem of MST sensitivity can be solved in O (log D T ) rounds (with high probability) on an MPC with local memory s = O n ( δ ) and optimal global memory g = O m ( + n ) .

We recall that, given Remark 2.2 we can assume that T is a rooted spanning tree. From Remark 2.3, we can assume that the algorithm knows the value of D T . Given Remark 2.4, while our algorithm is stated for trees it can easily be extended to forests; and that, given Observation 2.20 and Corollary 2.19, we can assume that G is an ancestor-descendant graph (Definition 2.11) with respect to T . We also recall that we can compute a DFS interval label for all vertices in O (log D T ) rounds (Lemma 2.14).

First, we note that our MST verification algorithm works by computing, for each non-tree edge e , the highest weight of an edge which e covers in T . Since this is the information which is relevant for computing the sensitivity of non-tree edges, this almost gives us an MST sensitivity algorithm for non-tree edges immediately. It remains to compute, for each pair of edges { u, LCA ( u, v ) } , { v, LCA ( u, v ) } , which has the lowest sensitivity. This is easily accomplished using sorting and prefix-sum in O (1) rounds, and so we have the following:

Observation 4.2. The MST verification algorithm outlined in Section 3 can be extended to compute the sensitivity of edges in E \ T .

Finally, we observe that the problem of MST sensitivity is (for tree edges) the same computing the minimum weight of a covering edge:

Observation 4.3. To compute the sensitivity of a tree edge e ( sens ( e ) , see Definition 1.2), it suffices to compute the minimum weight of a non-tree edge which covers e (see Definition 2.1). Let mc ( e ) be the minimum weight of a non-tree edge which covers e . Then sens ( e ) = mc ( e ) -w e ( ) .

For ease of notation, we will work with mc rather than sens values in this section. We can set aside a series for machines for keeping track of and updating mc values: this requires an additive O n ( ) global memory (and so does not affect the total asymptotically). These machines can process O n ( ) updates to the mc values of vertices in O (1) rounds, using sorting and prefix sum.

However, this approach is much more complex than it was for the MST verification algorithm. In particular, for verification it sufficed to summarize information about the clusters. For sensitivity we have to be careful to preserve enough information about the clusters so that, when we undo the clustering, we can eventually compute the sensitivity of the edges inside them. Informally speaking, we need to be able to retrieve the information related to clusters from any intermediate step. Since there are O (log D T ) many intermediate steps before obtaining final clusters, O (log D T ) rounds are enough to retrieve the information.

We will use an approach to solve the problem of MST sensitivity which employs a similar method to our MST verification algorithm: reduce the number of vertices by a factor of Ω(poly( D T )) using a hierarchical clustering; use an algorithm which requires an additional Ω(poly( D T )) memory per vertex; and finally use this information to compute the sensitivity values for the original edges of the tree.

In Section 4.1, we discuss our contraction process for MST sensitivity. Note that, at the end of the contraction process (as in Algorithm 5), we have a clustering C , a tree T C of O n/ ( poly( D T )) clusters, and a graph G ′ (obtained by replacing some of the original edges). In Section 4.2, we discuss how to find the sensitivity of the edges between adjacent clusters in C (See in Algorithm 6). This is made possible by the extra poly( D T ) global space we have per cluster. Finally, in Section 4.3, we discuss how we 'unwind' the relevant information w.r.t. intermediate clusters in O (log D T ) rounds to determine the sensitivity of the edges in T which we contracted into clusters during the contraction phase (see Algorithm 7).

Our overall algorithm is as follows:

## Algorithm 4 TreeEdgeSensitivity ( G,T )

- 1: For each edge e ∈ T , set mc ( e ) = ∞ .
- 3: Replace each edge { u, v } ∈ E \ T with edges { u, LCA ( u, v ) } and { v, LCA ( u, v ) } (Corollary 2.19).
- 2: Compute a DFS interval label I for all vertices.
- 4: C , N, E τ ′ ← ClusterContractions ( G,T ) (Algorithm 5)
- 6: UndoContractions ( G,T,N ∪ N , C ′ τ ) (Algorithm 7)
- 5: N ′ ← ClusterSensitivity ( G,E ,T ′ C τ , C τ ) (Algorithm 6)

## 4.1 Contraction into Clusters

To run our sensitivity algorithm in Section 4.2, we need to have poly( D T ) global memory per vertex. To accomplish this, we first perform a hierarchical clustering, producing a set of clusters C . We then run our sensitivity algorithm on T C .

We are going to want to maintain the invariant that, at each step of the hierarchical clustering, if an endpoint of a non-tree edge is in a cluster c , it does not cover any of the edges inside c .

̸

We create what we call a root-to-leaf note : a reminder of the part of the edge which we do not carry forward, to be dealt with later in the algorithm. We formally define this note as follows:

When we perform a contraction, we maintain this invariant by 'cutting off' any ends of a non-tree edge which would violate the invariant. Suppose there is a non-tree edge e = { u, v } , and after a contraction step u is inside a cluster c . Let u ′ be the last vertex on the path from u to v which is also in c . Suppose u = u ′ : in this case the invariant would be violated. We keep the part of the edge which is outside of the cluster ( { u , v ′ } ) and carry it forward to future contraction steps. For the part of the edge inside the newly-formed cluster c , we first observe that (because the invariant was preserved from the previous contraction step) this part forms a path, from the root of one sub-cluster to one of its leaves.

Definition 4.4 (Root-to-Leaf Note) . A root-to-leaf note is a tuple ( r, l, i, w ) , where:

- · r is the root of a cluster c ;
- · l is one of the leaves of c ;
- · i is the index of the contraction step in which the cluster c was formed;
- · w is a weight.

Note that if we simultaneously create multiple root-to-leaf notes where r , l , and i are the same, it suffices to keep only the root-to-leaf note with the minimum w . The intuition behind root-to-leaf notes is that some non-tree edge covers a root-to-leaf path within some (now contracted) cluster. When expanding out the contracted out clusters (see Algorithm 7) we ensure that we take the root-to-leaf notes into account when computing the mc value for all edges which they cover.

The process of performing cluster contraction steps while maintaining the invariant above is depicted in Section 4.1 formally described as follows:

Definition 4.5 (Sensitivity Contraction Process) . Assume that we are at contraction step i . When we contract child clusters c 1 . . . c k into cluster c to form c ′ , for each non-tree edge e = { u, v } there are five possibilities:

- 1. u is in one of the junior sub-clusters, and v is in the senior sub-cluster. Since { u, v } does not cover any edges in clusters by assumption, u must be the root of the junior sub-cluster and v must be one of the leaves of the senior sub-cluster. It suffices to set mc ( { u, v } ) ← min( mc ( { u, v } ) , w ( e )) .
- 2. u is in the senior sub-cluster, and v is an ancestor of u . By the invariant, u must be the root of the senior sub-cluster. In this case the invariant is automatically maintained and no action is necessary.

Figure 2: A depiction of cases 1, 2, 4, and 5 of the sensitivity contraction process (Definition 4.5). (Case 3 omitted for brevity.) The orange clusters c (senior) and c 1 (junior) are being contracted to form the blue cluster c ′ . The dashed edge is the relevant non-tree edge. In cases 4 and 5, we replace the non-tree edge with a root-to-leaf note (the dashed, green line) covering part of the non-tree edge inside c ′ , and shorten the remaining edge (the solid, green line).

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00398v1-figure-375e3dfd-603e-415b-8c87-08b4e05b215c.jpg)

- 3. u is in a junior sub-cluster, and v is a descendant of u . By the invariant, v must be a leaf of a junior sub-cluster. In this case the invariant is automatically maintained and no action is necessary.
- 4. u is in a junior sub-cluster, and v is an ancestor of c ′ . By the invariant, u must be the leader of its junior sub-cluster. In this case we replace e with an edge { ℓ c ( ′ ) , v } (recall: ℓ c ( ′ ) is the leader of c ′ ). Since we have shortened the edge, we create a root-to-leaf note ( ℓ c ( ′ ) , p ( u , i, w ) ( { u, v } )) , where i is the index of the contraction step in which c was formed. We also set mc ( { u, p ( u ) } ) ← min( mc ( { u, p ( u ) } , w ( e )) .
- 5. u is in a senior sub-cluster, and v is an descendant of one of the junior sub-clusters of c ′ , c j . By the invariant, u must be a leaf of its junior sub-cluster. In this case we replace e with an edge { l, v } , where l is the leaf of c ′ on the path from u to v in T . Since we have shortened the edge, we create a root-to-leaf note ( ℓ c ( j ) , l, i, w ( { u, v } )) , where i is the index of the contraction step in which c j was formed. We also set mc ( { ℓ c ( j ) , u } ) ← min( mc ( { ℓ c ( j ) , u } ) , w ( e ) .

We note that if both endpoints require the creation of root-to-leaf notes, then we create both.

We now argue that this only results in O n ( ) root-to-leaf notes being produced, and so our global memory constraints are not violated:

Lemma 4.6. Performing the above operation for all non-tree edges in parallel after each cluster contraction step (Lemma 2.8) results in a total of O n ( ) root-to-leaf notes.

Proof. Follows from Observation 2.10. Fix a cluster c formed in step i . Then:

- · In case 4, the number of distinct root-to-leaf notes created is at most the number of junior sub-clusters of c . The total number of junior sub-clusters is at most the number of vertices in T C i : summing this over all contraction steps gives at most O n ( ) such root-to-leaf notes.
- · In case 5, the number of distinct root-to-leaf notes created is at most the number of leaves of c which have a child which is a cluster leader. Similarly, the total number of these is the number of vertices in T C i : summing over all contraction steps gives at most O n ( ) such root-to-leaf notes.

We now argue that we can actually perform this computation while we do a cluster contraction step:

Lemma 4.7. Algorithm 5 can be implemented deterministically on an MPC with s = O n ( δ ) and g = O n ( + m ) in O (log D T ) rounds.

Proof. It suffices to show that one iteration of Algorithm 5 can be implemented in O (1) rounds within the specified memory constraints. The edges which are to be contracted in each iteration can be identified in O (1) rounds (by Lemma 2.8). It remains to show that we can identify for each non-tree edge e ∈ E ′ whether case 1, 4, or 5 of Definition 4.5 applies.

Fix some non-tree edge e ∈ E ′ , and suppose that e = { u, v } , and that u is an ancestor of v .

- · It is easily checked whether case 1 of Definition 4.5 applies to e , since this is the case if and only if e is the same as one of the edges which are being contracted.
- · For case 4, we need to check whether some edge { u, u ′ } is being contracted, where I ( u ) ⊂ I ( u ′ ) . If this is the case then case 4 applies. We need to set mc ( { u, u ′ } ) = min { mc ( { u, u ′ } ) , w e ( ) } ; create a root-to-leaf note ( ℓ u ( ′ ) , u, i, w ) ; and truncate e so that it goes between ℓ u ( ′ ) and v .
- This can be accomplished by sorting the edges in E ′ along with the edges to be contracted, and using prefix-sum to communicate the edge { u, u ′ } to all edges in E ′ with u as an endpoint (if any). Then, machines can perform the necessary changes to the graph locally (sending the mc update to the machines dedicated to storing and updating those values).
- · For case 5, we need to check whether some edge { v, v ′ } with I ( v ) ⊃ I ( v ′ ) is being contracted. If so, then case 5 applies.

There is one added complication here: we need to find the correct leaf for the root-to-leaf note (that is, the leaf of the cluster containing v ′ through which the u -v path in T passes). Since for any cluster c we know what its children in T C are, we know what the leaves of c are (they are the parents of the roots of the children of c in T C ; they cannot be leaves of T since the u -v path could not pass through them). So by sorting the DFS interval labels of the leaves of the cluster along with the edges in E ′ (and using prefix-sum), we can find this leaf: let us call it l .

We need to set mc ( { v, v ′ } ) = min { mc ( { v, v ′ } ) , w ( e ) } ; create a root-to-leaf note ( ℓ v , l, i, w ( ) ) ; and truncate e so that it goes between l and u .

Since all cases can be identified and the correct action taken within O (1) rounds and linear global memory (using constantly many applications of sorting and prefix sum), the lemma result follows.

Finally, we present the algorithm for this first step as a whole:

## Algorithm 5 ClusterContractions ( G,T ) : Performs O (log D T ) cluster contraction steps

- 1: Let C 0 ← V ; E ′ ← E \ T
- 2: for i ∈ (1 , 2 , . . . , τ = O (log D T )) do
- 4: C i ← The set of clusters after this iteration.
- 3: Perform an iteration of Definition 4.5 on T C i -1 , using Lemma 2.8 to choose the edges to contract.
- 5: N i ← The root-to-leaf notes created during this iteration.
- 6: E ′ ← The truncated non-tree edges (from E \ T )
- 7: end for
- 8: return C τ : The clusters after τ = O (log D T ) cluster contraction steps
- 10: return E ′ : The truncated non-tree edges (from E \ T )
- 9: return N = N 1 ∪ N 2 ∪ · · · ∪ N τ : The root-to-leaf notes created by the cluster contraction steps

## 4.2 MST Sensitivity with n/ poly( D ) Vertices

After executing Algorithm 5, we have a clustering of the vertices in V into a set of n/ poly( D ) clusters C τ . We note that the diameter of T C τ is at most D T : for simplicity here we will assume that it is D T .

In this section, we denote the depth of a cluster v in T C by dep ( v ) : it is defined as the distance of v from the root cluster r .

We will now present an algorithm for MST sensitivity, which works in O (log D T ) rounds but with poly( D ) space per node. We will run this algorithm on the cluster tree T C τ , and use the result to compute the sensitivity of edges in T . Our algorithm works in a similar way to the algorithm of Pettie [Pet15] in the centralized setting.

We first define a useful array for our algorithm:

Definition 4.8. For each non-root cluster c ∈ C τ , A c is an array of length D T such that for each i ∈ [ D T ]

$$A _ { c } [ i ] = \begin{cases} \min _ { \{ \{ u, v \} \in E ^ { \prime \prime } \colon c ( u ) = c \wedge c ( v ) = x \} } \{ w ( \{ u, v \} ) \, \colon \text{dep} ( x ) < i \} & 1 \leq i \leq \text{dep} ( c ) \\ \infty & i > \text{dep} ( c ) \end{cases}$$

Note that we compute this array relative to a set of edges E ′′ . These edges are slightly truncated versions of the edges in E ′ , and we will compute this set during the algorithm.

## Algorithm 6 ClusterSensitivity ( G,E ,T,C ′ τ ) : Simulates MST sensitivity algorithm on C τ

- ′′
- 1: E ←∅ 2: for each non-tree edge e = { u, v } ∈ E ′ (where v is an ancestor of u ) do 3: Let v ′ be the first node on a path from v to u in T . 4: mc ( { v , v ′ } ← min { mc ( { v , v ′ } ) , w ( e ) } 5: Add an edge { u, v ′ } , with weight w e ( ) to E ′′ . 6: end for 7: for each non-root cluster c ∈ C τ do , 8: for for each i ∈ [ D T ] do determine the value A i c [ ] 9: end for 10: end for 11: for each non-root cluster c ∈ C τ (i.e., edge { c, p ( c ) } in T C ) do 12: minA ( c ) ← min { A x [ dep ( c )] : x is c or a descendant of c } 13: N c ← ( ℓ p c ( ( )) , p ( ℓ c ( )) , τ, minA ( c )) 14: mc ( { ℓ c , p ( ) ( ℓ c ( )) } ) ← min { mc ( { ℓ c , p ( ) ( ℓ c ( )) } ) , minA ( c ) } 15: end for 16: return N ′ = { N c : c ∈ C τ } : a set of root-to-leaf notes, one for each cluster in C τ

Lemma 4.9. After executing Algorithm 6 we have correctly computed:

- (i) mc values for each edge in T C τ ; and
- (ii) for each pair of clusters c , c c p ∈ C τ such that c c is a child of c p , the minimum weight of an edge in E ′ which covers the path from ℓ c ( p ) to p ℓ c ( ( c )) .

Proof. For part (i) , it is enough to show that Algorithm 6 correctly computes the mc values for each edge in T C . Recall that the mc value of a tree edge e is the minimum weight of any non-tree edge which covers e . Note that lines 1-5 of Algorithm 6 split each edge into two parts: the topmost 'arc' { v, v ′ } of the edge { u, v } , and the rest of the edge ( { u, v ′ } ). By line 4, mc ( v, v ′ ) is at most the weight of the topmost arc, and so it remains to consider whether lines 6-11 correctly compute the mc values for each tree edge relative to the edges in E ′′ after line 5.

As we assume as a precondition that the vertices of any non-tree edges are in an ancestor-descendant relation, we have, for each edge { u, p ( u ) } ∈ T C :

$$\ m c \left ( \{ u, p ( u ) \} \right ) \\ = & \min ( m c ( u, p ( u ) ), \min \{ w ( \{ v, v ^ { \prime } \} ) \, \colon \, v \, \text{is $u$ or a descendant of $u$, and $v^{\prime}$ is an ancestor of $u$} \} \right ) \\ = & \min ( m c ( u, p ( u ) ), \sum \, \min \, \min \{ w ( \{ v, v ^ { \prime } \} ) \, \colon \, v^{\prime}$ is an ancestor of $u$} \} \right )$$

Applying the definition of A u [ i ] ,

$$\ m c \left ( \{ u, p ( u ) \} \right ) = \min \left ( \ m c ( u, p ( u ) ), \quad \min _ { v \text{ is either } u \text{ or a descendant of } u } A _ { v } [ \text{dep} ( u ) ] \right ).$$

For part (ii) , we argue that the minimum weight non-tree edge covering the path from ℓ c ( p ) to p ℓ c ( ( c )) is exactly minA ( c c ) . First, note that we have already shown that minA ( c c ) is the minimum weight of a non-tree edge in E ′′ which covers the tree edge { ℓ c ( c ) ,

Fix some e = { u, v } ∈ E ′ , and suppose that v is an ancestor of u . Let c 1 = c τ ( u ) , c k = c τ ( v ) , and let c 2 . . . c k -1 be the other clusters on a path from c 1 to c k in T C τ .

p ℓ c ( ( c ) } . We prove part (ii) of the lemma by showing that the set of edges in E ′′ which cover the tree edge { ℓ c ( c ) , p ( ℓ c ( c )) } is the same as the set of edges in E ′′ which cover the path from ℓ c ( p ) to p ℓ c ( ( c )) .

Then, note that, since in Algorithm 5 we maintain the invariant that all edges in E ′ cover no edges in the clusters containing their endpoints, u must be the root of c 1 and p ℓ c ( ( k -1 )) = v . It it easy to see that e covers the edges between c 1 and c 2 , c 2 and c 2 . . . c k -1 and c k . It also covers the path from p ℓ c ( ( 1 )) to ℓ c ( 2 ) , from p ℓ c ( ( 2 )) to ℓ c ( 3 ) . . . , and from p ℓ c ( ( k -2 )) to ℓ c ( k -1 ) .

Edges in E ′′ are the same as edges in E ′ , except that the topmost arc (in the example above, the edge between c k -1 and c k ) have been removed. It is easy to check that once this is done, iff an edge in E ′′ covers the edge between c i and c i +1 , it also covers the path from p ℓ c ( ( i )) to ℓ c ( i +1 ) , and so we are done.

Next, we argue that we can implement Algorithm 6 in O (log D T ) rounds of sublinear MPC , with optimal global space.

Lemma 4.10. Algorithm 6 can be implemented deterministically on an MPC with s = O n ( δ ) and g = O n ( + m ) in O (log D T ) rounds.

Proof. We can compute the depth dep ( c ) in T C τ of each cluster c ∈ C τ , and we have already computed the DFS interval labeling of ℓ c ( ) . These steps can be implemented in O (log D T ) rounds. Recall that, with the DFS interval labeling of two clusters c and c ′ , we can decide whether c and c ′ are in an ancestor-descendant relationship.

For lines 7-10 of Algorithm 6, let us dedicate a set of consecutive machines M c,i for each non-root cluster c ∈ C τ and each depth i ∈ [ D T ] . For each c and i ∈ [ D T ] , all the edges in E ′′ from a node in c to an ancestor can be gathered onto M c,i using sorting in O (1) rounds. Then, for each c and i , we can find the minimum weight of an edge on M c,i .

For lines 1-6 of Algorithm 6, we can sort the edges in T C along with the non-tree edges in E ′ by the topmost endpoint. Let { u, v } be a non-tree edge in E ′ where v is an ancestor of u . By the invariant maintained in Algorithm 5, the child of v on the path from v to u in T is the root of a cluster. Therefore, using prefix-sum, we can then identify which child v ′ of v in T is on the path from v to u in T , for all such edges in parallel. Lines 4 and 5 then follow easily.

For lines 11-15 of Algorithm 6, we can compute minA ( c ) for all clusters c ∈ C using O D ( T ) parallel applications of the algorithm in [GLM + 23] for finding in parallel the minimum label in all subtrees in a tree. This requires an additional O D ( T ) global space for each node in T C , but since there are O n/D ( T ) nodes in T C , this is a total global space of O m ( + n ) , as required.

Note that the total space used in our MPC implementation is O nD ( T ) since we are storing an array of size D T for each non-root vertex.

## 4.3 Unwinding Cluster Contraction and Computing Sensitivity

For all edges in T C τ , we now have computed the mc (and thus sens ) values. It remains to compute the mc values of the vertices within the vertices of T C τ , which correspond to the clusters of C τ .

Our algorithm is as follows.

As part of our MST sensitivity algorithm in the previous section, for each cluster c ∈ C τ , for each child c 1 , c 2 . . . c k of c in T C τ , we computed a root-to-leaf note for the paths from ℓ c ( ) to p ℓ c ( ( 1 )) , p ( ℓ c ( 2 )) . . . , p ( ℓ c ( k )) . In this section we combine these with the root-to-leaf notes which were set aside during the cluster contraction part of the algorithm (Algorithm 5), and ensure that the mc value for each intra-cluster edge is at most the minimum weight of a root-to-leaf note which covers that edge, when we undo the cluster contraction steps.

Algorithm 7 UndoContractions ( G,T,N,C τ ) : Undo the cluster contractions and compute mc values for all edges

| 1: for i ∈ ( τ = O (log D T ) , . . . , 2 , 1) do   | 1: for i ∈ ( τ = O (log D T ) , . . . , 2 , 1) do                                                                   |
|-----------------------------------------------------|---------------------------------------------------------------------------------------------------------------------|
| 2:                                                  | for Each cluster c formed in iteration i of Algorithm 5, in parallel do                                             |
| 3:                                                  | Let c p be the senior sub-cluster of c ; let c 1 . . . c k be the junior sub-clusters of c .                        |
| 4:                                                  | for Each root-to-leaf note r = ( ℓ ( c ) , v, i, w ) , in parallel do                                               |
| 5:                                                  | c i ← The subcluster of c containing v .                                                                            |
| 6:                                                  | mc ( { ℓ ( c i ) , p ( ℓ ( c i )) } ) ← min { mc ( { ℓ ( c i ) , p ( ℓ ( c i )) } ) , w } .                         |
| 7:                                                  | Remove root-to-leaf note r from N .                                                                                 |
| 8:                                                  | Add root-to-leaf note ( ℓ ( c ) , p ( ℓ ( c i )) , I c p , w ) to N , where I c p is the iteration in which c i was |
| formed.                                             | formed.                                                                                                             |
| 9:                                                  | Add root-to-leaf note ( ℓ ( c i ) , v, I c i , w ) to N , where I c i is the iteration in which c i was formed.     |
| 10:                                                 | end for                                                                                                             |
| 11:                                                 | end for                                                                                                             |
| 12:                                                 | Remove duplicate root-to-leaf notes (those whose first three values are the same), keeping the one weight.          |
| with minimum                                        | with minimum                                                                                                        |
| 13:                                                 | end for                                                                                                             |

We first argue that the mc values which are computed during Algorithm 7 are correct:

Lemma 4.11. The mc values computed at the end of Algorithm 7 are correct: i.e., for all v ∈ V , mc ( v ) is the cost of the minimum edge which non-tree edge which covers (Definition 2.1) v .

Proof. Firstly, note that for all edges in T C τ (those edges which aren't 'inside' clusters), mc values have been computed correctly (Lemma 4.9 (i)).

Let e = { u, v } ∈ E \ T be a non-tree edge and let P be the path in T between u and v . Recall that the endpoints of all non-tree edges are between ancestors and descendants. Note that P comprises edges in T C τ (which we have already accounted for) and edges inside clusters in C τ . Let c ∈ C τ be a cluster. There are two cases:

We now argue that for all edges in T \ T C τ , mc values have been correctly computed. To do this, we look from the other perspective and show that each edge in E \ T is at least as large as the mc value for each edge in T \ T C τ which it covers.

- · Suppose u is an ancestor of ℓ c ( ) and v is in a descendant cluster of c . Then the section of the path which passes through c must go from the root of c to a leaf of c . By Lemma 4.9 (ii), the minimum weight of an edge in E ′ which covers each root-to-leaf path in c has been correctly computed, and e must weigh at least this value.
- · Suppose that u is inside c and P covers at least one edge in c . Then, during the cluster contraction process (Algorithm 5), (possibly several) root-to-leaf notes were created to account for this end-segment of P which is inside a cluster. The only place in our subroutines where root-to-leaf notes are deleted

is when another note covering the same path but with a lower weight is also present; therefore e must weight at least as much as the root-to-leaf note covering this segment of P .

Therefore root-to-leaf notes of at most weight w e ( ) are created for every edge in P \ T C τ (since edges in T C τ are accounted for).

It remains to show that, for each edge e on the path covered by a root-to-leaf note ( · , · , · , w ) , that mc ( e ) ≤ w . This is ensured by lines 6-9 of Algorithm 7. Root-to-leaf notes are split into three parts: a root-to-leaf note in the senior sub-cluster; a root-to-leaf note in a junior sub-cluster; and the edge between the two has its mc value updated, if applicable. Eventually all edges on the path of a root-to-leaf notes will have their mc value updated to the weight of that root-to-leaf note (if applicable), and will finish with at most that weight.

Finally, we show that Algorithm 7 can be implemented in sublinear MPC in O (log D T ) rounds and with optimal global memory:

Lemma 4.12. Algorithm 7 can be implemented deterministically on an MPC with s = O n ( δ ) and g = O n ( + m ) in O (log D T ) rounds.

Proof. We start by claiming that, at all times, N contains at most O n ( ) root-to-leaf notes.

Claim 4.13. Throughout the execution of Algorithm 7, | N | = O n ( ) .

As a simple consequence of Observation 2.10, we can, for each cluster, maintain a record of its subclusters and which iteration they were formed in. This information can be stored along with each cluster in C i . When evaluating which mc values to update and how and which root-to-leaf notes to create, machines have this information locally.

Claim 4.13 implies that when deduplicating the root-to-leaf notes (which can be done in O (1) rounds using sorting and prefix-sum), the global memory bounds are not exceeded.

We can set aside a set of machines dedicated to keeping track of and updating mc values for all tree edges. Since there are at any time O n ( ) root-to-leaf notes being dealt with in the for-loop from lines 4-10 (Claim 4.13), there are at most O n ( ) updates to these values per loop (line 6). These machines can use sorting and prefix-sum to update their stored mc values in O (1) rounds and O n ( ) memory.

It remains to prove Claim 4.13:

Proof of Claim 4.13. It suffices to bound the total possible number of non-duplicate root-to-leaf notes at any point, since when we potentially create additional duplicate notes (lines 8 and 9), this is only a constant-factor increase before we remove duplicates again in line 12.

It remains to bound the number of root-to-leaf notes where the leaf is also a leaf of T . Consider one such leaf l . We claim, that, at any time, that there is at most one root-to-leaf note with l as a leaf. This follows from two facts:

We will start by bounding the total number of root-to-leaf notes where the 'leaf' has at least one child in T . Fix an iteration i and a corresponding cluster decomposition C i , and consider a root-to-leaf note ( r, l, i, w ) . All children of l in T (at least one exists by assumption) must be leaders of a cluster in C i . Further, note that for each choice of i and l there is a unique r (the root of the cluster containing l in iteration i ). Therefore, we can charge each choice of i and l (where l has a child in T ) to a vertex in T C i . Using Observation 2.10, there at most O n ( ) clusters over all levels of the hierarchical clustering.

- · Only one root-to-leaf note containing l is created during Algorithm 5. Once a root-to-leaf note containing l is created (and the edge in question is truncated), case 4 or 5 of Definition 4.5 cannot apply to l anymore ( l will always be in a junior sub-cluster but will never be the root of it).
- · When a root-to-leaf note is processed in Algorithm 7, exactly one root-to-leaf note containing l is created.

This completes the proof of the claim.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00398v1-figure-6fc3fde9-414a-4776-8e76-04932f1cd2f4.jpg)

Finally, we conclude the section as a whole with the proof of Theorem 4.1:

Proof of Theorem 4.1. By Observations 4.2 and 4.3, it suffices to compute the values of mc for each treeedge. It is easy to see that given the mc values for all non-tree edges, we can compute the sens values for all non-tree edges in O (1) rounds.

All steps are deterministic except for the computation of the interval labeling (Lemma 2.14), which means that the algorithm as a whole succeeds with high probability.

The correctness of Algorithm 4 follows from Lemmas 4.9 and 4.11. Running time and memory constraints of Algorithm 4 follow from Lemmas 4.7, 4.10 and 4.12.

## 5 Lower Bound for MST Verification

In this section we give a simple lower bound result which shows that, conditioned on a popular 1-vs-2-cycle conjecture, our algorithm for MST verification is optimal.

First, we recall the 1-vs-2-cycle conjecture.

Conjecture 5.1 ( 1-vs-2-cycle Conjecture . ) Let δ &lt; 1 be an arbitrary positive constant. The problem of distinguishing one cycle of length n from two cycles of length n/ 2 requires Ω(log n ) rounds on an MPC with local memory s = O n ( δ ) .

Theorem 5.2 ( MST Verification Lower Bound . ) Let δ &lt; 1 be an arbitrary positive constant. Let G = ( V, E ) be an edge-weighted graph. Let T ⊆ E be a set of n -1 edges of G and let D T be the diameter of T .

Deciding whether T is a minimum spanning forest of G requires Ω(log D T ) rounds, on an MPC with with local memory s = O n ( δ ) , unless the 1-vs-2-cycle conjecture (Conjecture 5.1) is false.

Proof. Let G be a complete graph on some vertex set V , and suppose all edges in G have weight 1 . Let T ⊂ G be a spanning subgraph of G with n -1 edges. Note that D = D MST = 1 , but D T might be much larger.

Since all graphs with n -1 edges have the same weight, the problem of determining whether T is a minimum spanning tree of G is reduced to determining whether T is connected. Suppose there is a o (log D T ) round algorithm for deciding whether T is an MST of G . This would imply that we can decide whether T is connected in O (1) rounds. However, by [CC23], this requires Ω(log D T ) rounds, conditioned on the 1-vs-2-cycle conjecture.

## References

[ASS + 18a] Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 674-685. IEEE Computer Society, 2018.

[ASS + 18b] Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. CoRR , abs/1805.03055, 2018.

[ASZ19]

Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 14:1-14:16. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019.

| [BDE + 19]   | Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab Mirrokni. Near-optimal massively parallel graph connectivity. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 1615-1636. IEEE Computer Society, 2019.                 |
|--------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [BLM + 23]   | Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Optimal deter- ministic massively parallel connectivity on forests. In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2589-2631. SIAM, 2023.                                      |
| [CC23]       | Sam Coy and Artur Czumaj. Deterministic massively parallel connectivity. SIAM Journal on Computing , 52(5):1269-1318, 2023.                                                                                                                                                                             |
| [Cha00]      | Bernard Chazelle. A minimum spanning tree algorithm with inverse-Ackermann type complexity. Journal of the ACM , 47(6):1028-1047, 2000.                                                                                                                                                                 |
| [CKT96]      | Richard Cole, Philip N. Klein, and Robert Endre Tarjan. Finding minimum spanning forests in logarithmic time and linear work using random sampling. In Guy E. Blelloch, editor, Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) , pages 243-250. ACM, 1996. |
| [DG08]       | Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. Communications of the ACM , 51(1):107-113, January 2008.                                                                                                                                                     |
| [DRT92]      | Brandon Dixon, Monika Rauch, and Robert E Tarjan. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing , 21(6):1184-1192, 1992.                                                                                                                    |
| [DT97]       | Brandon Dixon and Robert Endre Tarjan. Optimal parallel verification of minimum spanning trees in logarithmic time. Algorithmica , 17(1):11-18, 1997.                                                                                                                                                   |
| [GH85]       | Ronald L. Graham and Pavol Hell. On the history of the minimum spanning tree problem. IEEE Annals of the History of Computing , 7(1):43-57, 1985.                                                                                                                                                       |
| [GLM + 23]   | Chetan Gupta, Rustam Latypov, Yannic Maus, Shreyas Pai, Simo Särkkä, Jan Studený, Jukka Suomela, Jara Uitto, and Hossein Vahidi. Fast dynamic programming in trees in the MPCmodel. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) . ACM Press, 2023.   |
| [GSZ11]      | Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the MapReduce framework. In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC) , pages 374-383, 2011.                                                                   |
| [JN18]       | Tomasz Jurdziński and Krzysztof Nowicki. MST in O (1) rounds of congested clique. In Pro- ceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2620-2632. SIAM, Philadelphia, PA, 2018.                                                                                 |
| [Kin97]      | Valerie King. A simpler minimum spanning tree verification algorithm. Algorithmica , 18(2):263- 270, 1997.                                                                                                                                                                                              |
| [KKT95]      | David R. Karger, Philip N. Klein, and Robert Endre Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM , 42(2):321-328, 1995.                                                                                                                                 |
| [Kom84]      | János Komlós. Linear verification for spanning trees. In Proceedings of the 25th Annual Sym- posium on Foundations of Computer Science (FOCS) , pages 201-206. IEEE Computer Society, 1984.                                                                                                             |
| [KPRS97]     | Valerie King, Chung Keung Poon, Vijaya Ramachandran, and Santanu Sinha. An optimal EREWPRAMalgorithm for minimum spanning tree verification. Information Processing Letters , 62(3):153-159, 1997.                                                                                                      |

| [KSV10]    | Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapRe- duce. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 938-948. SIAM, 2010.                                                                                                                                                     |
|------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [LMSV11]   | Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: A method for solving graph problems in MapReduce. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , pages 85-94, 2011.                                                                                                            |
| [Now21]    | Krzysztof Nowicki. A deterministic algorithm for the MST problem in constant rounds of con- gested clique. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC) , pages 1154-1165, 2021.                                                                                                                                                        |
| [Pet05]    | Seth Pettie. Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC) , volume 3827 of Lecture Notes in Computer Science , pages 964-973. Springer, 2005.                                                                                                  |
| [Pet15]    | Seth Pettie. Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. Jour- nal of Graph Algorithms and Applications , 19(1):375-391, 2015. A preliminary version appeared in Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC) , pp. 964-073, 2005, and in CoRR abs/1407.1910, http://arxiv.org/abs/1407.1910. |
| [PR02]     | Seth Pettie and Vijaya Ramachandran. An optimal minimum spanning tree algorithm. JACM , 49(1):16-34, 2002.                                                                                                                                                                                                                                                               |
| [Tar82]    | Robert Endre Tarjan. Sensitivity analysis of minimum spanning trees and shortest path trees. Information Processing Letters , 14(1):30-33, 1982. See Corrigendum, IPL 23(4), 219.                                                                                                                                                                                        |
| [Whi12]    | Tom White. Hadoop: The Definitive Guide . O'Reilly Media, Inc., US, 2012.                                                                                                                                                                                                                                                                                                |
| [ZCF + 10] | Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. In Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud) , 2010.                                                                                                                                         |

## A Conditional MST Lower Bound

For the sake of completeness of our arguments, we sketch a simple proof of a claim that, conditioned on the 1-vs-2-cycles conjecture, there is no o (log n ) -rounds MPC algorithm with s = O n ( δ ) local memory and polynomial global memory g = poly( n ) for the minimum spanning tree problem.

Claim A.1. Conditioned on the 1-vs-2 cycles Conjecture 5.1, there is no o (log D MST ) -rounds MPC algorithm for finding a minimum spanning tree, on sublinear MPC with polynomial global memory.

Proof. Let G = ( V, E ) be an input graph with the promise that G is either an n -vertex cycle or it consists of two disjoint n 2 -vertex cycles. Define a new weighted graph G ∗ with vertex set V ∗ = V ∪{ v ∗ } with v ∗ / V ∈ and edge set E ∗ = E ∪ {{ v ∗ , u } : u ∈ V } , and with edge weight w : E ∗ →R defined as follows:

$$w ( e ) = \begin{cases} 1 & \text{if $e\in E$} \\ 2 & \text{if $e\in \{\{v^{*}, u\} \colon u\in V\}$} \end{cases}$$

Notice that G ∗ is connected, has n + 1 vertices, 2 n edges, and diameter 2 . The diameter of a minimum spanning tree is Θ( n ) (whether G is one or two cycles).

Next, observe that if G is an n -vertex cycle then a minimum spanning tree algorithm, when run on G ∗ , returns a spanning tree of weight n + 1 , but if G consists of two disjoint n 2 -vertex cycles, then we get a spanning tree of weight n +2 .

This implies that if there is a minimum spanning tree algorithm which runs in o (log n ) rounds (even for constant diameter graphs) on sublinear MPC with polynomial global memory then the 1-vs-2-cycles conjecture fails.

This does not preclude the existence of an O (log D MST ) round algorithm for the problem (in the proof, O (log D MST ) = Ω(log n ) ). In fact, such an algorithm exists with larger global memory [ASS + 18a, CC23]. The proof does rule out the existence of an o (log D MST ) algorithm however, since o (log D MST ) = o (log n ) for all values of D MST .
Sam Coy Artur Czumaj Gopinath Mishra Anish Mukherjee
Log Diameter Rounds MST Verification and Sensitivity in MPC
We consider two natural variants of the problem of minimum spanning tree
(MST) of a graph in the parallel setting: MST verification (verifying if a
given tree is an MST) and the sensitivity analysis of an MST (finding the
lowest cost replacement edge for each edge of the MST). These two problems have
been studied extensively for sequential algorithms and for parallel algorithms
in the PRAM model of computation. In this paper, we extend the study to the
standard model of Massive Parallel Computation (MPC).
  It is known that for graphs of diameter $D$, the connectivity problem can be
solved in $O(\log D + \log\log n)$ rounds on an MPC with low local memory (each
machine can store only $O(n^{\delta})$ words for an arbitrary constant $\delta
> 0$) and with linear global memory, that is, with optimal utilization.
However, for the related task of finding an MST, we need $\Omega(\log
D_{\text{MST}})$ rounds, where $D_{\text{MST}}$ denotes the diameter of the
minimum spanning tree. The state of the art upper bound for MST is $O(\log n)$
rounds; the result follows by simulating existing PRAM algorithms. While this
bound may be optimal for general graphs, the benchmark of connectivity and
lower bound for MST suggest the target bound of $O(\log D_{\text{MST}})$
rounds, or possibly $O(\log D_{\text{MST}} + \log\log n)$ rounds. As for now,
we do not know if this bound is achievable for the MST problem on an MPC with
low local memory and linear global memory. In this paper, we show that two
natural variants of the MST problem: MST verification and sensitivity analysis
of an MST, can be completed in $O(\log D_T)$ rounds on an MPC with low local
memory and with linear global memory; here $D_T$ is the diameter of the input
``candidate MST'' $T$. The algorithms asymptotically match our lower bound,
conditioned on the 1-vs-2-cycle conjecture.