Deterministic Distance Approximation in MPC via Improved Hitting Sets∗ Kyungjin Cho, Michal Dory, Yannic Maus, Tijn de Vos
arXiv:2606.03674v1 [cs.DS] 2 Jun 2026
Abstract In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we significantly improve upon the state of the art in the deterministic Congested Clique. In particular, we obtain the following four results on undirected graphs: 1. In both linear MPC and Congested Clique, we obtain an O(k) stretch-spanner of a weighted graph of size O(n1+1/k ) in O(1) rounds, for some parameter k ≥ 0. For k = O(log n), this leads to an O(log n) approximation of APSP in constant rounds in both models. 2. In sublinear MPC, we obtain an O(k 1+ε )-stretch spanner of a weighted graph of size O(n1+1/k ) in O(log k) rounds, for any fixed constant ε > 0. 3. In Congested Clique, we obtain O(1)-approximate APSP for weighted graphs in O(log log log n) rounds. 4. In near-linear MPC, we obtain (1 + ε)-approximate single-source shortest paths and O(1)-approximate all-pairs shortest paths for unweighted graphs in poly log log n rounds. Our algorithm only requires a single near-linear memory machine, where the rest can have sublinear memory. Our deterministic algorithms obtain similar guarantees to the state of the art randomized algorithms without incurring additional factors in the round complexity. To obtain these results, we inspect the randomized algorithms and isolate a randomized sampling routine. Then we derandomize these sampling routines by using a deterministic hitting set. Hereto, we develop a versatile deterministic hitting set algorithm, which we hope will have further derandomization applications.
∗ This research was funded in whole or in part by the Austrian Science Fund (FWF) https://doi.org/10. 55776/P36280 and https://doi.org/10.55776/I6915. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. This research was supported by the Israel Science Foundation (grant No. 2829/25).
Contents 1 Introduction 1.1 Contributions on Distance Problems . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Spanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 A Glimpse at our Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Contributions on Computing Hitting Sets . . . . . . . . . . . . . . . . . . . . . .
1 3 3 4 5 6
2 Technical Overview 2.1 Deterministic Hitting Set Algorithms in a Nutshell . . . . . . . . . . . . . . . . . 2.1.1 Dominating Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Deterministic Algorithms for Distance Approximation . . . . . . . . . . . . . . . 2.3 Further Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 8 8 10 13
3 Graphs, MPC Primitives, and Derandomization 16 3.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 The MPC Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 MPC Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.4 Simulating MPC Algorithms in the Congested Clique . . . . . . . . . . . . . . . . 20 3.5 Hash Functions for Derandomization . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.6 Derandomization in MPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Hitting Sets in MPC 22 4.1 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Linear MPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.1 Fast Hitting Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.2 Fast Hitting Sets for large N . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2.3 Hitting Sets of Size O |U | dlog d + N/d . . . . . . . . . . . . . . . . . . . . 29 N . . . . . . . . . . . . . . . . . . . . . . . 30 4.2.4 Hitting Sets of Size O |U | log d 4.3 Sublinear MPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.1 Sparsification Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.2 Fast Hitting Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 N 4.3.3 Hitting Sets of Size O |U | log . . . . . . . . . . . . . . . . . . . . . . . 37 d 5 Application I: Spanner Algorithms 39 5.1 Unweighted Spanners in Linear MPC and Congested Clique . . . . . . . . . . . . 39 5.1.1 Implementation in the MPC model . . . . . . . . . . . . . . . . . . . . . . 40 5.1.2 Sparsification Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Weighted Spanners in Linear MPC and Congested Clique . . . . . . . . . . . . . 45 5.3 Weighted Spanners in Sublinear MPC . . . . . . . . . . . . . . . . . . . . . . . . 47 6 Application II: APSP Algorithms 53 6.1 A Constant Approximate Weighted APSP in the Congested Clique . . . . . . . . 53 6.2 A Constant Approximate Unweighted Shortest Paths in Near-Linear MPC . . . . 54 6.2.1 Multi-source restricted Bellman-Ford: Proof of Lemma 6.6 . . . . . . . . . 58 References
61
A Proof of the Conditional Expectation Lemma in MPC
68
1
Introduction
In the last decades, processing massive amounts of data has become omnipresent. Processing this data in parallel is one of the main approaches to achieve efficient algorithms. The massively parallel computation (MPC) model [KSV10] is a modern parallel model developed to model large-scale parallel processing settings such as MapReduce [DG08] , Hadoop [Whi12], Spark [ZCFS+10], and Dryad [IBYB+07], that deal with massive data. In this model, the input is distributed between a set of N machines each with limited memory L, that communicate with each other via all-to-all communication in synchronous rounds. In each round, each machine can send and receive a total of L words of O(log(N L)) bits and perform internal computation. The goal is to minimize the number of communication rounds. A central line of research focuses on obtaining fast algorithms for undirected graph problems in MPC. The ultimate goal is to develop algorithms that significantly outperform those in traditional parallel computing settings. Note that all graphs considered in this paper are undirected. There are several variants of the MPC model that mostly differ in the bound on the memory available per machine. In the super-linear MPC model each machine has L = n1+γ memory for a constant γ, where n is the number of vertices in the input graph, in the near-linear MPC model each machine has L = Õ(n) memory, in the linear MPC model each machine has L = O(n) memory1 , and in the sublinear MPC model each machine has L = nδ memory for a constant δ < 1. In each of these models, we ideally have O(m) total space, where m is the input size. Sometimes, algorithms incur a small overhead, e.g., they have Õ(m) or O(m1+ρ ) total space for some small constant ρ. For more details on the MPC model, see Section 3. Algorithms for the MPC Model The MPC model has received a lot of attention in recent years. A rich line of work led to fast algorithms for various graph problems such as connectivity [ASSW+18; BDEL+19; CC23; FGG22], minimum spanning tree [LMSV11; Now21], various coloring problems [CFGU+19; CDP21c], maximal matching and maximal independent set [CŁMM+18; GGKM+18; BBDF+19; BHH19], minimum cut [LMSV11; GN20], shortest paths and spanners [BDGM+21; DFKL21; FHO22; DM24], and more. The main goal is to obtain very fast algorithms that ideally take sublogarithmic or even constant number of rounds. While in the super-linear and linear memory regimes of MPC many problems indeed have constant or poly(log log n) round algorithms, in the sublinear memory regime many important problems such as computing minimum spanning tree or shortest paths are conjectured to require Ω(log n) rounds. Deterministic MPC algorithms While many of the algorithms discussed above are randomized, substantial effort has also been devoted to developing deterministic MPC algorithms. In several cases, these algorithms achieve runtimes matching the randomized state of the art—and sometimes even match known conditional lower bounds—for fundamental problems such as connectivity, minimum spanning tree, and vertex coloring [CDP21c; Now21; CC23; FGG22]. However, gaps between randomized and deterministic runtimes persist for other problems, including maximal matching, maximal independent set, and ruling sets [CDP21a; PP22; FGG23; GP24; JKPS25], as well as for many distance computation problems that are the primary focus of this work. Distance computation Distance problems are fundamental topics in graph algorithms, including the study of Single-Source Shortest Paths (SSSP), All-Pairs Shortest Paths (APSP), and spanners. The approximate SSSP problem asks to compute, for a given source vertex, approximate distances to all other vertices, while the APSP problem asks to compute approximate distances between every pair of vertices. For a weighted graph, a k-spanner is a sparse subgraph 1
We write Õ(f ) := O(f poly log f ) for any function f .
1
Regime
Stretch
Size
Rounds
Total space
Randomness
Congested Clique
O(k)
O(n1+1/k k)
O(log k)
-
Deterministic
[PY18]
Congested Clique
(1 + ε)(2k − 1)
O(n1+1/k )
O(1)
-
Randomized
[CZ22]
Congested Clique
O(k)
O(n1+1/k )
O(1)
-
Deterministic
This paper (Theorem 1.2)
Near-linear MPC
O(k)
O(n1+1/k )
O(1)
Õ(n + m)
Randomized
[DFKL21]
Linear MPC
O(k)
O(n1+1/k )
O(1)
O(n + m)
Deterministic
This paper (Theorem 1.2)
Sublinear MPC
O(k 1+ε )
O(n1+1/k log k)
O(log k)
Õ(m + n)
Randomized
[BDGM+21]
Sublinear MPC
O(k 1+ε )
O(n1+1/k )
O(log k)
O(m + n)
Deterministic
This paper (Theorem 1.3)
Table 1: Summary of our spanner algorithms and the previous results. Regime
Approximate
Rounds
Randomness
Weighted
Congested Clique
O(1)-approximate
O(log log log n)
Randomized
Weighted
Congested Clique
(3 + ε)-approximate
O(log
2
n/ε2 )
Deterministic
Weighted
[CDKL21]
Congested Clique
O(1)-approximate
O(log log log n)
Deterministic
Weighted
This paper (Theorem 1.4)
Near-linear MPC
O(log n)-approximate
O(1)
Randomized
Weighted
[DFKL21; FHO22]
Linear MPC
O(log n)-approximate
O(1)
Deterministic
Weighted
This paper (Corollary 6.1)
Near-linear MPC
O(1)-approximate
poly(log log n)
Randomized
Unweighted
[DM24]
Near-linear MPC
O(1)-approximate
poly(log log n)
Deterministic
Unweighted
This paper (Theorem 1.6)
[BCCD+24]
Table 2: Summary of our APSP algorithms and the previous sublogarithmic results. that approximately preserves pairwise distances up to a multiplicative k factor. Any graph with n vertices admits a (2k − 1)-spanner of size at most O(n1+1/k ) [ADDJ+93]. Spanners have been used for various distance problems, including transhipment-based distance approximation [Li20; BFKL21] and fast distance sketches [DN20]. Due to their theoretical significance and various real-world applications, these problems have been extensively studied from multiple perspectives. In particular, there has been substantial recent progress in developing MPC algorithms. Polylogarithmic-round MPC algorithms for distance computation In sublinear MPC there are polylogarithmic algorithms for APSP and SSSP, including deterministic algorithms. Note that in the sublinear MPC model there is a conditional Ω(log n) lower bound for these problems based on the widely believed 1-vs-2 cycles conjecture, see, e.g., [GKU19; NS22]. Hajiaghayi, Lattanzi, Seddighin, and Stein [HLSS19] give a deterministic O(log n)-round algorithm for APSP in MPC with nδ memory per machine and O(n3−δ/2 ) total space. There is also a randomized poly(log n)-round sublinear MPC algorithm for distance sketches by Dinitz and Nazari [DN20]. These results are explicit MPC algorithms. In addition, many implicit MPC results arise from simulations of classical PRAM algorithms. In particular, PRAM algorithms that use a polynomial number of processors can be simulated in the MPC model with only constant overhead in round complexity [GSZ11]. In sublinear MPC, this leads to poly(log n)-round algorithms for (1+ε)-approximate SSSP [Li20; ASZ20; EM21; RGHZ+22] and poly log n-spanners [BEGG+22]. Many of these algorithms are deterministic [EM21; RGHZ+22; BEGG+22]. Sublogarithmic-round MPC algorithms for distance computation As discussed above, in sublinear MPC there is a conditional Ω(log n) lower bound for approximate shortest paths, however this lower bound does not apply to spanners and there are indeed faster algorithms for constructing graph spanners. In addition, in the near-linear memory MPC there are sublogarithmic algorithms for approximate shortest paths as we discuss next. For spanners, [BDGM+21] provide a randomized algorithm that computes an O(k 1+ε )spanner of size O(n1+1/k ) in O(log k) rounds. In the near-linear MPC model, there are faster 2
randomized O(1)-round algorithms to compute an O(k)-spanner with O(n1+1/k ) edges [DFKL21; FHO22]. Moreover, there are O(1)-round O(log n)-approximation algorithms for weighted APSP in the near-linear MPC model, based on the construction of spanners with stretch O(log n) [BDGM+21; DFKL21; FHO22]. In unweighted graphs there are randomized poly(log log n)-round2 algorithms for (1 + ε)approximate SSSP and O(1)-approximate APSP using one near-linear memory machine, where the rest of machines can have sublinear memory [DM24]. All the above mentioned algorithms are randomized, which leads to the following open question: Question 1.1. Can we obtain deterministic algorithms with sublogarithmic round complexity for distance computation in MPC?
1.1
Contributions on Distance Problems
In this paper, we answer Question 1.1 in the affirmative: we give the first sublogarithmic-round deterministic MPC algorithms for spanners and approximate shortest paths. Moreover, our algorithms have optimal or close-to-optimal total space. Since linear MPC algorithms transfer to the so-called Congested Clique, we also obtain novel results there – sometimes improving significantly on the state of the art. In the Congested Clique model [LPSPP05], we have an n-node communication network and an input graph G = (V, E) on the same nodes, where each node initially knows its incident edges. Computation proceeds in synchronous rounds: in each round, every node can send an O(log n)-bit message to every other node, and perform unlimited local computation between rounds. The objective is to solve a problem on G using as few rounds as possible. See Section 2.3 for existing work in the Congested Clique model. We remark that while linear MPC algorithms can be simulated in Congested Clique [BDH18], most existing Congested Clique algorithms do not directly imply MPC algorithms as the memory requirements do not fit the MPC model. Additionally, we also obtain the first deterministic sublogarithmic round algorithms for computing spanners in the sublinear MPC model. 1.1.1
Spanners
Linear MPC and Congested Clique (Sections 5.1 and 5.2) Our first result is an O(k)stretch spanner of size O(n1+1/k ) in linear MPC and Congested Clique. Theorem 1.2. There exists a deterministic algorithm that, given a positive integer k and a weighted graph G = (V, E, w) with w : E → [poly n] on n vertices, computes an O(k)-spanner with O(n1+1/k ) edges in constant rounds in the linear MPC model using O(m + n) total space. Furthermore, it can be simulated in the Congested Clique. This is the first deterministic sublogarithmic-round spanner construction in the MPC model. It matches the randomized state-of-the-art runtime by Dory, Fischer, Khoury, and Leitersdorf [DFKL21] while slightly improving both the size of the spanner and the total memory size by a log n factor. In Congested Clique, this improves upon the deterministic state of the art by Parter and Yogev [PY18], who compute an O(k)-stretch spanner of size O(k · n1+1/k ) in O(log k) rounds. Chechik and Zhang [CZ22] provide faster randomized spanners with stretch (1 + ε)(2k − 1) and size O(n1+1/k ) in constant rounds. We match their results up to constant factors. Our spanner construction works in linear MPC, where [CZ22] does not translate to MPC because of its total memory requirements. 2
In this introduction, we consider ε to be a constant.
3
By setting k = log n, Theorem 1.2 gives an O(log n)-spanner of size O(n), that fits in one machine not only in the Congested Clique but also in the linear MPC model with O(n) local space. Furthermore, if we have a machine storing such a spanner, we can locally compute an O(log n)-approximate APSP. Therefore, we can obtain a constant round algorithm for O(log n)approximate APSP in either model. See Corollary 6.1 in Section 6 for details. Sublinear MPC (Section 5.3) Also in the sublinear MPC model, we give the first sublogarithmicround deterministic spanner algorithm. Theorem 1.3. [Simplified version of Theorem 5.7] For constants δ, ε < 1, given a weighted graph G on n vertices and positive parameter k ≥ 1, we can deterministically construct an O(k 1+ε )spanner of G with O(n1+1/k ) edges in O(log k) rounds in the sublinear MPC model with O(nδ ) local space and O(m + n) total space. This improves exponentially on the current state-of-the art deterministic algorithm [BEGG+22] and it nearly matches the randomized state of the art by Biswas, Dory, Ghaffari, Mitrović, and Nazari [BDGM+21] up to a constant factor in the stretch, size, and the round complexity. Moreover, we improve the total space from Õ(m + n) to O(m + n). The round complexity of Theorem 1.3 is nearly optimal, assuming the aforementioned 1-vs2 cycle conjecture. This follows from an Ω(k) lower bound in the distributed LOCAL model [DGPV08] for the closely related problem of constructing spanners with optimal parameters, namely (2k − 1)-spanners with O(n1+1/k ) edges, which implies a conditional lower bound of Ω(log k) in the sublinear MPC model [GKU19]. 1.1.2
Shortest Paths
As already mentioned above, we can obtain O(log n)-approximate APSP algorithms through the computation of spanners. Next, we present our results that compute O(1)-approximation for APSP directly. Congested Clique (Section 6.1) In Congested Clique, we provide an algorithm for constant approximate APSP. Theorem 1.4. There exists a deterministic algorithm that, given a weighted graph G = (V, E, w) with w : E → [poly n] on n vertices, computes O(1)-approximate APSP in O(log log log n) rounds in Congested Clique. We obtain this result by derandomizing the algorithm of Bui, Chandra, Chang, Dory, and Leitersdorf [BCCD+24] in the same number of rounds and only incurring another constant factor in the stretch. This is exponentially faster than the previous fastest deterministic constant approximation for APSP: in unweighted graphs, Dory and Parter [DP22] compute (2 + ε)-APSP in poly(log log n) rounds. In weighted graphs, we improve double-exponentially over the state of the art: Censor-Hillel, Dory, Korhonen, and Leitersdorf [CDKL21] compute (3 + ε)-APSP in O(log2 n/ε2 ) rounds. Near-Linear MPC (Section 6.2) We also study approximate shortest paths in the nearlinear MPC model. In fact, our results here are even stronger and use only a few near-linear space machines, while additional machines can have sublinear local space. This setting is also known as the heterogeneous MPC model, introduced by [FHO25]. In particular, our approximate SSSP and APSP algorithms require only one machine with near-linear space, while the approximate Multi-Source Shortest Paths (MSSP) algorithm requires a near-linear space machine for each source. 4
We give the first deterministic algorithms for approximate SSSP, MSSP, and APSP for unweighted graphs. It matches the randomized state of the art by Dory and Matar [DM24]. In particular, we derive an MSSP algorithm: for a given set of sources S ⊆ V , it outputs approximate distances between every vertices s ∈ S and v ∈ V by using |S| machines with near-linear local space and additional sublinear memory machines. Theorem 1.5. [Simplified version of Theorem 6.3] Let G = (V, E) be an unweighted graph on n vertices and m edges, and let δ > 0 and ε, ρ < 1/2 be constants. For a fixed source set S ⊆ V of size O(nρ ), there is a deterministic algorithm that computes all (1+ε) approximate shortest paths for every pairs (s, v) ∈ S × V in poly log log n rounds in the MPC model using |S| machines with Õ(n) space and additional machines with O(nδ ) local space and Õ((m + n1+ρ )nρ ) total space. Note that Theorem 1.5 implies an approximate SSSP algorithm using a single near-linear space machine. We also give a deterministic algorithm to construct a data structure supporting constant-round queries for approximate APSP by using a single machine with near-linear space. Theorem 1.6. [Simplified version of Theorem 6.4] Let G = (V, E) be an unweighted graph on n vertices and m edges, and let δ > 0 and ε, ρ < 1/2, and 2 ≤ k ≤ 1/ρ be constants. There is a deterministic algorithm that computes a distance oracle of size Õ(kn1+1/k ) in poly log log n rounds in the MPC model using a single machine with Õ(n) space and additional machines with O(nδ ) local space and Õ((m + n1+ρ )n1/k ) total space. Our oracle supports O(1)-round queries for (1 + ε)(2k − 1)-approximate distances between any two vertices in G. We can further improve the total space in the above theorems to O(m + n1+c ) for a small constant c > 0 at the cost of increasing the stretch by a constant factor, as discussed in [DM24]. In particular, if m = Ω(n1+c ), the total space reduces to O(m). To get this, we can first use our spanner algorithms and then run the approximate shortest paths algorithms on the spanner. Such an approach will increase the approximation factor to poly(1/c) while improving the total memory to O(m + n1+c ). See Section 6.2 for details.
1.2
A Glimpse at our Techniques
For our distance computation results, we build on and adapt the algorithmic techniques underlying the randomized state-of-the-art approaches [DFKL21; BDGM+21; BCCD+24; DM24]. A key step in our approach is to isolate the role of randomness in these algorithms and identify a single structural component responsible for it, which in all cases can be modeled as an instance of the hitting set problem. For some problems, making this structure explicit (and efficiently solvable with deterministic algorithms) requires modifications to the respective original algorithm. In the hitting set problem, we are given a finite universe of elements U , and N subsets S1 , . . . , SN ⊆ U . A hitting set D ⊆ U is a set such that Si ∩ D ̸= ∅ for all i ∈ [N ]. Trivially, U is a hitting set itself. The aim is to compute a hitting set of small size. When we are additionally guaranteed that each set Si contains at least d elements, then we know that a simple greedy |U | log N algorithm [Lov75] gives a hitting set of size O . However, such an algorithm is highly d sequential and not suitable for models. A simple random sampling approach also distributed |U | log N gives a hitting set of size O : add each element u ∈ U independently to D with d probability p = logdN . We provide efficient deterministic algorithms to solve the hitting set problem, for a wide range of parameter regimes. In particular, we compute a hitting set of the aforementioned size in O(log log d) rounds. We also give a constant round algorithm that | computes a slightly larger hitting set of size O( d|U 0.99 ). This suboptimal size is still a sparse enough deterministic primitive for many applications. In particular, we use it to obtain many of the results in Section 1.1. 5
1.3
Contributions on Computing Hitting Sets
When considering the hitting set problem in the MPC model, it is not immediately clear what the ‘linear’ and ‘sublinear’ memory regimes are. In this paper, we consider it linear MPC when the local space L is at least d, such that each set Si fits in a machine. To the best of our knowledge, previous work always set L = |U | (which implies L ≥ d). We choose the more flexible L ≥ d such that the algorithm is more versatile, as is necessary for some of our applications. In this regime, we obtain the following theorem. Theorem 1.7. Let L be the parameter denoting the local space. There is a deterministic MPC algorithm that, given a universe U , a number d ≤ min{|U |, L} and a collection of N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ], that computes a hitting set: | 1. of size O d|U in O(1) rounds; or 0.99 2. of size O
|U | log d d
in O(log log d) rounds.
P |S | Both algorithms assume N ≤ |U | = poly L and use linear total space: O L + |U | + N i . i=1 For most applications, N ≤ |U | = poly L is a reasonable assumption. In Section 4 we provide additional algorithms without this assumption. We also study the case that L < d, which we call sublinear as single sets do not even fit into a machine. As is customary, we ask that L = Θ(dδ ) for some constant δ. Theorem 1.8. Let δ ≤ 1 be a positive constant. There is a deterministic MPC algorithm that, given a universe U , a number d ≤ |U | and a collection of N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ], that computes a hitting set: log d 1. of size O |Ud|0.99 in O(1) rounds; or 2. of size O
|U | log d d
in O(log log d) rounds with O(dδ ) local space.
Both algorithms assume |U |, N = poly d, use O(dδ ) local space, and use linear total space: PN O(|U | + i=1 |Si |). An important point of this “linear” and “sublinear” hitting set distinction, is that does not necessarily correspond to the applications in linear and sublinear MPC graph problems. To be precise, we use the “linear hitting set” in some “sublinear MPC” graph algorithms. In such applications, we have Θ(nγ ) local space. If d < nγ in our hitting set instance, we can use the “linear hitting set”. If d ≥ nγ , we use the “sublinear hitting set”. Note that since Theorem 1.8 required |U |, N = poly d, it cannot be applied to (nontrivial) instances with small, e.g., constant, d. However, exactly in such a regime, we can use the “linear hitting set”. We derandomize the computation of general hitting sets for the full range of variables, including d ≥ nδ , and show that this has many applications: it is sufficient to derandomize spanners and approximate shortest paths in linear and sublinear MPC. Since derandomizing random sampling is a fundamental problem, we hope that our general deterministic hitting set will find applications in the derandomization of other problems. Comparison to prior work Theorems 1.7 and 1.8 improve and generalize the state of the art for hitting sets in MPC: [CC23; FGG22] compute hitting sets of size O(|U |/d0.2 ) for the special case that |U | = N and d ≤ nδ in constant rounds in sublinear MPC. This result is not sufficient for us for two reasons: 1) The upper bound of O(|U |/d0.2 ) is not small enough for our applications. In our distance computations, it is crucial that the hitting set is almost the same 6
size as the randomized ideal O(|U | log n/d). 2) For Theorems 1.5, 1.6 and 5.7, we also need hitting sets in the truly sublinear regime where d ≥ nδ . In a broad sense, random sampling for problem specific ‘hitting events’ has been derandomized for several linear and sublinear MPC problems [CDP21c; PP22; FGG23; GP24; JKPS25]. In both hitting set algorithms and in most of these other works, it is assumed that d ≤ nδ . We give an overview of our hitting set results, how we obtain them, and how they can be used to derandomize distance problems in Section 2.
7
2
Technical Overview
In Section 2.1 we present our deterministic hitting set algorithms in a nutshell. Then, in Section 2.2 we give an overview of the randomized components in the state-of-the-art algorithms for the distance problems presented in Section 1.1 and how we can use our deterministic hitting set algorithms to systematically replace these randomized procedures.
2.1
Deterministic Hitting Set Algorithms in a Nutshell
To showcase our approach without many of the technical notation and details, we first consider a special case of the hitting set problem: the dominating set problem. For many of the theorems in this paper, the full generality of the hitting set problem is not necessary, and the dominating set problem suffices. For this overview, we further restrict to d-regular graphs, i.e., |N (v)| = d for every v ∈ V . Here N (v) := {v} ∪ {u ∈ V : {u, v} ∈ E} denotes the neighborhood of v. 2.1.1
Dominating Sets
We define a d-dominating set as follows. Definition 2.1. Let G = (V, E) be a graph. A d-dominating set is a subset of vertices D ⊆ V such that for every vertex v ∈ V \ D with deg(v) ≥ d, we have N (v) ∩ D ̸= ∅. n First, we sketch how to obtain a d-dominating set of size O n log using a randomized d algorithm. This algorithm has two phases. First, we sample each vertex v ∈ V with probability p = log n/d and denote the set of sampled vertices by Ds . Some vertices v ∈ V may still be uncovered, i.e., N (v) ∩ Ds = ∅ holds. Let Ds′ be the set of uncovered vertices. By construction, D := Ds ∪ Ds′ is a d-dominating set of G. Next, we consider the size of D. By linearity of expectation, we obtain E[|Ds |] = O(np) = O(n log n/d). For the size of Ds′ , consider a vertex v. The probability that v is not covered by Ds is at most (1 − p)
|N (v)|
=
1 − logd n
d
≤ e− log n = n−1 .
(1)
Now, again by linearity of expectation, we obtain that |Ds′ | ≤ 1 in expectation. Concluding, the expected size of the dominating set is E[|D|] = E[|Ds |] + E[|Ds′ |] = O(n log n/d) + 1 = O(n log n/d). Derandomization procedure To derandomize the process described above, we use the method of conditional expectation [Lub93; MNN+89]. This has become a standard technique in designing deterministic distributed algorithms in MPC, in particular see, e.g., [GHK18; GK18; PY18; CPS20; CDP21b; CDP21c; BEGG+22; DP22; PP22; CC23; FGG23; GGHI+23; GP24; JKPS25]. In the MPC model this derandomization method is particularly efficient if the randomness for the algorithm is very restricted in the sense that it can be extracted from an (extremely) short random seed. Next, we will discuss the method yielding a fully deterministic algorithm in more detail. For now, assume we are given a randomized dominating set algorithm whose only use of randomness is restricted to a random seed of b bits – think of a logarithmic seed length. If the expected dominating set size of the algorithm is at most some value x, then the goal of the method is to deterministically compute a random seed s∗ that attains this expectation; once the seed s∗ is known we can run the given algorithm using s∗ as the (deterministic) source of randomness and can deterministically compute a dominating set with size at most x. 8
To see how a seed s leads to a dominating set, we let each random seed s denote a set of sampled vertices Ds . We let Ds′ ⊆ V denote the set of vertices that are not covered, and hence added in phase two. This means we obtain the d-dominating set Ds ∪ Ds′ . As said above, the goal is now to find s∗ such that |Ds∗ ∪ Ds′ ∗ | ≤ x. This is done iteratively, by considering Θ(log n) bits of s∗ at a time, and compute what the best choice is for these bits: given a prefix r, we need to compute the next Θ(log n) bits. The following observation summarizes the crucial step in our derandomization method (Lemma 3.8). Observation 2.2. Given a prefix r, to compute the next Θ(log n) bits, we need to determine if v ∈ Ds or v ∈ Ds′ for all seeds s with prefix r in parallel. In particular, this means it is sufficient if we can determine if v ∈ Ds or v ∈ Ds′ for any seed s without communication. We show that in the linear MPC model, we can store the information such that v ∈ Ds or and v ∈ Ds′ can both be checked internally. We repeat this for O(⌈ logb n ⌉) iterations until all bits are fixed. Short random seeds. In the randomized sampling-based algorithm at the start of this section, we sampled each vertex independently with probability p. This needs at least one random bit per vertex, so at least n random bits in total. It turns out that we can cope with less randomness. We show that we in total need either 1. O(log n · log log d) bits for a dominating set of size O(n log n/d); or 2. O(log n) random bits for a dominating set of size O(n/d0.99 ). As explained above, this leads to O(1) and O(log log d)-round algorithms respectively. Many applications (sometimes after modifications) do not need dominating sets of the optimal size, and the slightly increased size of (2) suffices. Thus, for this warm-up we focus on (2). Here, we sample with probability p = 1/d0.99 rather than the optimal p = log n/d. This means that the expected size of Ds becomes O(n/d0.99 ). By this increased size, we obtain some slack in the randomness: we no longer need complete independence between vertices to bound the size of the uncovered vertices Ds′ . Instead, O(1)-wise independence suffices3 . Vadhan [Vad12] gives a procedure to extract n O(1)-wise independent random variables sufficient for our sampling process from a seed with O(log n) random bits. Tail bounds for k-wise independent random variable then show that a vertex is uncovered with probability at most 1/d (compare to Equation (1)). Hence the expected number of vertices Ds′ that join in the second phase is O(n/d). In total this gives a d-dominating set of size O(n/d0.99 ) + O(n/d) = O(n/d0.99 ). Combining (2) with the explained derandomization method, we obtain the following simplified version of Theorem 1.7. Theorem 2.3. There exists a deterministic MPC algorithm that, given a d-regular graph G = n (V, E) on n vertices and m edges, computes a d-dominating set of size O( d0.99 ) in constant rounds. The algorithm uses linear Θ(n) local space and O(m) total space. To obtain an analogous result in the sublinear regime, another challenge appears. We describe this challenge and how to overcome it next. Sublinear MPC In the sublinear MPC model, we only have O(nδ ) local space, for some constant δ. In this regime, we can still internally find out if v ∈ Ds for a single random seed s as required in Observation 2.2. However, to see if v ∈ Ds′ , i.e., to see if N (v) ∩ Ds = ∅ for poly n seeds in parallel, we need access to all of N (v). Since N (v) does not necessarily fit on 3 Given n random variables X1 , . . . Xn , we say that they are k-wise independent if any subset of k random variables behaves as if they are independent. For (1), we use a different way to limit the seed size via pseudorandom generators [GY20].
9
a single machine, we cannot check without communication if N (v) ∩ Ds = ∅. This means that without adaptations, the explained derandomization cannot be applied. Most previous sublinear MPC algorithms [FGG22; CC23; FGG23] get around this by assuming that d ≤ nδ holds for their dominating set (hitting set) instance. However, not all applications satisfy d ≤ nδ . We overcome this by introducing an additional sparsification step. A similar approach was applied by Giliberti and Parsaeian [GP24] for the special case of ruling sets. Sparsification in Sublinear MPC The goal of our sparsification step is to obtain some subset V ′ ⊆ V , such that N (v) ∩ V ′ = nδ for every node v ∈ V . Let us first consider a simple randomized routine that achieves this (in expectation): we sample every node with probability nδ /d. This gives the following guarantees (in expectation): • d′ (v) := |N (v) ∩ V ′ | = nδ , and δ
• |V ′ | = n · nd . Given such a set V ′ , we can fall back for the linearcase sinced′ ≤ nδ . This to ′the algorithm δ |V | n would give a dominating set of size O n0.99δ = O n · d·nn0.99δ = O d·(nδn)−0.01 = O d0.99 , where the last equality holds since d ≥ nδ . So we reduced our problem to finding V ′ deterministically; we cannot directly sample with δ probability p = nd and use the same method for derandomization suffers from the exact same problem as before. Instead we sample iteratively with probabilities p1 , p2 , . . . , pk such that p = p1 · p2 · · · pk , and each pi ≥ 1/nδ/2 – for this overview, we assume pi = 1/nδ/2 for each i. In the randomized algorithm, this leads to exactly the same results. However, we now have a big advantage: if we sample with probability pi , we can satisfy Observation 2.2 as follows. Let v ∈ V be some node with d ≫ nδ neighbors stored on d/nδ consecutive machines. With one sampling step, the expected number of sampled nodes on each machine is nδ · pi = nδ · 1/nδ/2 = nδ/2 . And here is the crux: the number of sampled nodes on each machine can be checked locally, without any communication, satisfying Observation 2.2. Moreover, since this expectation is still quite large, we can use tail bounds to show that even with limited dependence, we obtain this expectation. In the above, we changed the perspective from nodes to machines: when sampling with a too low probability, there is only a guarantee on the sampled nodes in the neighborhood as a whole, not on each machine. Instead, we measure the quality of a seed on each machine, for which no communication is necessary. To ensure feasibility of our subsampling, i.e., to ensure that the set of sampled nodes is not too small, we apply our derandomization method with an adjusted potential function. For full details we refer to Section 4.3. So combining our sparsification step with the linear MPC algorithm on the sparsified instance, we obtain the following simplified version of Theorem 1.8. Theorem 2.4. Let δ > 0 be a positive constant. There exists a deterministic MPC algorithm that, given a d-regular graph G = (V, E) on n vertices and m edges, for some d = nΩ(1) , computes n a d-dominating set of size O( d0.99 ) in constant rounds. The algorithm uses linear Θ(nδ ) local space and O(m) total space.
2.2
Deterministic Algorithms for Distance Approximation
In this paper, we design algorithms for distance problems using hitting set algorithms as a central tool. Distance problems aim to (approximately) compute the distances between pairs of vertices in a graph. A fundamental strategy for coping with the complexity of shortest paths is to compress the global distance structure into a small set of representative vertices. A basic 10
example is the clustering technique used to construct a spanner. It aims to decompose the vertex set into several clusters so that the vertices belonging to the same clusters are close to each other. Then the distance between clusters approximates the distance between two vertices in the original graph. For a simple case, we consider an unweighted d-regular graph. The idea is to select a small set of vertices such that each vertex v has a selected vertex among v or its neighbors. Then we can set a cluster as the set of vertices adjacent to the same selected vertex. If a vertex v is adjacent to multiple selected vertices, then it chooses an arbitrary one and joins the cluster. A clustering with x clusters yields an O(1)-spanner with O(n+x2 ) edges consisting of (i) one edge between every two adjacent clusters and (ii) one edge between each non-selected vertex and its adjacent selected vertex. We can further sparsify the graph by (possibly recursively) computing a spanner of the graph obtained from the clustering while increasing the stretch. In summary, partitioning the vertex set into a small number of clusters yields a sparse spanner. The key step in computing such a clustering is to select a small set of vertices such that every non-selected vertex is adjacent to at least one selected vertex. This selection task can be formulated as a hitting set problem on the graph; in particular, since we have a d-regular graph, it corresponds exactly to the d-dominating set problem introduced in Section 2.1. Many randomized algorithms for approximate distance problems rely on sampling a small set of representative vertices, with the goal of ensuring suitable coverage of the graph, typically by guaranteeing that a sampled vertex lies close to most vertices. In this paper, we replace these random sampling steps with deterministic hitting set constructions to obtain our algorithms for distance problems. In the following, we briefly outline this approach for each of the distance problems considered in this paper. Spanners in linear MPC and Congested Clique As summarized by Theorem 1.2, we study spanners of weighted graphs in linear MPC and Congested Clique. In Congested Clique, there is a reduction that extends a spanner algorithm for unweighted graphs to weighted graphs [CZ22]. We extend this reduction to work in linear MPC, see Section 5.2. Therefore, we focus on derandomizing the algorithm of [DFKL21] for unweighted graphs, which is a constant-round randomized algorithm in Congested Clique and near-linear MPC. The algorithm partitions the graph into O(log n) hierarchical levels according to vertex degrees. At each level, it utilizes the presented clustering technique by selecting a small vertex set such that every vertex with a certain degree is adjacent to at least one selected vertex, and contracting the vertices to the adjacent selected vertex in some deterministic canonical way. We obtain a separate contracted graph for each of the O(log n) levels. It then computes a spanner of each one of the contracted graphs using a randomized sparsification technique. By executing the processes for all hierarchy levels in parallel, they achieve a constant-round algorithm. However, to enable this parallelism, they require Θ(n log n) local space even for the MPC model. In summary, the algorithm uses randomization in two places, first for constructing O(log n) clustering graphs. Second, for a sparsification that allows to construct sparse spanners on each one of the clustering graphs. In Section 5.1, we show how to derandomize the algorithm. We also improve the local space to O(n). Recall that we need to derandomize two steps. First, building the clustering graphs. Second, the randomized sparsification technique. For the latter step, we extend a deterministic sparsification designed for Congested Clique by Leitersdorf [Lei22]. Our main contribution lies in the first step to build the clustering. As discussed above, the clustering problem can be phrased as a hitting set problem and we use the hitting set algorithm of Theorem 1.7 Part 1 to achieve a deterministic algorithm. This algorithm runs in constant rounds, but this comes at a cost that the resulting hitting set is significantly larger than the expected size of the their randomized algorithm. We prove that this is still good enough for the construction. Moreover, we can construct the O(log n) hitting
11
sets simultaneously in O(1) rounds. Finally, we use a tighter analysis and obtain a linear-space MPC algorithm, rather than a near-linear-space one. Spanners in sublinear MPC To obtain the deterministic spanner algorithm in the sublinear MPC model from Theorem 1.3 we deviate from the above procedure but instead build upon the randomized algorithm from [BDGM+21].Their randomized spanner algorithm for the sublinear MPC model uses a recursive hierarchical structure [BDGM+21]. At the core, it combines certain steps of growing clusters and steps where it contracts clusters improving the round complexity from O(k) to O(log k) while increasing the stretch compared to the seminal spanner algorithm by Baswana and Sen [BS07]. The randomness of the original algorithm occurs in the steps that grow clusters. We reduce it to a hitting set problem: • Given a set C of clusters of a weighted graph G and a parameter 0 < p < 1, for each node v in G the set Sv ⊆ C is defined as the 1/p closest clusters of C to v and adjacent to v in G. • The goal is to compute D ⊆ C so that D ∩ Sv ̸= ∅ for every node v ∈ G. In Section 5.3, we derandomize this algorithm using our constant-round hitting set algorithms in the sublinear MPC model (Theorems 1.7 and 1.8 Part 1). The obtained hitting set size is not optimal and may exceed the expected size achieved by the randomized algorithm. To address the overhead, we rebalance the parameters of the algorithm, including the probabilities p used in the subroutines and the hierarchical depths. Constant approximate APSP in the Congested Clique Note that our spanner algorithm deterministically constructs an O(log n)-spanner with O(n) edges for an edge-weighted graph with n vertices. The spanner algorithm immediately gives an O(log n)-approximate APSP algorithm running in constant rounds in the Congested Clique model. In Section 6, we further obtain a constant-approximate APSP that runs in O(log log log n) rounds in the Congested Clique model by derandomizing the algorithm of [BCCD+24] as summarized by Theorem 1.4. The randomness in the original algorithm arises from two types of subroutines: constructing an O(log n)-approximate spanner of small size and computing hitting sets for the universe U := V and N := O(|V |) explicitly formulated sets. Here, we adapt our deterministic spanner algorithm of Theorem 1.2 and our deterministic hitting set algorithms of Theorem 1.7. Approximate shortest paths in the near-linear MPC model Theorems 1.5 and 1.6 summarize our deterministic algorithms in the near-linear MPC model. The single-source shortest paths (SSSP), multi-source shortest paths (MSSP), and all-pairs shortest paths (APSP) problems were studied in the randomized version of this model by Dory and Matar [DM24]. Their algorithm used a subroutine inspired by the Thorup–Zwick approach [TZ05]. Briefly, it begins with hierarchical sampling V = A0 ⊇ A1 ⊇ . . . ⊇ Aℓ for some suitable parameter ℓ. Then, the algorithm works in ℓ sequential iterations for each of Ai ’s. At the ith iteration, for a vertex v, it adds some weighted edges between v and other close vertices u ∈ Ai−1 . If there is a close sampled vertex u ∈ Ai reachable from v using a small number of edges, then it adds one edge between v and u. Otherwise, it adds many edges for all u ∈ Ai−1 close to v. Thus, the goal is for any vertex v, to bound the number of non-sampled vertices near v if there is no close sampled vertex from Ai near v. We formulate this goal as a hitting set problem: • Given an unweighted graph G, multiple sources Ai−1 , a weighted edge set H, a hop bound h, and a threshold d, for each vertex v, Sv ⊆ Ai−1 is defined as the O(d log n) closest 12
sources among Ai−1 to v, where distances are measured by the shortest paths using at most h edges in E(G) ∪ H. • The goal is to compute a small Ai ⊆ Ai−1 so that Ai ∩ Sv ̸= ∅ for every vertex v in G. In the original randomized algorithm [DM24], during the hierarchical sampling, Ai was sampled from Ai−1 with probability 1/d so that the expected size of Ai is at most O(|Ai−1 |/d) and the above condition holds with high probability, without explicitly formulating a hitting set problem and actually even without explicitly computing the sets Sv . In Section 6.2, we avoid the hierarchical sampling by deterministically obtaining Ai from Ai−1 at the beginning of each ith sequential iteration. Particularly, we first explicitly formulate the above hitting set problem. Note that even if the desired Sv ’s are not a subset of the neighbors of v, they are reachable using at most h edges. This property allows us to compute the sets efficiently in O(h) rounds. Then we deterministically obtain Ai from Ai−1 of size at most O(|Ai−1 |/d) in O(log log n) rounds by using Theorems 1.7 and 1.8 Part 2. This is the same as the expected size desired by the previous random process. Although deterministically computing Ai requires O(h + log log n) additional rounds per sequential iteration, this is not a bottleneck for the overall algorithm. Thus, it does not affect the final round complexity. Down the line [DM24] uses the subroutine for various choices of the parameters4 , yielding a randomized poly(log log n)-round approximate distance algorithms; due to the deterministic subroutine in our case the results become deterministic as summarized in Theorem 1.5 and Theorem 1.6.
2.3
Further Related Work
Congested Clique A linear MPC algorithm can be simulated in Congested Clique by allowing a constant time overhead [BDH18]. However, the reverse does not hold usually. This is because in the MPC model the goal is to use a total space similar to size of the input, Õ(m), where in Congested Clique there are no specific memory requirements, hence a direct simulation may use too much memory. Next, we review the distance approximation algorithms in the Congested Clique model. There are deterministic algorithms to compute a (2k−1)-spanner of size Õ(n1+1/k ) in poly (log log n) rounds or to compute an O(k)-spanner of size O(k ·n1+1/k ) in O(log k) rounds [PY18]. Additionally, there are deterministic algorithms for the approximate APSP problem [CHKKL+19; LG16; CHLT19; CDKL21; DP22], including a poly(log n)-round algorithm for weighted graphs [CDKL21] and a poly(log log n)-round algorithm for unweighted graphs [DP22]. These APSP algorithms are based on matrix multiplication and hence require large total memory, which makes them unsuitable for linear MPC. Furthermore, the current fastest algorithms are randomized, such as the O(1)-round O(k)-spanners [DFKL21; CZ22], O(1)-round O(log n)-approximation APSP [DFKL21; CZ22], and the O(log log log n)-round O(1) approximation APSP algorithms [BCCD+24]. Deterministic hitting sets in other distributed models Censor-Hillel, Parter, and Schwartzman [CPS20] use hitting set like techniques to derandomize the Baswan-Sen Spanner (and MIS) in the Congested Clique. Later, Parter and Yogev [PY18] gave an explicit deterministic hitting set algorithm in the Congested Clique. The authors apply it to compute spanners and follow up work by Censor-Hilel, Dory, Korhonen, and Leitersdord [CDKL21] use it to compute APSP. The hitting set algorithm takes O((log log n)3 ) rounds, but with newer pseudo-random generators of [GY20] this becomes O(log log n) rounds. They also have a constant construction that 4 In their full algorithm [DM24] sometimes use the subroutine by simulating ℓ = O(log log n) iterations in parallel while our method inherently requires that the ℓ iterations are performed sequentially. However, also in their algorithms the runtime bottleneck of their distance computations stems from using the subroutine sequentially for ℓ iterations. Hence, we obtain the same overall runtime.
13
leads to a hitting set of size O(n17/16 /d0.5 ). Theorem 1.7 can be seen as a generalization of their work, where 1) we need to take additional care to make sure all internal computations do not exceed the local memory, 2) our constant round algorithm achieves a sparser hitting set, and 3) our algorithms work for a wider range of parameters. Later, Dory and Parter [DP22] introduces the notion of a ‘soft’ hitting set. For their shortest path algorithm, they need a definition akin to hitting sets with slightly different properties. They dub it a soft hitting set, and provide an algorithm to compute it in the same round complexity as [PY18]. Deterministic hitting sets and their application to spanners have also been studied in the related CONGEST model [GK18; BEGG+22; GGHI+23]. This model is similar to the Congested Clique except that the nodes can only communicate with their neighbors [Pel00]. This line of work lead to a deterministic hitting set in poly log n rounds by Ghaffari, Grunau, Haeupler, Ilchi, and Rozhoň [GGHI+23], which they apply to derandomize the Baswana-Sen algorithm [BS07] to give a deterministic spanner algorithm. They perform a multi-step process to make it computationally efficient not only in the CONGEST model, but also in the PRAM model. However, such techniques do not directly translate to the MPC model; it would lead to poly log n-round algorithms, which is exponentially slower than what we aim for. Berger, Rompel, and Shor [BRS94] provide a PRAM algorithm that works also for our variant of hitting set (termed ‘balanced set cover’ in their paper). However, their algorithm is a recursive process that contains log m iterations. This leads to (at least one) factor log m in the round complexity, also in a possible MPC implementation. Agarwal and Ramachandran [AR20] compute a ‘blocking set’ in CONGEST, an object for shortest path computation that ‘hits’ many paths. The algorithm is based on an implementation of a result of the aforementioned paper [BRS94] and implementing it in MPC also would come with at least logarithmic overhead. Deterministic MPC algorithms For connectivity, there are deterministic algorithms in sublinear MPC that take O(log D + log logm/n n) rounds [CC23; FGG22]. This matches the randomized state of the art, which is conjectured to be optimal [ASSW+18; BDEL+19]. Coy and Czumaj also show how to obtain a minimum spanning tree (MST) deterministically in O(log n) rounds, matching a conditional lower bound of Ω(log n) which follows from the widelybelieved 1vs2-Cycle conjecture. In linear MPC, Nowicki [Now21] gives a deterministic O(1)round algorithm for MST, hence also solving connectivity in this regime. A substantial body of work has established deterministic MPC algorithms for fundamental symmetry-breaking problems, showing that randomness can often be eliminated without sacrificing efficiency. While problems such as maximal matching, graph coloring, and maximal independent set may appear different from distance problems, their algorithms rely on similar techniques. In particular, sparsification and the method of conditional expectation have been used extensively to obtain deterministic counterparts. Moreover, MIS and its relaxed variants, such as ruling sets, are sometimes used in distance algorithms, for example, to select cluster centers in clustering-based approaches. Czumaj, Davies, and Parter [CDP21c] give a deterministic (∆ + 1)-vertex coloring algorithm in linear MPC using O(1) rounds. In sublinear MPC, the authors gave an O(log log log n)-rounds algorithm in follow up work [CDP21b]. This matches both the randomized state of the art and a conditional lower bound for the problem [GKU19]. Next we consider maximal independent set and maximal matching. Fischer, Giliberti, and Grunau [FGG23] provide algorithms of O(log α + log log n) rounds for both problems in sublinear √ MPC, where α denotes the arboricity of the graph. The randomized state of the art is O( log α log log α + log log n) [GU19; GGJ20]. This gap is one of the motivations to look at the ruling set problem. In the linear MPC model, Giliberti and Parsaeian [GP24] give a constant round algorithm for computing 2-ruling sets, matching the randomized algorithm by Cambus, Kuhn, Pai, and 14
√ Uitto [CKPU23]. Giliberti and Parsaeian also provide a deterministic Õ( log n) algorithm in sublinear MPC, which at the cost of slightly superlinear O(m+n1+ε ) global memory is improved to O(log1/3 ∆ log log ∆ + log log n) rounds by Ji, Kothapalli, Pemmaraju, and Singh [JKPS25]. The fastest randomized algorithm for this regime takes Õ(log1/6 ∆ · log log n) rounds [KPP20]. Derandomization in MPC The algorithm of Nowicki [Now21] mentioned above provides an inherently deterministic algorithm. All other algorithms contain a derandomization step. As discussed above, some of the algorithms [CC23; FGG22] solve exactly the hitting set problem. Others [CDP21c; PP22; FGG23; GP24; JKPS25] derandomize a more problem specific sampling step. Although the methods here are similar to ours (limited independence and the method of conditional expectation), the results are specific to the algorithm at hand and do not provide general derandomization of sampling. In our algorithms, we use k-wise independence and pseudorandom generators for reducing the amount of randomness for sampling nodes. This is in the same spirit as Newman’s method [New91], a reduction from public to private randomness in communication complexity. Potentially, we can also use Newman’s method here as an alternative pseudorandom generator. However, Newman’s method would require exponential computation and certain space requirements. It is unclear whether such space requirements can be met – in particular in sublinear MPC. Relation to Set Cover For both the classic tasks of finding an approximation of the optimal set cover or optimal hitting set it is a major open problem of the field to get sublogarithmicround complexity in MPC, even using randomized algorithms. The hitting set problem in this paper is different from these classic variants and hence we even find O(1)-round algorithms; the solution is still sufficient for our applications. Different variants of these problems have also been considered in multiple works in CONGEST [AR20] and PRAM [BRS94] where the distinction between our variant and the classic optimization problem does not matter as much because it usually only affects logarithmic factors, but in our case it is crucial to solve a variant of the problem that allows O(1)-round algorithms.
Outline In Section 3, we introduce our models formally, provide MPC primitives, and summarize derandomization techniques used in our work. In Section 4, we give the full algorithms and proofs for our hitting set results. In Section 5, we present the detailed algorithms and their analysis for spanners. In Section 6, we provide the results of the deterministic algorithms for the approximate shortest paths problems, including the approximate APSP problem.
15
3
Graphs, MPC Primitives, and Derandomization
3.1
Graphs
Notation. In this paper, we consider undirected graphs G = (V, E) with n vertices and m edges. An edge is represented by an unordered pair {u, v} of vertices. We say that a vertex u is adjacent to v if {u, v} ∈ E(G), and that the edge {u, v} is incident to both u and v. When G is not clear from context, we denote the vertex set and edge set of G by V (G) and E(G), respectively, and let degG (u) be the number of edges in E(G) incident to u ∈ V (G). When we write G = (V, E, w), we refer to an edge-weighted graph with vertex set V and edge set E. The weight function w : V 2 → R is symmetric, where w(u, v) = ∞ if {u, v} ∈ / E (equivalently, w : E → R \ {∞}). Thus each edge {u, v} ∈ E has weight w(u, v) = w(v, u). If all edges have unit weight, i.e., w(u, v) = 1 for every {u, v} ∈ E, we simply write G = (V, E) and call G an unweighted graph. A path π between vertices s, t ∈ V in a graph G = (V, E, w) is a sequence of edges in E such that consecutive edges share an endpoint while the first and the last edges are incident to s and t, respectively. The length of π is the sum of the weights of edges in the path. In an unweighted graph, this equals the number of edges in the path. A path is a shortest path if no shorter path exists between s and t. Furthermore, we define the distance between two vertices in G as the length of a shortest path between them. Spanners. For an edge weighted graph G = (V, E), a subgraph H = (V, EH ) is called an α-spanner of G if for any two vertices u, v ∈ V , the distance between them in H is at most α times of the distance in G. Equivalently, it can be defined with a condition on the stretch of each edge. That means H is an α-spanner if the distance between u and v in H is at most α · w(u, v) for each edge {u, v} ∈ E, where w(u, v) is the weight of the edge {u, v} in G. It is well-known that every graph with n vertices has a (2k − 1)-spanner with O(n1+1/k ) edges, and such a spanner can be constructed by a greedy centralized algorithm with a linear space complexity [ADDJ+93]. All-pairs shortest paths problem. For an edge-weighted graph G = (V, E), the all-pairs shortest paths (APSP) problem asks to build a data structure supporting a query algorithm to return the distance between any two given vertices v, u ∈ V in G. Additionally, an αapproximate APSP problem aims to compute an α-approximate distance between two query vertices for the approximate factor α > 0. For instance, an α-spanner supports a query of α-approximate distance between any two vertices. Therefore, α-spanner immediately gives a solution for an α-approximate APSP problem. There are variations of the APSP problem by restricting the queries. For instance, by fixing one query vertex as s ∈ V , the (approximate) single-source shortest paths (SSSP) problem claims to compute the (approximate) distance between s and any other vertex v ∈ V . Additionally, for a vertex set S ⊆ V , the (approximate) multi-source shortest paths (MSSP) problem supports the (approximate) distance query between any two vertices s ∈ S and v ∈ V .
3.2
The MPC Model
In the massively parallel computation (MPC) model, the algorithm consists of a sequence of synchronous rounds using multiple N machines with local space L and the total space M = N ·L. Usually, the total space is forced to be linear (or near-linear) in the input size. During each round, the machines are isolated from each other, and work individually. The machines can communicate with each other only between rounds. In each of the communication rounds, the messages received or sent per machine cannot exceed the local space. Throughout, we assume word size O(log M ), such that the identifier of a machine can fit in one word. The communication 16
is much more expensive compared to the individual computation. Therefore, the model aims to minimize the communication, that is the number of rounds, while preserving the small local space per machine. Various regimes in the MPC graph algorithms. For the graph algorithms of an input graph G with n vertices, the MPC graph algorithm considers the local space related to the size n. For instance, the linear, the near-linear, and the sublinear regimes consider the local space L = O(n), O(n · poly(log n)), and O(nδ ), respectively, where 0 < δ < 1 is a fixed constant. The sublinear regime is the most desirable while the most challenging, since it does not allow a single machine to store information about all the vertices of the graph. For instance, the hardness has been conjectured to require at least Ω(log n) rounds in any sublinear MPC model to distinguish between a large cycle of length n and two cycles of lengths ⌊n/2⌋ and ⌈n/2⌉, called the 1-vs-2 cycles conjecture. In this aspect, the heterogeneous MPC model has been introduced [FHO25] that varies the local spaces of the machines. In this model, there is a single machine or a small number of machines with larger local space, and many machines with small local space. Even for a single machine with a near-linear local space and additional machines with sublinear local space, the heterogeneous MPC model circumvents the conditional hardness results from the sublinear regime, including the 1-vs-2 cycles problem and the approximate SSSP problem. This is why various (approximate) distance problems, including SSSP and APSP problems, have been studied in the heterogeneous MPC model [FHO25; DM24] instead of the classic sublinear MPC model.
3.3
MPC Primitives
Basic tools implemented in the MPC model. In the MPC model, several useful tools have been developed, including sorting and summation of elements. In this paper, we also utilize the algorithms as illustrated by the following lemma. Lemma 3.1 ([Goo96; GSZ11; DN19]). Sorting, filtering, and prefix sum on a sequence of M messages can be performed deterministically in O(logL M ) rounds in the MPC model using L local space and O(M ) total space. Additionally, in O(logL N ) rounds, a machine M can broadcast a constant number of messages to N consecutive machines M1 , . . . , MN , given that M has the ids of the first and last machines (M1 and MN ). Running Multiple MPC Algorithms Simultaneously. In some applications, we have multiple MPC algorithms, that run on part of the input, and need only part of the total space. Such algorithms can then we run simultaneously, where the total space becomes the sum of the space used by each algorithm. Observation 3.2. Let A1 , . . . , Ax be x MPC algorithms, where each algorithm Ai runs in Ti (n) rounds with Li (n) local space and Mi (n) total space when n input messages are given for Ai . When ni input messages are given along with the functions Li and Mi , that are labeled with index i, for each i ∈ [x], we can run all algorithms simultaneously in O(maxi {Ti (ni )} + logL M ) rounds in the MPC model with L local space and M total space if: P 1. M ≥ 6 i Mi (ni ) + 6x and 2. L ≥ maxi {Li (ni )}. Proof. During this algorithm, we suppose that we have ⌊M/L⌋ machines with L local space, and the input messages and the functions Mi ’s and Li ’s are given arbitrarily distributed across the 17
P machines. We have at most i Mi (ni ) input messages and 2x functions, while we do not know the exact value of ni . In the following, we first calculate the needed space Mi (ni ) to run Ai for each i ∈ [x]. Then we allocate the space for each algorithm, and finally, we run the algorithms. Preprocessing phase. In this phase, the goal is to count the number of input messages ni , and compute the memory Mi (ni ) needed to simulate the algorithm Ai for each i ∈ [x]. To count the input messages, we collect the distributed input messages and functions in the first half machines in O(logL M ) rounds using the sorting algorithm of Lemma 3.1. After this process, we can assume that the input messages belonging to the same algorithm Ai are stored in consecutive machines. We derive the implementation so that each machine having an input message of Ai knows the id of the first machine Mi having a message of Ai . Furthermore, the first machine Mi knows the ids of all machines having an input message of Ai . First, each machine creates a list of the indices of the algorithms for which it holds input messages. In the next two rounds, every machine sends this list to both its previous and next machines. After that, each machine M knows if it is the first machine having a message of algorithm Ai for each i ∈ [x]. For each algorithm Ai , we let Mi be the first machine that has a message of Ai . Note that the last machine that has a message of Ai is Mi+1 or its previous machine, without loss of generality, we suppose that it is Mi+1 . Note that Mi and Mi+1 are the same machine if and only if the messages of Ai are on a single machine. This is a trivial case, so we can assume that Mi ̸= Mi+1 Next, we collect the ids of every Mi in x/L consecutive machines in O(logL x) rounds by the sorting algorithm, and broadcast the id of Mi to the machines having a message of Ai , i.e, the machines between Mi and Mi+1 . This takes at most O(logL M ) rounds by Lemma 3.1. Precisely, we first send to Mi the ids of Mi+1 , only if Mi ̸= Mi+1 . Then each Mi broadcasts its ids to the machines between Mi and Mi+1 , simultaneously. It takes O(logL (M/L)) rounds by Lemma 3.1. By using the prefix sum algorithm illustrated by Lemma 3.1, we can calculate the number ni of input messages stored in the machines and send it to the machine Mi for every i ∈ [x] in O(logL M ) rounds. After that, each machine Mi calculates the total space Mi (ni ) needed for the algorithm Ai . In the following, we allocate Mi (ni ) space for each algorithm Ai . Allocating phase. In this phase, our goal is to allocate sufficient memory to all algorithms Ai . We do this by generating dummy messages. Then, we run a similar sorting and communication routine as in the previous phase, but now with not only the input messages, but also these dummy messages. To describe this in more detail, recall that, after the Preprocessing phase, the data is stored in the first half of the machines, so the last half of the machines X1 , . . . , Xℓ are empty. During this phase, we generate dummy messages in X1 , . . . , Xℓ . Then, using the same process to the Preprocessing phase, we can redistribute them along with the input messages so that for each algorithm Ai , its 2Mi (ni ) dummy messages and ni input messages are stored in consecutive machines in O(logL M ) rounds. Note that even if Ai is worked in some MPC model with Mi (ni ) total space, but we give additional marginal space for convenience. Furthermore, we can make sure that each machine that has a message of Ai knows the id of the first machine M′i that has a message of Ai . Additionally, the first machine M′i knows the ids of all machines having a message of Ai . To generate the dummy space, the first machine X1 broadcasts its id to each of the first half of the machines, that includes Mi ’s, using Lemma 3.1. Recall that Mi is the first machine having some message or functions of Ai for i ∈ [x]. This machine knows the valueP Mi (ni ). Then we use the prefix sum algorithm of Lemma 3.1 again to compute the prefix sum i−1 j=1 ·Mj (nj ). We store this value at the machine Mi for each i ∈ [x]. In the next round, all machines Mi simultaneously do the following: P Pi • Compute M(i) = 2 · i−1 j=1 Mj (nj ) + 1 and M(i + 1) = 2 · j=1 Mj (nj ) + 1, and 18
• Send the values M(i) and M(i + 1) to the machine X⌊M(i)/L⌋+1 . P Note that M(i + 1) = 2 · ij=1 Mj (nj ) + 1 = M(i) + 2Mi (ni ). Then each X⌊M(i)/L⌋+1 machines for i ∈ [x] broadcasts, simultaneously, the received values M(i) and M(i + 1) to the consecutive following machines X⌊M(i)/L⌋+2 , . . . , X⌊M(i+1)/L⌋+1 by Lemma 3.1. Finally, each machine Xj ′ generates max{L, M(i + 1) − L · (j ′ − 1)} dummy messages labeled by i for the algorithm Ai if j ′ = ⌊M(i)/L⌋ + j for some j. Note that it is possible that a single machine Xj ′ generates dummy elements for several algorithms without exceeding the local space by construction. At the termination of the process, the last half of the machines X1 , . . . , Xℓ store 2Mi (ni ) dummy messages for all algorithms {Ai }i . Using the same process to the Preprocessing phase, we can redistribute the dummy messages and the input messages in O(logL M ) rounds so that for each algorithm Ai , its 2Mi (ni ) dummy messages and ni input messages are stored in the consecutive machines. Furthermore, we can make each machine having a message of Ai know the id of the first machine M′i having a message of Ai . Additionally, the first machine M′i knows the ids of all machines having an input message of Ai along with the id of M′i+1 . Therefore, we are ready to run the algorithms Ai ’s. Running algorithms. Let M′i be the first machine storing a message belonging to the algorithm Ai . Note that M′i = M′i+1 if and only if the machine M′i stores all the messages of Ai . In such a case, we can run the algorithm Ai by using the single machine M′i by using the input messages and the memory of its dummy messages allocated to Ai . Therefore, we suppose that such algorithms Ai ’s are already simulated in O(1) rounds. In the following, we simulate the remaining algorithms Ai ’s of which M′i ̸= M′i+1 . For a fixed index i, recall that the consecutive machines N1 , . . . , NNi between M′i and M′i+1 (including M′i ) has the messages only for the algorithm Ai , where Ni = ⌈(2Mi (ni ) + ni )/L⌉ Additionally, since M′i knows the id of M′i+1 , each M′i can broadcast the ids of M′i and M′i+1 to N1 , . . . , NNi . That means that N1 , . . . , NNi know the ids of themselves that have sufficient total space to run Ai . In the following, our goal is to simulate Ai by using the consecutive Ni = ⌈(2Mi (ni ) + ni )/L⌉ machines between M′i and M′i+1 in O(Ti (ni )) rounds. This ensures that we can simultaneously run the algorithms Ai ’s in O(maxi (Ti )) rounds. To simulate the algorithm Ai , we start by removing all of the dummy messages in N1 , . . . , NNi . Note that the algorithm Ai is implemented for an MPC model with Li (n) local space and Mi (n) total space using ⌊Mi (n)/Li (n)⌋ machines. Here, each of N1 , . . . , NNi has L ≥ Li (ni ) local space. Then we split the L local space of each machine Nj forj ∈ [Ni ] into ⌈L/Li (ni )⌉ ⌊L/Li (ni )⌋ parts Nj1 , . . . , Nj each of which has Li (ni ) space by ignoring the remaining L − Li (ni ) · ⌊L/L (n )⌋
i i ⌊L/Li (ni )⌋ space. Then we can give the different ids to each parts Nj1 , . . . , Nj . Note x x that there are at least ⌊Mi (n)/Li (n)⌋ number of Nj since we define Nj for all x ∈ [Ni ] and j ∈ [⌊L/Li (ni )⌋]. Therefore, we can run the algorithm Ai within at most Ti (ni ) rounds using the machines N1 , . . . , NNi by treating Njx ’s with x ∈ [⌊L/Li (ni )⌋] and j ∈ [Ni ] like independent (at least) ⌊Mi (n)/Li (n)⌋ machines with Li (ni ) local space. This is because during the implementation of Ai , each Njx sends and receives at most Li (ni ) messages at the same time. That means each machine Nx sends and receives at most Li (ni ) · ⌊L/Li (ni )⌋ ≤ L messages at any point during the implementation. This completes the proof of the observation.
This observation allows for flexibility in how we account for the machine allocation of individual subroutines. Throughout the paper, we ensure that every algorithm respects the prescribed upper bound on the local space at all times, along with the total space. The number of machines used by a subroutine is allowed to be omitted as long as the resulting total space remains within the claimed bounds. In particular, we do not require every subroutine to be implemented using exactly O(m/n) machines; some subroutines may use more machines with smaller local space without affecting the overall guarantees, by the above observation. 19
3.4
Simulating MPC Algorithms in the Congested Clique
Using Lenzen’s routing [Len13], it is quite immediate to see that we can simulate linear MPC algorithms in the Congested Clique. For a formal proof, we refer to Behnezhad, Derakhshan, and Hajiaghayi [BDH18]. Lemma 3.3 (Theorem 3.2 in [BDH18]). Let A be an algorithm that for an input graph G, with n vertices, runs in T rounds of MPC with O(n) local memory and O(n2 ) total memory. One can simulate A in O(T ) rounds of Congested Clique.
3.5
Hash Functions for Derandomization
k-wise independence. Definition 3.4. For N, M, k ∈ N such that d ≤ N , a family of functions H = {h : [N ] → [M ]} is k-wise independent if for all distinct x1 , x2 , . . . , xk ∈ [N ], the random variables H(x1 ), . . . , H(xk ) are independent and uniformly distributed in [M ] when H is chosen randomly from H. See, e.g., [Vad12] for an explicit construction of H. Lemma 3.5 ([Vad12] Corollary 3.34). For positive integers N, M, k, there is a family of k-wise independent hash functions H = {h : [N ] → [M ]} such that choosing a random function from H takes k(log N + log M ) random bits. For k-wise independent function, we have the following tail bound. Lemma 3.6 ([BR94] Lemma 2.3). Let k ≥ 4 be an even integer. Let X1 , . . . , Xn be k-wise P independent random variables taking values in [0, 1]. Let X = ni=1 Xi denote their sum and let µ := E[X]. If µ ≥ k, then, for any ε > 0, we have P[|X − µ| ≥ εµ] ≤ 8
2k ε2 µ
k/2 .
Pseudorandom generator for hitting events. We also have the following pseudorandom generator of Gopalan and Yeudayoff [GY20], which is particularly designed for hitting events. Lemma 3.7 ([GY20] Theorem 1.9). For positive integers N and M , and for error parameter ϵ > 0, there is a family of hash functions H from [N ] to [M ] with seed length O((log log N + log(M/ε)) log log(M/ε)), such that for every subsets I1 , . . . , IN ⊆ [M ], we have: |Ph∼H [∀i ∈ [N ], h(i) ∈ Ii ] − Pg∼U [∀i ∈ [N ], g(i) ∈ Ii ]| ≤ ε, where U is the family of all functions from [N ] to [M ]. We can sample from H in polynomial time.
3.6
Derandomization in MPC
Conditional expectation method. In this paper, we utilize a hash function family H described in Lemma 3.6 or Lemma 3.7, and our goal is to find a good hash function h in H efficiently. For this, we apply the conditional expectations method, see, e.g., [MU17, Chapter 6.3]. The method iteratively restricts the hash function family so that it finally returns a desired hash function deterministically. The following lemma illustrates the method. Lemma 3.8. We are given a family H of hash functions and k objective functions f1 , . . . , fk : H → R such that: 1. The hash functions of H are encoded by s-bit random seeds, 20
2. Eh∼H [
Pk
i=1 fi (h)] ≤ x, and
3. Eh∼H [fi (h) | the prefix of h ∈ H is r ] can be computed in a single machine with L local space for any i ∈ [k] and any prefix string r ∈ {0, 1}∗ of length at most s. P There exists a deterministic MPC algorithm that computes a function h∗ ∈ H with ki=1 fi (h∗ ) ≤ x in O(s log k/ log2 L) rounds with O(L) local space and O(kL) total space. Here, we present the main ideas first, while the details are in the proof. This algorithm decomposes the random seeds into t = O(s/ log L) chunks R1 , . . . , Rt of ⌊log L⌋ bits random seeds, and iteratively determines each chunk in O(log k/ log L) rounds. At the j-th iteration, we determine the j-th chunk Rj by assuming that the prefix R1 · · · Rj−1 is fixed in the previous iterations. That means that the family of hash functions H is restricted to Hj during the previous (j − 1) iterations, and the j-th iteration receives Hj and restricts it further to Hj+1 by determining the chunk Rj . Note that there are at most L number of different assignments r1 , . . . , rL for Rj , since Rj consists of ⌊log L⌋ bits. To do this, we need k machines M 1 , . . . , M k with 2L local space. The machine M i computes the expectations of fi (h) over the hash functions h in Hj whose Rj chunk is r for all r ∈ {r1 , . . . , rL }. The machine M i can compute it locally without any communication by using L space to compute each expectation value and L space to store the computed value. Therefore, it Pkis enough to have 2L local space. Furthermore, we can compute the expectation value of i=1 fi for the prefixes r1 , . . . , rL by summation of the calculated expectation values, which takes O(log k/ log L) rounds by Lemma 3.1. Therefore, determining one chunk takes O(log k/ log L) rounds, and thus, the lemma holds.
21
4
Hitting Sets in MPC
In this section, we provide our deterministic hitting set algorithms. In particular, we prove Theorems 1.7 and 1.8. In fact, we show more general versions, where the demands on N and |U | are largely dropped. Since these results are rather technical, and we mostly do not need them for our applications, we defer the statements to their respective technical sections. Here, we restate the simpler version Theorems 1.7 and 1.8 for convenience. We split our results into two sections: ‘linear MPC’ and ‘sublinear MPC’. We note that these descriptions are with respect to the hitting set problem itself and do not always coincide with the application. To be precise, let the hitting set instance consist of N sets S1 , . . . , SN , where |Si | ≥ d. Let the local memory be denoted by L. If L = Ω(d), then we call the instance ‘linear’: a set Si fits on one machine. Note that we do not set L = Θ(d), but allow for (much) bigger L as well. As we will demonstrate, such additional space can have additional running time advantages in the derandomization process. If L < d, we call the instance ‘sublinear’. In this case, we will always assume L = O(dδ ) for some constant δ ∈ (0, 1) – analogous to the sublinear MPC model for graph problems: here we have O(nδ ) for some constant δ ∈ (0, 1), where n = |V | denotes the number of vertices. Now suppose we are faced with a hitting set problem in the context of graphs. If this is linear MPC, i.e., Θ(n) local space, we will also use the ‘linear MPC’ hitting set. If this in sublinear MPC, i.e., Θ(nδ ) local space, it depends on the hitting set instance which hitting set we use: if d < nδ , we can use the ‘linear MPC’ hitting set. If d ≥ nδ , we use the ‘sublinear MPC’ hitting set. When presenting the theorems below, we detail which version is used for each of the applications in Sections 5 and 6. Note that in each of these cases, we have that |U |, N = O(n), and that the local space L is at least Ω(dδ ) when we apply a hitting set. This means that we always have |U |, N = poly L, as required by Theorems 1.7 and 1.8. If we do not have this assumption, we obtain results with additional factors logL |U | and logL N , see Sections 4.2 and 4.3. Linear MPC Hitting Sets. Theorem 1.7. Let L be the parameter denoting the local space. There is a deterministic MPC algorithm that, given a universe U , a number d ≤ min{|U |, L} and a collection of N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ], that computes a hitting set: | 1. of size O d|U in O(1) rounds; or 0.99 2. of size O
|U | log d d
in O(log log d) rounds.
P Both algorithms assume N ≤ |U | = poly L and use linear total space: O L + |U | + N |S | . i i=1 Proof. We prove part 1 in Lemma 4.3 (Section 4.2.1), part 2 in Lemma 4.8 (Section 4.2.3). The results as stated here follow from these two lemmas by setting |U |, N = poly L. Additionally, we show in Sections 4.2.2 and 4.2.4 that we can drop the N ≤ |U | demand, i.e., we can also deal with the case thatthe number of sets is very large. For part 1, if N = poly L, |U | logd N we obtain a hitting set of size O in O(logd N ) rounds. See Lemma 4.6 for the d0.99 N formal statement. For part 2, if N = poly L, we obtain a hitting set of size O |U | log in d O(log log(d + N )) rounds. See Lemma 4.11 for the formal statement. Theorem 1.7 Part 1 is used in our spanner in linear MPC (Section 5.1), our spanner in sublinear MPC Section 5.3, and APSP in the Congested Clique (Section 6.1). Theorem 1.7 Part 2 is used in APSP in the Congested Clique Section 6.1. Lemma 4.11 is used in APSP in the near-linear regime (Section 6.2). 22
Sublinear MPC Hitting Sets. Next, we consider the ‘sublinear’ regime. In this case, we have relatively large d. In particular, d is larger than the local space, which is here denoted as O(dδ ) for some constant δ ∈ (0, 1). Theorem 1.8. Let δ ≤ 1 be a positive constant. There is a deterministic MPC algorithm that, given a universe U , a number d ≤ |U | and a collection of N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ], that computes a hitting set: |U | log d 1. of size O d0.99 in O(1) rounds; or 2. of size O
|U | log d d
in O(log log d) rounds with O(dδ ) local space.
Both algorithms assume |U |, N = poly d, use O(dδ ) local space, and use linear total space: PN O(|U | + i=1 |Si |). Proof. We prove part 1 in Lemma 4.18 (Section 4.3.2) and part 2 in Lemma 4.21 (Section 4.3.3). The results as stated here follow from these two lemmas by setting |U |, N = poly d. Theorem 1.8 Part 1 is used in our spanner in sublinear MPC (Section 5.3). Theorem 1.8 Part 2 is used in APSP in the heterogeneous regime (Section 6.2).
4.1
Preprocessing
The given input for a hitting set problem is as follows: a universe U , a number d ≤ |U | and collection of N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ]. This input might be larger than necessary in two ways: 1) Some sets Si might be much larger than d. Although this can only be helpful, our algorithm (and its randomized predecessor) do not exploit this. Hence, we can discard any such elements and prune each Si to have size exactly |Si | = d. 2) The set U might contain elements that are in none of the (pruned sets) Si . Such elements never have to be part of the hitting set, and hence can be discarded. A pruned set U should have size O(N d) at most. The following preprocessing lemma formalizes this pruning procedure. Lemma 4.1. Let L be a parameter. There exists a deterministic MPC algorithm that, given a universe U , a number d ≤ |U | and collection PNof N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ] and total input size M := |U | + i=1 |Si |, outputs a universe Ũ and a collection of N subsets S̃1 , . . . , S̃N ⊆ U , such that |Ũ | ≤ N d, and for each i ∈ [N ] S̃i ⊆ Si and |S̃i | = d. The algorithm takes O(logL M ) rounds, and uses O(L) local space and O(M ) total space. We can assume that the new instance is structured as follow: • U is stored on O(N d/L) consecutive machines. • If L ≥ d, each set Si is stored within one machine (with possibly multiple sets in the same machine). • If L < d, the sets Si are stored on multiple, consecutive machines (where each machine contains a subset of Si for exactly one index i). Proof. First, we prune the sets Si : Whenever a set Si is larger than d, we want to omit further elements. Hereto, we sort all elements using Lemma 3.1 to each set Si on consecutive machines. We can count the elements in each set Si simultaneously again using Lemma 3.1 and make this value known to all relevant machines. Then we delete the largest (in the ordering) |Si | − d elements for set Si locally. We can perform this for all sets Si simulatneously due to Observation 3.2. Afterwards, we sort again to structure the output as required. This takes O(M ) space and O(logL M ) rounds. 23
Next, we prune the set U : In another O(logL M ) rounds and with O(M ) space, weScheck which elements of U appear in any set Si . This is done by sorting the tuples {(u, 1) : u ∈ i Si } and {(u, 0) : u ∈ U }, using Lemma 3.1. When an element (u, 0) does not neighbor any elements (u, 1), it is deleted. Then, we sort once more to store the remaining elements (u, 0) on O(N d/L) consecutive machines. Furthermore, we can assume that d is bounded away from |U |. A technicality needed to apply Lemma 3.6. Remark 4.2. Without loss of generality, we can assume that d ≤ |U |/200 when computing a |U | hitting set of size O d0.99 . Proof. If |U |/211 < d ≤ |U |. We can set d′ = |U |/211. Clearly |Si | ≥ d ≥ d′ . This instance |U | ′ ≤ provides a hitting set parametrized by d , which produces a hitting set of size O d′0.99 | | = O d|U 2110.99 · O d|U 0.99 0.99 .
4.2
Linear MPC
For the linear MPC hitting set problem, we provide four algorithms, outputting a hitting set of N 0.99 ), O(|U | log d/d + N/d), and O(|U | log N/d) respectsize O(|U |/d0.99 + N/d), O(|U | logd |U | /d fully. We note that for the first two results, in Theorem 1.7 we assumed that N ≤ |U |, which means the latter term is absorbed in the first. For full generality, we drop this requirement in this section. In our applications, we either have N ≤ |U | or we use the third result. 4.2.1
Fast Hitting Sets
The goal of this section is to prove the following lemma. This lemma computes a hitting set that is of size O(|U |/d0.99 + N/d). This is roughly a factor d0.01 larger than our other hitting sets. However, this allows us to use hash functions with a very small seed. This translates in a low round complexity: for |U |, N = O(poly d) it only takes a constant number of rounds. Lemma 4.3. There exists a deterministic MPC algorithm that, given a universe U , a number d ≤ |U |, and a collection of N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ], computes 0.99 + N/d). Let L ≥ d denote the local space of each machine, a hitting set D of size O(|U PN|/d and let M := L + |U | + i=1 |Si |. Then the algorithm takes O(log2L N + logL M ) rounds and O(M ) total space. The main idea is to derandomize random sampling. The simplest such version is given in the following algorithm. Algorithm 1 Constructing an (incomplete) hitting set D with random sampling 1: D ← ∅ 2: for all u ∈ U do 3:
Add u to D with probability p = 1/d0.99 return D
However, this does not necessarily give a hitting set: Consider some set Si of size d. The probability that none of the elements of Si are sampled is 0.01
(1 − p)|Si | = (1 − d−0.99 )d ≤ e−d
.
This means that for small d (d ≤ Θ(log N )), we do not obtain a result with high probability. There are two possible solutions: (i) increase the sampling probability, or (ii) add additional 24
elements to D. Solution (i) will be explored in Section 4.2.4. Here, we consider Solution (ii). The random algorithm becomes a two phase process, see Algorithm 2: first we add elements to D by random sampling, then we add an element to D for each set Si that is not hit by the first part. Algorithm 2 Constructing a hitting set D with independent random sampling 1: D ← ∅ 2: for all u ∈ U do
Add u to D with probability p = 1/d0.99 4: for i = 1 to N in parallel do 5: if Si ∩ D = ∅ then 6: Add an arbitrary element of Si to D return D 3:
Now the set D is guaranteed to be a hitting set. However, its size becomes less obvious. In Algorithm 1, the expected size of D = O(|U |/d0.99 ) by linearity of expectation. In Algorithm 2, we have a contribution of O(|U |/d0.99 ) from the first phase and a contribution from the second 0.01 phase. The contribution of the second phase is O(N/ed ). Of course, our goal is to provide a deterministic algorithm. Our approach has two ingredients: 1) we reduce the randomness by using O(1)-wise independent hash functions, and 2) we deterministically choose the (short) ‘random’ seed of this hash function using the method of conditional expectation. The fact that we only have O(1)-wise independence rather than full independence will change our probability analysis. We show that we can still bound the contribution of the second phase by O(N/d). Ingredient 1: Reducing randomness via O(1)-wise independent hash functions. We let H be a family of 200-wise independent hash functions h : U → [⌈d0.99 ⌉]. Each hash function h corresponds to two sets of elements Dh , Dh′ ⊆ U . Dh corresponds to the elements sampled directly in Algorithm 2. Dh′ covers all remaining sets Si , it corresponds to the elements added in the second phase of Algorithm 2. In the case of the hitting set being a dominating set in the graph, you can think of this as a node selecting itself, because non of its neighbors are in the dominating set. In this general setting, we need to select an arbitrary element of Si , for each i that has Si ∩ Dh = ∅. Formally, we define Dh and Dh′ as: Dh := {u ∈ U | h(u) = 1}, and Dh′ := {Si [1] : Si ∩ Dh = ∅, i ∈ [N ]}, where Si [1] denotes the first (lexicographically ordered) element of Si . Note that now D := Dh ∪ Dh′ is a hitting set of S1 , . . . , SN . We denote h ∼ H for taking a hash function h ∈ H according to the corresponding contribution. For each of the hash functions in this paper, h ∼ H means we take h ∈ H uniformly at random. By the following claim, the expectation of such a sampled hash function h ∼ H corresponds to a hitting set of the desired size. Claim 4.4. Let H be a family of 200-wise independent hash functions h : U → [⌈d0.99 ⌉]. For h ∼ H, the expected size of Dh and Dh′ are O(|U |/d0.99 ) and O(N/d), respectively. Proof. We first show that the expected size of Dh equals |U |/d0.99 . For an element u ∈ U , we let Xu be the random variable such that Xu = 1 if h(u) P= 1, otherwise Xu = 0. Then the expected size ofP Dh over H is same as the expectation of u∈U Xu . By the linearity of expectations, Eh∼H [ u∈U Xu ] equals |U |/d0.99 , which implies the first claim. In the following, we bound the expected size of Dh′ .
25
We fix an index i ∈ [N ], and we bound the probability that it contributed to Dh′ , i.e., Si ∩ Dh = ∅. Since the Xu ’s are 200-wise independent random variables, Lemma 3.6 implies the following bound: X X Ph∼H [Si ∩ Dh = ∅] = Ph∼H Xu = 0 ≤ Ph∼H Xu − µ ≥ µ u∈Si
u∈Si
≤8
2 · 200 µ
200/2
≤O
1 µ100
1 ≤O , d
(2)
P 0.01 by the linearity of expectations. To apply Lemma 3.6, we also where µ := E u∈Si Xu ≥ d need to satisfy µ ≤ k. Since µ = |U |/d0.99 and we can assume that d ≤ |U |/211 by Remark 4.2, we see that µ ≥ |U |/(|U |/211)0.99 = 2110.99 > 200. For each i ∈ [N ], we let Yi be the indicator random variable for the event that Si ∩ Dh = ∅. Then Eh∼H [Yi ] ≤ O(1/d) by Inequality 2. Therefore, the expected size of Dh′ is at most O(N/d) by the linearity of expectations, which completes the proof. Ingredient 2: Derandomization via the method of conditional expectation. To deterministically obtain a good O(1)-wise independent hash function, we use the method of conditional expectation, Lemma 3.8. We know that the 200-wise independent hash functions from h : [|U |] → [⌈d0.99 ⌉] need 200(log |U | + log⌈d0.99 ⌉) = O(log |U |) random bits by Lemma 3.5. Next, we define objective functions that correspond to the expectations of the previous paragraph. We are describing the sizes of Dh and Dh′ using objective functions. For each of these, we define its own set of objective functions, fi and gi , respectively. In total, we have k = |U |/L + O(N d/L) functions. First, consider the elements of U stored on |U |/L machines. Let f1 , . . . f|U |/L denote the number of sampled elements on each such machine, i.e., if Ui denotes the elements stored on machine i, then fi (h) = |{u : h(u) = 1}|. Hence, we can write the size of the sampled elements P|U |/L as Dh = i=1 fi (h). Second, the N sets S1 , . . . SN are stored on O(N d/L) machines M1 , . . . , MO(N d/L) so that no two machines store elements from the same set Si . On each such machine Mi let gi denote how many sets Sj stored in Mi have Sj ∩ Dh = ∅, i.e., if S L , . . . SL are stored on machine i, d (i−1) d i−1 L then gi (h) = j ∈ d (i − 1), Ld i : Sj ∩ Dh = ∅ . Hence, we can write the size of the elements PO(N d/L) gi (h). from the second phase as Dh′ = i=1 Claim 4.5. The values Eh∼H [fi (h) | the prefix of h ∈ H is r ] and Eh∼H [gi (h) | the prefix of h ∈ H is r ] can be computed in a single machine with L local space, for any i where fi or gi is defined and any r ∈ {0, 1}∗ . Proof. The function fi (h) denotes how many elements of U on machine Mi are sampled. For a fixed h : U → [⌈1/p⌉], the machine can check internally which elements are sampled (encoded by h(u) = 1)), by counting this for every possible h ∈ H with prefix r, and dividing out by the total number of such h, we obtain Eh∼H [fi (h) | the prefix of h ∈ H is r ]. Note that since we only consider one function h at the time, and we can consider O(L) elements of U , we require only L local space. The function gi (h) denotes how many sets Sj stored on machine Mi satisfy Sj ∩ Dh = ∅. Again, for fixed h we can compute this value. For each set Sj , we see if h(u) = 1 for at least one u ∈ Sj . If not, it contributed to gi (h). As before, Mi sums the values gi (h) for every possible h ∈ H with prefix r and divides out by the total number of such h to obtain Eh∼H [gi (h) | the prefix of h ∈ H is r ]. Note that since we only consider one function h at the time, and we can consider O(L) elements of U , we require only L local space. 26
Putting everything together. Finally, we use the notation and results obtained above to prove Lemma 4.3. Proof of Lemma 4.3. First, we use Lemma 4.1 to reduce the size of the data we work with to O(N d) in O(logL M ) rounds. This also ensures that |U | ≤ N d and U is stored on O(N d/L) consecutive machines and each set Si is stored within one machine (with ⌊L/d⌋ such sets in the same machine). We set s = O(log |U |) and k = |U |/L + O(N d/L). Then we see that: 1. The hash functions of H are encoded by s-bit random seeds by Lemma 3.5; hP i PO(N d/L) |U |/L 2. Eh∼H gi (h) ≤ O(|U |/d0.99 + N/d) by Claim 4.4; i=1 fi (h) + i=1 3. The expectation of each objective function fi and gi can be computed in a single machine with L local space for any prefix r ∈ {0, 1}∗ by Claim 4.5. This means we satisfy the demands of Lemma 3.8. It then follows that we can compute a hitting set D of size O(|U |/d0.99 + N/d) in O(s log k/ log2 L) = O(log |U | log(|U |/L + N d/L)/ log2 L) = O(log2L N ) rounds, using that |U | = O(N d) and d ≤ L. 4.2.2
Fast Hitting Sets for large N
In the previous section, we noted that for small d (d ≤ Θ(log N )), sampling with probability 1/d0.99 does not give with high probability results. We overcame this by adding additional N 0.99 , elements. Alternatively, we can increase the sampling probability to p = 400·(1+logd |U | )/d which gives the following results. Lemma 4.6. There exists a deterministic MPC algorithm that, given a universe U , a number d ≤ |U |, and a collection of N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ], computes N 0.99 ). Let L ≥ d denote the local space of each machine, a hitting set D of size O(|U | logd |U | /d P 2 N and let M := L + |U | + N i=1 |Si |. Then the algorithm takes O(logd |U | · logL N + logL M ) rounds and O(M ) total space. The proof is analogous to Lemma 4.3, with only the probability increased. We follow the same notation, and proving the adaptations. N Ingredient 1: Reducing randomness via O logd |U | -wise independent hash functions. First, we need a new version of Claim 4.4, giving the expected size of the dominating set using the increased sampling probability. N Claim 4.7. Let H be a family of 200 1 + logd |U | -wise independent hash functions h : U → N N ′ 0.99 ) [⌈d0.99 /(400 · logd |U | )⌉]. For h ∼ H, the expected size of Dh and Dh are O(|U | logd |U | /d and O(|U |/d), respectively. N 0.99 . For an Proof. We first show that the expected size of Dh equals 400 · |U | · (1 + logd |U | )/d element u ∈ U , we let Xu be the random variable such that Xu = 1 if h(u) P = 1, otherwise Xu = 0. Then the expected size of Dh over H is same as the expectation of u∈U Xu . By the P N 0.99 , which implies linearity of expectations, Eh∼H [ u∈U Xu ] equals 400 · |U | · 1 + logd |U | /d
the first claim. In the following, we bound the expected size of Dh′ . We fix an index i ∈ [N ], and we bound the probability that it contributed to Dh′ , i.e., N Si ∩ Dh = ∅. Since the Xu ’s are 200(1 + logd |U | )-wise independent random variables, Lemma 3.6
27
implies the following bound: Ph∼H [Si ∩ Dh = ∅] = Ph∼H
X
Xu = 0 ≤ Ph∼H
u∈Si
X
Xu − µ ≥ µ
u∈Si
!200/2· 1+logd N
≤8
N 2 · 200 · (1 + logd |U |)
|U |
(3)
µ !200/2· 1+logd N
≤8
N 2 · 200 · (1 + logd |U |) N 400 · (1 + logd |U | ) · d0.01
|U |
(4) ≤O
|U | Nd
,
(5)
N 0.01 by the linearity of expectations. To apply X ≥ 400 · 1 + log d |U | · d u∈Si u N 0.99 ≥ Lemma 3.6, we also need to satisfy µ ≤ k, which holds since µ = 400 · |U | · 1 + logd |U | /d N 200 · 1 + logd |U | . For each i ∈ [N ], we let Yi be the indicator random variable for the event that Si ∩ Dh = ∅. Then Eh∼H [Yi ] ≤ O(1/N ) by Inequality 5. Therefore, the expected size of Dh′ is at most O(|U |/d) by the linearity of expectations, which completes the proof. where µ := E
P
Ingredient 2: Derandomization via the method of conditional expectation. We use the method of conditional expectation as in Section 4.2.1. In particular, Claim 4.5 holds since we are in the same setting. N 0.99 /(400· We know that the 200 1 + logd |U | -wise independent hash functions from h : [|U |] → [⌈d N N 0.99 ⌉) = O(log N ·log |U |) random bits 1 + logd |U d |U | | )⌉] need 200· 1 + logd |U | (log |U |+log⌈d by Lemma 3.5. Putting everything together. Now, we use the notation and results obtained above to prove Lemma 4.6. Proof of Lemma 4.6. First, we use Lemma 4.1 to reduce the size of the data we work with to O(N d) in O(logL M ) rounds. This also ensures that |U | ≤ N d and U is stored on O(N d/L) consecutive machines and each set Si is stored within one machine (with ⌊L/d⌋ such sets in the same machine). N We set s = O(logd |U | · log |U |) and k = |U |/L + O(N d/L). Then we see that: 1. The hash functions of H are encoded by s-bit random seeds by Lemma 3.5; hP i PO(N d/L) |U |/L N 0.99 ) by Claim 4.7; 2. Eh∼H f (h) + g (h) ≤ O(|U | logd |U i i i=1 i=1 | /d 3. The expectation of each objective function fi and gi can be computed in a single machine with L local space for any prefix r ∈ {0, 1}∗ by Claim 4.5. This means we satisfy the demands of Lemma 3.8. It then follows that we can compute a N 0.99 ) in O(s log k/ log2 L) = O(log N · log |U | log(|U |/L + hitting set D of size O(|U | logd |U d |U | | /d 2 N N d/L)/ log2 L) = O(logd |U | · logL N ) rounds, using that |U | = O(N d) and d ≤ L.
28
4.2.3
Hitting Sets of Size O
|U | log d + N/d d
In the following two sections, we obtain a smaller-sized hitting set by relaxing the round complexity. First, we obtain a version that is efficient for “small” N , i.e., N = O(|U |). If N is larger, we obtain a similar result in Section 4.2.4 at the cost of a factor log N instead of a factor log d in the size. The result of this section is summarized in the following lemma. Lemma 4.8. There exists a deterministic MPC algorithm that, given a universe U , a number d ≤ |U |, and a collection of N subsets S 1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ], computes a |U | log d hitting set D of size O + N/d . Let L ≥ d denote the local space of each machine, and d PN let M := L + |U | + i=1 |Si |. Then the algorithm takes O(log log d · logL log N · logL N + logL M ) rounds and O(M ) total space. The algorithm is analogous to the algorithm in the proof of Theorem 4.3. Instead of derandomizing random sampling with p = 1/d0.99 , we derandomize sampling with probability p = 2 · log d/d. Furthermore, we use Lemma 3.7 instead of O(1)-wise independence, which gives a family of hash functions that approximates random sampling. This has been done before by, e.g., [BEGG+22, Appendix B]. Reducing randomness via pseudorandom generators. We consider the random process where each element u ∈ U adds itself to a hitting set D with probability p = 2 log d/d. We show how to obtain this random process with a family H of hash functions h : U → [⌈1/p⌉] from Lemma 3.7 with ε = d−c for some sufficiently large constant c. Analogous to Lemma 4.3, each hash function h ∈ H corresponds to two element sets Dh := {u ∈ U | h(u) = 1}, and Dh′ := {Si [1] : Si ∩ Dh = ∅, i ∈ [N ]}, where Si [1] denotes the first (lexicographically ordered) element of Si . Claim 4.9. For h ∼ H, the expected size of Dh and Dh′ are O(|U | log d/d) and O(N/d), respectively. Proof. In the following, we bound the probability of u ∈ Dh for an element u ∈ U and the probability that Si ∩ Dh′ = ∅ for an index i ∈ [N ] and thus Si [1] ∈ Dh′ . The hash functions in H map each element to integers in [⌈1/p⌉] according to Lemma 3.7. Furthermore, an element u ∈ U is in Dh if and only if h(u) = 1. Therefore, for an element u ∈ U , the probability of u ∈ Dh can be bound by Lemma 3.7 as follows: Ph∼H [u ∈ Dh ] = Ph∼H [h(u) ∈ {1} while h(v) ∈ [⌈1/p⌉] for all v ∈ U \ {u}] ≤ Pg∼U [g(u) ∈ {1} while g(v) ∈ [⌈1/p⌉] for all v ∈ U \ {u}] + ε log d = Pg∼U [g(u) = 1] ≤ p + ε = O , d where U denotes all mapping of U → [⌈1/p⌉]. So Eh∼H [|Dh |] ≤ |U |(p + ε) = O( |U | dlog d ). In the following, we bound the probability that i ∈ [N ] contributed to Dh′ , i.e., that Si ∩Dh′ = ∅. First of all, we consider all mappings U and bound the probability Si ∩ Sg′ = ∅ for g ∼ U. That means every element u ∈ Si satisfies g(u) ̸= 1. Therefore, the probability is bounded as follows: Pg∼U [Si ∩ Sg′ = ∅] = Pg∼U [g(u) ∈ [2, ⌈1/p⌉] for u ∈ Si while g(u′ ) ∈ [⌈1/p⌉] for u′ ∈ U \ Si ] = Pg∼U [g(u) ∈ [2, ⌈1/p⌉] for u ∈ Si ] |Si | 1 ≤ 1 − ⌈1/p⌉ ≤ (1 − p/2)d . 29
Lemma 3.7 gives that two probabilities Ph∼H [Si ∩ Dh′ = ∅] and Pg∼U [Si ∩ Sg′ = ∅] are at most ε = d−c apart. Which means that with high probability, using the hash functions suffices. Ph∼H [Si ∩ Sg′ = ∅] ≤ (1 − p/2)d + ε ≤ (1 − logd d )d + d−c ≤ d1 + d−c . So the expected size of Dh′ is Eh∼H [|Dh′ |] = O(N/d). In conclusion, we have that Eh∼H [|Dh ∪ Dh′ |] = O
|U | log d + N/d d
.
Derandomization via the method of conditional expectation. Next, we show that by Lemma 3.8, we can find a proper hash function deterministically. Hereto, we define the objective functions as before. First, consider the elements of U stored on |U |/L machines. Let f1 , . . . f|U |/L denote the number of sampled elements on each such machine. Hence, we can write the size of the sampled P|U |/L elements as Dh = i=1 fi (h). Second, the N sets S1 , . . . SN are stored on O(N d/L) machines M1 , . . . , MO(N d/L) so that no two machines store elements from the same set Si . On each such machine Mi let gi denote how many sets Sj stored in Mi have Sj ∩ Dh = ∅. Hence, we can write the size of the elements PO(N d/L) from the second phase as Dh′ = i=1 gi (h). Claim 4.10. The values Eh∼H [fi (h) | the prefix of h ∈ H is r ] and Eh∼H [gi (h) | the prefix of h ∈ H is r ] can be computed in a single machine with L local space, for any i where fi or gi is defined and any r ∈ {0, 1}∗ . Proof. As fi and gi are defined as in Claim 4.5, the proof of Claim 4.5 holds again. Putting everything together. Finally, we use the notation and results obtained above to prove Lemma 4.8. Proof of Lemma 4.8. Again, we start by applying Lemma 4.1 to reduce the size of the data we work with to O(N d) in O(logL M ) rounds. This also ensures that U is stored on O(N d/L) consecutive machines and each set Si is stored within one machine (with ⌊L/d⌋ such sets in the same machine). We set s = O((log log |U | + log d) log log d) and k = |U |/L + O(N d/L). Then we see that: 1. The hash functions of H are encoded by s-bit random seeds by Lemma 3.7; P|U |/L PO(N d/L) 2. Eh∼H [ i=1 fi (h) + i=1 gi (h)] = O |U | dlog d + N/d by Claim 4.9; 3. The expectation of each objective function fi and gi can be computed in a single machine with L local space for any prefix r ∈ {0, 1}∗ by Claim 4.10. This the demands of Lemma 3.8, hence we can compute a hitting set D of means we satisfy |U | log d size O + N/d in O(s log k/ log2 L) = O((log log |U | + log d) log log d · log N/ log2 L) = d O(log log d · logL log N · logL N ) rounds, where we use that |U | = O(N d) and d ≤ L. 4.2.4
Hitting Sets of Size O
|U | log N d
In this section, we obtain a similar hitting set as in Section 4.2.3, with the main difference that we do not have the additive factor +N/d. This comes at the cost at a slightly higher sampling probability, that replaces log d by log N . The result is as follows.
30
Lemma 4.11. There exists a deterministic MPC algorithm that, given a universe U , a number d ≤ |U |, and a collection of N subsets S1 , . . . , SN ⊆ U with |Si | ≥ d for each i ∈ [N ], computes |U | log N a hitting set D of size O . Let L ≥ d denote the local space of each machine, and let d PN M := L + |U | + i=1 |Si |. Then the algorithm takes O(log log(d + N ) · (logL N )2 + logL M ) rounds and O(M ) total space. The algorithm is analogous to the algorithm in the proof of Lemma 4.8. Instead of derandomizing random sampling with p = 2 · log d/d, we derandomize sampling with probability p = 2 · log N/d. Reducing randomness via pseudorandom generators. Now, we consider the random process where each element u ∈ U adds itself to a hitting set D with probability p = 2 log N/d. We show how to obtain this random process with a family H of hash functions h : U → [⌈1/p⌉] from Lemma 3.7 with ε = (d + N )−c for some sufficiently large constant c. Analogous to Lemma 4.8, each hash function h ∈ H corresponds to two element sets Dh := {u ∈ U | h(u) = 1} and Dh′ := {Si [1] : Si ∩Dh = ∅, i ∈ [N ]}, where Si [1] denotes the first (lexicographically ordered) element of Si . However, our goal is now to make Dh′ much smaller. Claim 4.12. For h ∼ H, the expected size of Dh and Dh′ are O(|U | log N/d) and O(1), respectively. Proof. In the following, we bound the probability of u ∈ Dh for an element u ∈ U and the probability that Si ∩ Dh′ = ∅ for an index i ∈ [N ] and thus Si [1] ∈ Dh′ . The hash functions in H map each element to integers in [⌈1/p⌉] according to Lemma 3.7. Furthermore, an element u ∈ U is in Dh if and only if h(u) = 1. Therefore, for an element u ∈ U , the probability of u ∈ Dh can be bound by Lemma 3.7 as follows: Ph∼H [u ∈ Dh ] = Ph∼H [h(u) ∈ {1} while h(v) ∈ [⌈1/p⌉] for all v ∈ U \ {u}] ≤ Pg∼U [g(u) ∈ {1} while g(v) ∈ [⌈1/p⌉] for all v ∈ U \ {u}] + ε log N = Pg∼U [g(u) = 1] ≤ p + ε = O , d N where U denotes all mapping of U → [⌈1/p⌉]. So Eh∼H [|Dh |] ≤ |U |(p + ε) = O( |U | log ). d ′ In the following, we bound the probability that i ∈ [N ] contributed to Dh , i.e., that Si ∩Dh′ = ∅. First of all, we consider all mappings U and bound the probability Si ∩ Sg′ = ∅ for g ∼ U. That means every element u ∈ Si satisfies g(u) ̸= 1. Therefore, the probability is bounded as follows:
Pg∼U [Si ∩ Sg′ = ∅] = Pg∼U [g(u) ∈ [2, ⌈1/p⌉] for u ∈ Si while g(u′ ) ∈ [⌈1/p⌉] for u′ ∈ U \ Si ] = Pg∼U [g(u) ∈ [2, ⌈1/p⌉] for u ∈ Si ] |Si | 1 ≤ 1 − ⌈1/p⌉ ≤ (1 − p/2)d . Lemma 3.7 gives that two probabilities Ph∼H [Si ∩ Dh′ = ∅] and Pg∼U [Si ∩ Sg′ = ∅] are at most ε = (d + N )−c apart. Which means that with high probability, using the hash functions suffices. Ph∼H [Si ∩ Sg′ = ∅] ≤ (1 − p/2)d + ε ≤ (1 − logdN )d + d−c ≤ N1 + (d + N )−c . So the expected size of Dh′ is Eh∼H [|Dh′ |] = O(N/N ) = O(1).
31
Derandomization via the method of conditional expectation. Next, we show that by Lemma 3.8, we can find a proper hash function deterministically. Hereto, we define the objective functions as before. First, consider the elements of U stored on |U |/L machines. Let f1 , . . . f|U |/L denote the number of sampled elements on each such machine. Hence, we can write the size of the sampled P|U |/L elements as Dh = i=1 fi (h). Second, the N sets S1 , . . . SN are stored on O(N d/L) machines M1 , . . . , MO(N d/L) so that no two machines store elements from the same set Si . On each such machine Mi let gi denote how many sets Sj stored in Mi have Sj ∩ Dh = ∅. Hence, we can write the size of the elements PO(N d/L) from the second phase as Dh′ = i=1 gi (h). Claim 4.13. The values Eh∼H [fi (h) | the prefix of h ∈ H is r ] and Eh∼H [gi (h) | the prefix of h ∈ H is r ] can be computed in a single machine with L local space, for any i where fi or gi is defined and any r ∈ {0, 1}∗ . Proof. As fi and gi are defined as in Claim 4.5, the proof of Claim 4.5 holds again. Putting everything together. Finally, we use the notation and results obtained above to prove Lemma 4.11. Proof of Lemma 4.11. Again, we start by applying Lemma 4.1 to reduce the size of the data we work with to O(N d) in O(logL M ) rounds. This also ensures that U is stored on O(N d/L) consecutive machines and each set Si is stored within one machine (with ⌊L/d⌋ such sets in the same machine). We set s = O((log log |U | + log(d + N )) log log(d + N )) and k = |U |/L + O(N d/L). Then we see that: 1. The hash functions of H are encoded by s-bit random seeds by Lemma 3.7; P|U |/L PO(N d/L) N 2. Eh∼H [ i=1 fi (h) + i=1 gi (h)] = O |U | log by Claim 4.12; d 3. The expectation of each objective function fi and gi can be computed in a single machine with L local space for any prefix r ∈ {0, 1}∗ by Claim 4.13. This means the demands of Lemma 3.8, hence we can compute a hitting set we satisfy |U | log N D of size O in O(s log k/ log2 L) = O((log log |U | + log(d + N )) log log(d + N ) · d log N/ log2 L) = O(log log(d + N ) · logL N · logL N ) rounds, where we use that |U | = O(N d) and d ≤ L.
32
4.3
Sublinear MPC
In this section, we modify the algorithms of Section 4.2 for the sublinear MPC model with O(dδ ) local space for some constant δ ∈ (0, 1). Here, we must address several technical subtleties, since we cannot fit a set Si fits in a single machine: dδ < d for δ < 1. Note that this also means, that (after sorting) a machine never contains elements from multiple sets Si . We first design a sparsification tool in Section 4.3.1, that reduces the universe to a smaller set U ′ that 1) still contains a hitting set 2) Si ∩ U ′ fits on a single machine. Then, we apply this to get hitting sets of size O(|U | log N/d0.99 ) and O(|U | log N/d) in Sections 4.3.2 and 4.3.3 respectfully. δ/4 Throughout, we assume that logd N ≤ dδ/4 , or equivalently N < dd . When N = poly d, this is automatically satisfied. 4.3.1
Sparsification Tool
The goal of this subsection is to give a routine that does some initial, crude sampling, such that the remaining sets fit in in one machine. Lemma 4.14. Let δ > 0 be a constant. There exists a deterministic MPC algorithm that, given δ/4 a universe U , a number d ≤ |U | and collection of N < dd subsets S1 , . . . , SN ⊆ U with |Si | ≥ d ′ ′ 1−δ ′| = for each i ∈ [N ], computes a sparsified instance PNU ⊆ U such that |U | = O(|U |/d ), |Si ∩U 2 δ ′ δ O(d ) and |Si ∩ U | ≥ d . Let M := |U | + i=1 |Si |. The algorithm takes O(logd |U | logd N + logd M ) rounds with O(dδ ) local space and O(M ) total space. The idea is to sample with probability dδ /d = dδ−1 to obtain U ′ . In expectation, this immediately gives the bounds as stated. However, we cannot derandomize such an aggressive sampling step, as the objective function cannot be evaluated within one machine. Hence we design a recursive sampling scheme, using ℓ iterations, for some constant ℓ to be determined. The goal is that within each iteration, we can construct objective functions that cannot be evaluated locally. We sample with a larger probability p, such that pℓ = dδ−1 . If we take p = 1/dδ/2 , then we need ℓ · δ/2 = 1 − δ, or equivalently ℓ = 2/δ − 2. For simplicity, we assume that ℓ = 2/δ − 2 is a positive integer. If not, we set ℓ = max{1, ⌈2/δ − 2⌉} and set p = d(δ−1)/ℓ , which is almost 1/dδ/2 and only affects the constants in the proof below. Now we compute ℓ subsets U = U (0) ⊇ U (1) ⊇ . . . ⊃ U (ℓ) = U ′ recursively by sampling each element in U (j) for U (j+1) with probability p = 2/dδ/2 . Note that this is a factor 2 bigger than stated previously, which is needed to reach the dδ lower bound, without additional constants. Then, during the recursive iterations, we aim to obtain sets U (j) ⊆ U for i ∈ [1, ℓ] such that 1. |U (j) | ≤ |U | · pj , j 2. |Si ∩ U (j) | ≤ d 3p for each i ∈ [N ]. 2 3. |Si ∩ U (j) | ≥ d
p j for each i ∈ [N ]. 2
We note here that the upper bound of 2 becomes in the end d
j 3p 2
p ℓ
= 3ℓ · dδ . Since ℓ is a
constant, this becomes O(dδ ). The lower bound of 3 becomes d 2 = dδ . In the following, we describe how to derandomize the sampling U (j+1) from U (j) , satisfying these three properties. We assume that U (j) is given. Moreover, we suppose that for an index i ∈ [N ], the elements of the set Si ∩ U (j) are stored in consecutive machines, with dδ elements per machine, except at most one since we can sort in O(1/δ) rounds with O(dδ ) local space by Lemma 3.1.
33
Reducing randomness via limited dependent hash functions. We let H be a family of (j) → [⌈1/p⌉], where p = 200 /dδ/2 . Each hash ( 12 δ logd N )-wise independent hash functions h : U δ function h corresponds to a set of elements Dh := {u ∈ U (j) | h(u) = 1}. By the following claim, we can bound the expected size of Dh . For a machine M , we let V (M ) be the set of elements stored in M . δ/4
Claim 4.15. Let N < dd . Let H be a family of ( 24 δ logd N )-wise independent hash functions δ/2 . For h ∼ H, the expected size of D is |U (j) |·p. Moreover, h : U (j) → [⌈1/p⌉], where p = 200 /d h δ δ vertices of some set S , we have that P for each machine M storing d [||V (M ) ∩ Dh | − µ| ≥ i h∼H δ/2 . µ/2] ≤ O dN1 2 , for µ := |V (M )| · p ≥ 200 · d δ Proof. It is clear that the expected size of Dh is at most |U (j) | · p by linearity of expectation. In the following, we prove the latter claim. For a machine M storing at least dδ vertices of some set Si , we let µ := |V (M )| · p denote the expected sampled size. We bound the probability that |V (M ) ∩ Dh | deviates by more than µ/2. Note that |V (M ) ∩ Dh | is the same as the sum of the indicator random variable Xu for the event u ∈ Dh for u ∈ V (M ). Here, we let Xu be ( 24 δ logd N )-wise independent random variables, that is Xu = 1 if u ∈ Dh , otherwise Xu = 0. Next, we want to use Lemma 3.6, which requires that 200 δ/2 µ ≥ 24 ≥ 24 δ logd N . We see that this is the case by filling in µ ≥ δ d δ logd N . So Lemma 3.6 implies the following bound: X Ph∼H [||V (M ) ∩ Dh | − µ| ≥ µ/2] = Ph∼H Xu − µ ≥ µ/2 u∈V (M )
! 12 logd N
δ 2 · 24 logd N δ logd N ≤8 1 dδ/2 ·µ 22 12 logd N δ 1 1 ≤8 . ≤ O dN 2 dδ/4
12 logd N δ
≤8
Derandomization via the method of conditional expectation. Our goal is to compute a hash function h∗ in H which corresponds to U (j+1) := Dh∗ so that |Dh∗ | is at most O(|U (j) | · p) and |V (M ) ∩ Dh∗ | ≥ |V (M )| · p for every machine M if |V (M )| ≥ dα . To obtain this, we use the method of conditional expectation, Lemma 3.8. Hereto, we define the corresponding objective functions. First, consider the elements of U (j) stored on |U (j) |/L machines. Let f1 , . . . f|U (j) |/L denote the number of sampled elements on each such machine. Hence, we can write the size of the P|U (j) |/L sampled elements as Dh = i=1 fi (h). Next, we need to ensure that we do not under- or over-sample on any machine. Here the objective functions are going to be different than before. We consider O(N · d1−δ ) machines M1 , . . . , MO(N ·d1−δ ) storing the sets S1 ∩ U (j) , . . . SN ∩ U (j) . On each such machine Mi , let ( |U | if ||V (M ) ∩ Dh | − |V (M )| · p| ≥ 21 |V (M )| · p, gi (h) := 0 otherwise. This means that whenever a machine does not stay close to the objective value, we artificially blow up the final size. If we find a hash function where the sum objective functions is < |U |, we know that none of the machines violate ||V (M ) ∩ Dh | − |V (M )| · p∥ ≥ 12 |V (M )| · p. Note that gi (h) can be evaluated within a single machine, and hence its expectation over all h ∼ H given some prefix can be computed internally. Claim 4.16. The values Eh∼H [fi (h) | the prefix of h ∈ H is r ] and Eh∼H [gi (h) | the prefix of h ∈ H is r ] can be computed in a single machine with L local space, for any i where fi or gi is defined and any r ∈ {0, 1}∗ . 34
Proof. As fi is defined as in Claim 4.5, the proof of Claim 4.5 holds again. The function gi (h) depends on the size of the sampled elements within one machine. Hence, for each h ∈ H, we can compute gi (h) internally. The machine sums the values gi (h) for every possible h ∈ H with prefix r and divides out by the total number of such h to obtain Eh∼H [gi (h) | the prefix of h ∈ H is r ]. Note that since we only consider one function h at the time, and we can consider O(L) elements of U , we require only L local space. Putting things together in the iterative procedure. Using the results from above, we obtain the following lemma. Claim 4.17. For p = 2/dδ/2 for some constant δ ∈ (0, 1), then we can deterministically compute a set U (j+1) ⊆ U (j) in O(logd |U | log2d N ) rounds so that: • |U (j+1) | ≤ |U (j) | · p, • |Si ∩ U (j+1) | ≤ |Si ∩ U (j) | · 3p 2 for i ∈ [N ], and • |Si ∩ U (j+1) | ≥ |Si ∩ U (j) | · p2 for i ∈ [N ] in the sublinear MPC model with O(dδ ) local space. Proof. We have the following: 1. The hash functions of H are encoded by O(log |U | logd (|U | · N ))-bit random seeds by Lemma 3.5; i hP PN d1−δ |U |/L g (h) ≤ O(|U (j) | · p) by Claim 4.15; 2. Eh∼H f (h) + i i i=1 i=1 3. The expectation of each objective function fi and gi can be computed in a single machine with L local space for any prefix r ∈ {0, 1}∗ by Claim 4.16. This satisfies the of Lemma 3.8, hence we can compute a proper hash funcP demands ∗ ) is O(|U (j) | · p) in O(log |U | log(|U | · N ) log(|U | + N )/ log3 d) = tion h∗ such that f (h i i (j+1) | < O(logd |U | log2d N ) rounds. If there is a machine Mi in MP 1 , . . . , MN ·d1−δ with |V (Mi ) ∩ U ∗ ∗ (j) |V (Mi )| · p, then the fi (h ) = |U | which contradicts to i fi (h ) is O(|U | · p). Therefore, the sampled h∗ corresponds to a set U (j+1) as required. Putting everything together. Now we can use Claim 4.17 repeatedly to obtain Lemma 4.14. Proof of Lemma 4.14. We start by applying Lemma 4.1 to reduce the size of the data we work with to O(N d) in O(logd M ) rounds. This also ensures that U is stored on O(N d1−δ ) consecutive machines and each set Si is stored within consecutive ⌈d1−δ ⌉ machines. By recursively applying Claim 4.17, we can get a set of elements U (ℓ) of size O(|U | · pℓ ) in O(logd |U | log2d N ) rounds. Furthermore, |Si ∩ U (ℓ) | = O(dδ ), and |Si ∩ U (ℓ) | ≥ d · pℓ = dδ for all i ∈ [N ], so we return U ′ = U (ℓ) . 4.3.2
Fast Hitting Sets
Using our sparsified instance from Lemma 4.14, we now obtain the following result. We note δ/4 that the demand that N < dd is in particular satisfied for N = O(poly d). Lemma 4.18. Let δ > 0 be a constant. There exists a deterministic MPC algorithm that, given δ/4 a universe U , a number d ≤ |U | and collection of N < dd subsets S1 , . . . , SN ⊆ U with P|Si | ≥ d for each i ∈ [N ], computes a hitting set D of size O(|U | logd N/d0.99 ). Let M := |U | + N i=1 |Si |. 2 δ Then the algorithm takes O(logd |U | logd N + logd M ) rounds with O(d ) local space and O(M ) total space. 35
Proof. We start by applying Lemma 4.1 to reduce the size of the data we work with to O(N d) in O(logd M ) rounds. This also ensures that U is stored on O(N d1−δ ) consecutive machines and each set Si is stored within consecutive ⌈d1−δ ⌉ machines. Next, we call Lemma 4.14 to obtain a sparsified instance U ′ ⊆ U such that |U ′ | = O(|U |/d1−δ ), |Si ∩ U ′ | = O(dδ ) and |Si ∩ U ′ | ≥ dδ for all i ∈ [N ]. We call Lemma 3.1 to store each set Si ∩ U ′ on its own machine. In the following, we describe how to compute a vertex set D ⊆ U ′ ⊆ U of size O(|U ′ | logd N/dδ ) = O(|U | logd N/d0.99 ) so that Si ∩ D ̸= ∅. As in the other sections, we derandomize random sampling using the method of conditional expectation, Lemma3.8. We consider the family H of (400 1δ logd N )-wise independent hash functions h : [|U ′ |] →
the expectation of Dh and Dh′ over h ∼ H as follows.
d0.99δ 400 δ logd N
. Then we can bound
200 ′ Claim 4.19. Let H be a family of ( δ logd N )-wise independent hash functions h : [|U |] → d0.99δ . For h ∼ H, the expectation of Dh and Dh′ are O(|U ′ | logd N/d0.99δ ) and O(1), 400 δ logd N
respectively. Proof. It is clear that the expected size of the sampled vertex set Dh is at most O(|U ′ | logd N/d0.99δ ) by the linearity of expectations. We let Xu ’s be ( 200 δ logd N )-wise independent random variables, that is Xu = 1 if u ∈ Dh , otherwise Xu = 0 for u ∈ V . Then the following probability holds for any i ∈ [N ] by Lemma 3.6: X X Ph∼H [V (Mi ) ∩ Dh = ∅] = Ph∼H Xu = 0 ≤ Ph∼H Xu − µ ≥ µ u∈V (Mi )
≤8
2 · 200 δ logd N µ
! 100 logd N δ
≤8
u∈V (Mi ) 400 δ logd N 400 0.01δ δ logd N · d
! 100 logd N δ
≤O
1 N
,
P 0.01δ . Therewhere in the second to last inequality we use µ := E[ u∈V (Mi ) Xu ] ≥ 400 δ logd N · d PN fore, Eh∼H [ i=1 f|U |/L+i (h)] is at most O(1). To apply Lemma 3.8, we define the objective functions as follows. First, consider the elements of U ′ stored on |U ′ |/L machines. Let f1 , . . . f|U ′ |/L denote the number of sampled elements on P|U ′ |/L each such machine. Hence, we can write the size of the sampled elements as Dh = i=1 fi (h). Second, the N sets S1 ∩ U ′ , . . . SN ∩ U ′ are stored on N machines M1 , . . . , MN . On each ′ such machine Mi let gi denote whether SP i ∩ U ∩ Dh = ∅. Hence, we can write the size of the N ′ elements from the second phase as Dh = i=1 gi (h). Claim 4.20. The values Eh∼H [fi (h) | the prefix of h ∈ H is r ] and Eh∼H [gi (h) | the prefix of h ∈ H is r ] can be computed in a single machine with L local space, for any i where fi or gi is defined and any r ∈ {0, 1}∗ . Proof. The function fi (h) denotes how many elements of U ′ on machine Mi are sampled. For a fixed h : U ′ → [⌈1/p⌉], the machine can check internally which elements are sampled (encoded by h(u) = 1)), by counting this for every possible h ∈ H with prefix r, and dividing out by the total number of such h, we obtain Eh∼H [fi (h) | the prefix of h ∈ H is r ]. Note that since we only consider one function h at the time, and we can consider O(L) elements of U ′ , we require only L local space. The function gi (h) denotes whether Si ∩ U ′ ∩ Dh = ∅. Again, for fixed h we can compute this. For i ∈ [N ], we see if h(u) = 1 for at least one u ∈ Si ∩ U ′ . If not, then gi (h) = 1. As before, Mi sums the values gi (h) for every possible h ∈ H with prefix r and divides out by the 36
total number of such h to obtain Eh∼H [gi (h) | the prefix of h ∈ H is r ]. Note that since we only consider one function h at the time, and we can consider O(L) elements of U ′ , we require only L local space. We now have the following: 1. The hash functions of H are encoded by O(logd N (log N + log |U |))-bit random seeds by Lemma 3.5; hP i PN |U |/L 2. Eh∼H f (h) + g (h) ≤ O(|U ′ | logd N/d0.99δ ) by Claim 4.19; i i i=1 i=1 3. The expectation of each objective function fi and gi can be computed in a single machine with L local space for any prefix r ∈ {0, 1}∗ by Claim 4.20. P|U |/L+N Then we can compute a proper hash function h∗ in H that corresponds to i=1 fi (h∗ ) ≤ 2 ′ 0.99δ O(|U | logd N/d ) in O(logd |U | logd N ) rounds by using Lemma 3.8. Note that the obtained h∗ gives a hitting set D satisfying that Si ∩ D ̸= ∅ if |V (Mi ) ∩ U ′ | ≥ dδ . By the property of U ′ , the vertex set D is a hitting set of the original instance. Furthermore, the size of D is bounded as follows due to |U ′ | ≤ O(|U |/d1−δ ): ′ |U | logd N/d1−δ |U | logd N |U | logd N |U | logd N ≤O =O =O |D| ≤ O . d0.99 d0.99δ d0.99δ d1−0.01δ This completes the proof of Lemma 4.18. 4.3.3
Hitting Sets of Size O
|U | log N d
In this section, we extend Lemma 4.8 for sublinear MPC models. That is, we compute an O(|U | log N/d) sized hitting set. Essentially, we use the algorithm from the previous section, but with another hash function (Lemma 3.7). The following lemma summarizes the result. Lemma 4.21. Let δ > 0 be a constant. There exists a deterministic MPC algorithm that, given δ/4 a universe U , a number d ≤ |U | and collection of N <dd subsets S1 , . . . , SN ⊆ U with |Si | ≥ d P |U | log N . Let M := L + |U | + N for each i ∈ [N ], computes a hitting set D of size O i=1 |Si |. d Then the algorithm takes in O(log log(d + N ) · logd log |U | log2d N + logd M ) rounds with O(dδ ) local space and O(M ) total space. Proof. Again, we start by applying Lemma 4.1 to reduce the size of the data we work with to O(N d) in O(logd M ) rounds. This also ensures that U is stored on O(N d1−δ ) consecutive machines and each set Si is stored within consecutive ⌈d1−δ ⌉ machines. We modify the algorithm of Lemma 4.8 by the same process as in Section 4.3.2 to return an O(|U | log d/d) sized hitting set in the sublinear MPC model. Again, we first call Lemma 4.14 to obtain U ′ ⊆ U such that: • |U ′ | ≤ O(|U |/d1−δ ), • |Si ∩ U ′ | = O(dδ ) for i ∈ [N ], and • |Si ∩ U ′ | ≥ dδ for i ∈ [N ]. We compute a hitting set D with respect to U ′ of size O(|U ′ | log N/dδ ) = O(|U | log N/d). The idea is to sample with probability p = 2 · logdδN , and derandomize this procedure. We show how to obtain this random process with a family H of hash functions h : U ′ → [⌈1/p⌉] from Lemma 3.7 with ε = d−δ·c for some sufficiently large constant c. Lemma 3.7 gives that the random seed has O(log dδ · log log dδ ) bits. Analogous to Lemma 4.3, each hash function h ∈ H corresponds to two element sets Dh := {u ∈ U ′ | h(u) = 1} and Dh′ := {Si [1] : Si ∩ Dh = ∅, i ∈ [N ]}, where Si [1] denotes the first (lexicographically ordered) element of Si . 37
Claim 4.22. For h ∼ H, the expected size of Dh and Dh′ are O(|U ′ | log N/dδ ) and O(1), respectively. The proof of this claim is exactly the same as the proof of Claim 4.12, with D1 and dδ instead of U and d. To apply Lemma 3.8, we define the objective functions as follows. First, consider the elements of U ′ stored on |U ′ |/L machines. Let f1 , . . . f|U ′ |/L denote the number of sampled elements on P|U ′ |/L each such machine. Hence, we can write the size of the sampled elements as Dh = i=1 fi (h). Second, the N sets S1 ∩ U ′ , . . . SN ∩ U ′ are stored on N machines M1 , . . . , MN . On each ′ such machine Mi let gi denote whether SP i ∩ U ∩ Dh = ∅. Hence, we can write the size of the N ′ elements from the second phase as Dh = i=1 gi (h). Claim 4.23. The values Eh∼H [fi (h) | the prefix of h ∈ H is r ] and Eh∼H [gi (h) | the prefix of h ∈ H is r ] can be computed in a single machine with L local space, for any i where fi or gi is defined and any r ∈ {0, 1}∗ . Since fi and gi are defined the same, the proof of the claim is exactly the same as in Claim 4.20 Now, we have the following: 1. The hash functions of H are encoded by s-bit random seeds by Lemma 3.7; hP i PN |U |/L 2. Eh∼H f (h) + g (h) ≤ O(|U ′ | log N/dδ ) by Claim 4.22; i i i=1 i=1 3. The expectation of each objective function fi and gi can be computed in a single machine with L local space for any prefix r ∈ {0, 1}∗ by Claim 4.23. P|U |/L+N Then we can compute a proper hash function h∗ in H that corresponds to i=1 fi (h∗ ) ≤ O(|U ′ | log N/dδ ) in O(s log k/ log2 d) = O(log log(d + N ) logd N ) rounds by using Lemma 3.8. Note that the obtained h∗ gives a hitting set D satisfying that Si ∩ D ̸= ∅ if |V (Mi ) ∩ U ′ | ≥ dδ . By the property of U ′ , the vertex set D is a hitting set of G. Furthermore, the size of D is bounded as follows due to |U ′ | ≤ O(|U |/d1−δ ): ′ |U | log N |U |/d1−δ log N |U | log N |D| ≤ O . ≤O =O d dδ dδ
38
5
Application I: Spanner Algorithms
In this section, we derive deterministic algorithms for spanners of undirected graphs in the Congested Clique and the MPC model by applying the hitting set algorithms illustrated in Section 4. In Section 5.1, we first construct an O(k)-spanner with O(n1+1/k ) edges for an unweighted graph with n vertices in linear MPC model and the Congested Clique. Then, in Section 5.2, we give a reduction from weighted spanners to unweighted spanners, obtaining Theorem 1.2. As described in Section 1.1.1, these spanners can subsequently be used to obtain O(log n)-approximate APSP results (see Section 6). Finally, in Section 5.3, we give our results for weighted spanners in sublinear MPC.
5.1
Unweighted Spanners in Linear MPC and Congested Clique
In this section, we let G be an unweighted, undirected graph with n vertices and maximum degree ∆. Dory, Fischer, Khoury, and Leitersdorf [DFKL21] gave a randomized O(1)-round algorithm constructing an O(k)-spanner of G in the MPC model with Õ(n) local space. Briefly, their main approach was to build and merge several spanners hierarchically with respect to the degrees of the vertices. They compute small sized di -dominating sets Di of G with di = 2i−1 and Di ⊆ Di−1 for all i ∈ [⌈log ∆⌉]. Here, a di dominating set refers to a vertex set D ⊆ V so that (N (v) ∪ {v}) ∩ D ̸= ∅ for every vertex v ∈ V with deg(v) ≥ di . Then they compute and union the spanners with respect to the clustering graphs defined by the dominating sets D1 , . . . , D⌈log ∆⌉ . Briefly, they decompose G into ⌈log ∆⌉ subgraphs G1 , . . . , G⌈log ∆⌉ so that: a vertex and an edge of G is in at least one of them, and a vertex in Gi is in Di or adjacent to a vertex in Di . Then they define clustering graphs of vertices Di ’s, and a vertex of Gi not in Di joins one of the adjacent clusters. Finally, they compute the spanners for the clustering graphs, and return their union and additional O(n) edges inside the clusters as a spanner of the original graph G. In this section, we derandomize their algorithm in the linear MPC model. In particular, we improve the local space to O(n) instead of Õ(n). Note that [DFKL21] used random processes for two steps. First, to compute the dominating sets Di . Second, to compute the spanners of the clustering graphs. We obtain a deterministic algorithm by Theorem 1.7 for the dominating set, and deriving deterministic sparsifying algorithm for the clustering, illustrated by Lemma 5.1. Although Lemma 5.1 gives a pretty larger spanner than our desired size, by applying it on the clustering graphs, we can reach the O(n1+1/k ) sized O(k) spanner as [DFKL21]. Clustering graphs. In the following, we construct and apply clustering graphs. For an unweighted graph G, a graph C = (VC , EC ) is a clustering graph if the following holds: • Each vertex v belongs to exactly one cluster in VC . • Two clusters c and c′ in VC are adjacent in the clustering graph C if and only if there is an edge in G between two vertices that belong to c and c′ , respectively. We say each cluster of C has a bounded radius at most r when each cluster has a center vertex c ∈ V and for any other vertex v ∈ V in the cluster, dG (c, v) ≤ r. In this section, we only consider clustering graphs whose clusters have bounded radius. For convenience, we let the vertex set VC of the clustering graph C correspond to the center vertices of the clusters, where each vertex represents its respective cluster. We suppose that each edge {c, c′ } in C stores an actual edge in G between two vertices that belong to c and c′ , respectively. Furthermore, we suppose that each vertex v in G knows the cluster in C to which v belongs. The clustering graph compresses the original graph while preserving all the essential properties required for constructing spanners, and thus has been widely used as a powerful technical tool for building spanners [DFKL21; BDGM+21]. Especially, it is a well-known observation 39
that any ℓ-spanner of C can be translated to an O(ℓ)-spanner of G when each cluster of C has a radius one. Note that if each cluster in C has radius one, then there is a star subgraph in G whose center is the center of the cluster and the leaves are the vertices belonging to the cluster. Then when we have an ℓ-spanner HC of C, we can obtain an O(ℓ)-spanner H of the original graph G by replacing each vertex of HC (cluster of C) by the star graph. Additionally, we can replace the edge between two clusters c and c′ in HC by an actual edge in G between two vertices belonging to the clusters of c and c′ , respectively. Then the obtained graph is an O(ℓ)-spanner. Sparsification of graphs. A deterministic algorithm to compute a spanner for the clustering graphs, was constructed by Leitersdorf [Lei22] in the Congested Clique model. If we use it on the original input graph, the obtained spanner size is pretty larger than our desire. However, after we compress the graph as a clustering graph, we can achieve the desired size. We simulate this deterministic algorithm in the MPC model using the following lemma by setting F as a clustering graph of G with M 1−2/s N 2/s = O(|V (G)|) and M 1/s N 1−1/s = o(|V (G)|) for some parameter s ≥ 3. A detailed proof is in Section 5.1.2. Lemma 5.1. Let F = (VF , EF ) be a graph with N vertices and M edges but no isolated vertex. For any positive s ≥ 3, we can deterministically construct a (2k − 1)-spanner for F with O(M 1/s N 1−1/s+1/k ) edges in O(1)-rounds in the MPC model with O(M 1−2/s · N 2/s ) local space and O(M ) total space. Sketch of the proof. The algorithm is analogous to that of Leitersdorf [Lei22]. However, we generalize the prior work by introducing a parameter s, where the original lemma is formulated for the special case when s = 3. Additionally, we give its implementation in the MPC model not only in the Congested Clique. Briefly, we let p = ⌈(2M/N )1/s ⌉, and we use at most O(p2 ) machines with O(M/p2 ) local size. Note that this is at least linear local space, since O(N ) ≤ O(M/p2 ) = O(M 1−2/s N 2/s ), using that M ≥ Ω(N ) since there are no isolated verices. Our algorithm consists of two phases. In the first phase, we distribute the given edges evenly across O(p2 ) machines so that: Each machine stores at most M/p2 + 2N edges while the induced subgraph of F by the edges has at most O(N/p) vertices. Therefore, we suppose that each of the O(p2 ) machines stores an induced subgraph. In the next phase, each of the O(p2 ) machines simultaneously runs the centralized algorithm [ADDJ+93] to get a (2k − 1)spanner with O((N/p)1+1/k ) edges of its induced subgraph. Since the induced subgraphs form a decomposition of the whole graph F , the union of (2k − 1)-spanners forms a (2k − 1)-spanner of the graph F , of total size O(M 1/s N 1−1/s+1/k ). In the following, we give the detailed algorithm computing a O(k)-spanner with O(n1+1/k ) edges by applying the dominating set algorithm of Theorem 1.7 and Lemma 5.1. 5.1.1
Implementation in the MPC model
The algorithm is the same as the previous one of [DFKL21], except that we use the deterministic hitting set algorithm of Theorem 1.7 instead of the random sampling process. Furthermore, we use the deterministic sparsification Lemma 5.1 instead of the randomized version. Here, we give the implementation of the algorithm in the MPC model with O(n) local space and O(m) total space. Initially, all the edge information is given arbitrarily distributed across the machines. For each edge {u, v} stored in the machines, we replace it into two pairs (u, v) and (v, u). By using the sorting of Lemma 3.1 to the 2m pairs corresponding to the edge set, we can gather the edges incident to a vertex into a single machine. Then we can compute the degree of every vertex, and thus, we partition the vertices according to their degree: V = V1 ∪ V2 ∪ · · · ∪ V⌈log ∆⌉ such that Vi := {v ∈ V | di ≤ deg(v) < 2di }. It takes O(1) rounds. In the following, each vertex v is stored as a pair (v, x) with an index x ∈ [⌈log ∆⌉] of which v ∈ Vx . Furthermore, we replace each pair (v, u) corresponding to an edge {u, v} as (x, v, u) with v ∈ Vx . 40
Hitting sets D1 ⊇ . . . ⊇ D⌈log ∆⌉ . We first show how to compute di -dominating sets Di′ ′ of G with di = 2i−1 for all i ∈ [⌈log ∆⌉]. Here, D1′ , . . . , D⌈log ∆⌉ do not satisfy the monotonicity condition yet, however, we would construct the hitting set Di ’s from them. We first aim to obtain sets Di′ ⊆ V such that (N (v) ∪ {v}) ∩ Di′ ̸= ∅ for every vertex v with deg(v) ≥ di . In other words, our goal is to solve the hitting set problem defined on the sets {N (v) ∪ {v} | v ∈ Vi }, whose size is at least di but at most 2di , and the universe Ui = Vi ∪ N (Vi ). Here, N (Vi ) is the set of vertices adjacent to Vi in G. First, we consider the case that the instance is small, more precisely: |Vi |di = O(n). In this case, the description of the problem fits in one machine. In this case, we gather all the edge information in a single machine, using the sorting process Lemma 3.1 and compute a hitting set deterministically internally using O(|Vi |di ) total space with a greedy algorithm [Lov75]. Note that since this machine is not full, it can still be shared with other instances. Next, we consider the larger case, |Vi |di = Ω(n). In this case, we use the algorithm of Lemma 4.3, with U = Ui , N = |Vi |, d = di , and L = |Ui |. This outputs a hitting set Di′ of size O(|Ui |/d0.99 + |Vi |/di ) ≤ O(n/d0.99 ) i i • in O(1) rounds P • with O( v∈Vi |N (v)| + |Ui |) = O(|Vi |di ) total space and O(|Ui |) ≤ O(n) local space. Note that the equality holds since the vertices in Vi have a degree at most 2di . Although we need [⌈log ∆⌉]-many dominating sets, by Observation 3.2, we can P construct them simultaneously in O(1) rounds in the MPC model with O(n) local space and O( i |Vi |di ) P total space. Note that the total space O( i |Vi |di ) is at most O(m) as following: X X X X deg(v) ≥ |Vi |di . 2m = deg(v) = v∈V
i∈[⌈log ∆⌉] v∈Vi
i∈[⌈log ∆⌉]
′ We suppose that the algorithm returns all the information of D1′ , . . . , D⌈log ∆⌉ within a single machine. Even if the information is distributed arbitrarily, we can redistribute it in a constant time using the sorting process Lemma 3.1. Furthermore, since each Dj′ has a size at most P O(n/d0.99 ), The total size j |Dj′ | = O(n) can be bounded by the the geometric series: j
X
|Dj′ | ≤
j∈[⌈log ∆⌉]
X
O(n/d0.99 )≤ j
j∈[⌈log ∆⌉]
X
O(n/20.99(j−1) ) = O(n/20.99⌈log ∆⌉ ) = O(n).
j∈[⌈log ∆⌉]
Now we have di -dominating set Di′ for each i. We suppose that we have a tuple ((v, x), j) for each vertex v ∈ Vx such that j is the maximum index with v ∈ Dj′ . Recall that we assumed at the start that each vertex is stored as a pair (v, x) with v ∈ Vx . If v is not in any dominating S set, then we set the index j to zero. For each i ∈ [⌈log ∆⌉], we define Di as the prefix union j≥i Dj′ , so that D1 , . . . , D⌈log ∆⌉ are the dominating sets with monotonicity. Then the pair ((v, x), j) immediately gives us the information so that v ∈ Di for every i ≤ j. Additionally, we replace the tuples (x, v, u) corresponding to the edges as the tuple (j, x, v, u) so that j is the maximum index with v ∈ Dj′ and v ∈ Vx . Note that we bound the size of Di using a geometric series: |Di | ≤
X j≥i
|Dj′ | ≤
X j≥i
O(n/d0.99 )≤ j
X
O(n/20.99(j−1) ) = O(n/20.99i ) = O(n/d0.99 ). i
j≥i
Clustering graphs C1 , . .S. , C⌈log ∆⌉ . With respect to the constructed dominating set Di for i ∈ [⌈log ∆⌉], we let Gi = ( j≥i Vj , Ei ) be the subgraph of G of which Vi is the set of vertices of S degree at least di but less than 2di and Ei is the set of edges in E whose both end vertices are in j≥i Vj but at least one is in Vi . Then our goal is to construct the clustering graphs Ci of Gi of which the cluster centers are Di and the radii of all clusters are at most one. Recall that we build 41
S S Di = j≥i Dj′ , where Dj′ is a dominating set of Vj , and thus, Di is a dominating set of j≥i Vj . Furthermore, each edges {u, v} ∈ Ei with v ∈ Vi are stored as two tuples (j, i, v, u) so that j is the maximum index with v ∈ Dj′ . Therefore, we can redistribute the tuples of the edges so that the edges of Ei are in consecutive machines. Furthermore, if |Ei | ≤ O(n), we can gather all the information of edges in a single machine using the sorting process Lemma 3.1 and compute the simple clustering graph Ci internally using O(|Ei |) total space. Note that this machine might not be full, and the remaining space still be used for other computations simultaneously. If |Ei | = Ω(n), we use the algorithm of [DFKL21], which computes such a clustering graph Ci in O(1) rounds with O(|Ei |) total space and O(n) local space. Furthermore, we can remove the parallel edges in the clustering graph Ci within constant rounds by Lemma 3.1. Briefly, we can gather the parallel edges within a single machine and remove all except one by sorting the edges labeled with the lexicographical ordering of the clusters at each endpoint of the edge. In conclusion, by Observation 3.2, we can construct all simple clustering graphs C1 , . . . , C⌈log ∆⌉ simultaneously in O(1) rounds with O(n) local space and O(m) total space. In termination, we have clustering graphs Ci ’s each Ci has O(n/d0.99 ) vertices and at most O(|Ei |) edges. i Note that in the termination of the algorithm in [DFKL21], a set of vertices in Gi adjacent to c is stored in a single machine for each vertex c ∈ Di of the clustering graph Ci . Furthermore, the tuples (i, (c, c′ ), (j, x, v, u)) and (i, (c′ , c), (k, y, v, u)) are distributed across the machines for each {c, c′ } edge in the obtained Ci , where there is an edge {u, v} ∈ Ei of which u and v are in N (c) ∪ {c} and N (c′ ) ∪ {c′ }, respectively. Recall that we assumed that each edge {u, v} is stored as two pairs (j, x, u, v) and (k, y, v, u) with the indices x, y, j, k ∈ [⌈log ∆⌉] where u ∈ Vx ∩ Dj ′ and v ∈ Vy ∩ Dk′ with j ′ ≤ j and k ′ ≤ k. The tuples can simulate the clustering graph Ci of Gi . Spanners of clustering graphs. We have the clustering graphs C1 , . . . , C⌈log ∆⌉ . Our goal is to compute the (2k − 1)-spanners H1 , . . . , H⌈log ∆⌉ of the clustering graphs and merge them. If the complexity of the clustering graph Ci is at most O(n), that means O(|Ei |) = O(n), then we can compute a (2k − 1)-spanner Hi for Ci with O(n1+1/k /d0.99 ) edges in O(1) rounds by i collecting Ei within a single machine with O(n) local space and apply the centralized algorithm of [ADDJ+93]. Note that the central algorithm gives O(N 1+1/k ) sized (2k − 1)-spanner of a graph with N vertices, and our clustering graph Ci has N = O(n/d0.99 ) vertices. i If Ci has at least Ω(n) edges, we can use Lemma 5.1 to compute the spanner Hi . Recall that the lemma gets an input graph with N non-isolated vertices and M edges along with a constant s ≥ 3, then it computes a (2k − 1)-spanner of the input graph with O(M 1/s N 1−1/s+1/k ) edges in the MPC model with O(M 1−2/s N 2/s + N ) local space and O(M ) total space. Hereto, we set the parameter s such that it balances the spanner size and the local space of the MPC model is small at the same time. This occurs exactly when s = 3.98 since Ci has O(n/d0.99 ) vertices i and O(|Ei |) = O(ndi ) edges. Precisely, if the complexity of the clustering graph Ci is at most O(n), that means O(|Ei |) = O(n), then we can compute a (2k − 1)-spanner Hi for Ci with O(n1+1/k /d0.48 ) edges in O(1) rounds by collecting Ei within a single machine with O(n) local i space and apply the centralized algorithm of [ADDJ+93]. Otherwise, when the complexity of Ci ) edges is at least Ω(n), then Lemma 5.1 returns a spanner Hi for each Ci with O(n1+1/k /d0.48 i while satisfying two things: • The total space is small: O(|Ei |) • The local space is small: O (ndi )1−2/3.98 ·
n2/3.98
0.99·2/3.98 + n
di
= O(n).
By ObservationP3.2, we can compute all Hi ’s simultaneously in the MPC model with O(n) local space and O( i |Ei |) = O(m) total space. O(k)-spanner of G. Recall that each edge information of a clustering graph Ci between c and c′ in Di is given as a tuple (i, (c, c′ ), (j, x, u, v)), where {u, v} is an actual edge in Ei of 42
which u ∈ N (c) ∪ {c} and v ∈ N (c′ ) ∪ {c′ }. Therefore, each edge of Hi ’s also gives such tuples and vertex sets. Then S we can replace all the tuples of Hi ’s as an edge {u, v} in Ei . Furthermore, for each vertex u ∈ x≥i Vx , we add the edge {u, c} ∈ E with c ∈ Di that is the last edge in the lexicographical ordering of the edge tuples (k, y, c, u), and we call it an intra edge. Choosing the lexicographically last edge {u, c} for H i ensures that it is in H j for every j ≤ i. Precisely, even if u is a vertex in H j , there is a unique intra edge in H j incident to u that is {u, c} due to the monotonicity D1 ⊇ . . . ⊇ D⌈log ∆⌉ . Recall that we assumed that each edge {u, v} ∈ E is stored as two pairs (j, x, u, v) and (k, y, v, u) with the indices x, y, j, k ∈ [⌈log ∆⌉] where u ∈ Vx ∩ Dj ′ and v ∈ Vy ∩ Dk′ with j ′ ≤ j and k ′ ≤ k. Therefore, we can compute the last edge in the lexicographical order in O(1) rounds by the sorting process Lemma 3.1. The translating process from Hi ’s to H i ’s increases the stretch of the spanners at most constant times [DFKL21].5 Therefore, it obtains O(k)-spanners H 1 , . . . , H ⌈log ∆⌉ of G1 , . . . , G⌈log ∆⌉ , respectively. Finally, we return the union of H i ’s as a O(k)-spanner of G. Even if the edges of H i ’s are arbitrarily distributed across the machines, there are O(n) edges incident to a vertex. Therefore, by sorting the edges, we can store all the edges incident to a single vertex in one machine in O(logn m) = O(1) rounds Lemma 3.1. In conclusion, our algorithm is implemented in O(1) rounds using O(n) local space and O(m) total space. Analysis. Note that each E(H i ) \ E(H i+1 ) has at most O(n1+1/k /d0.48 + |Vi |) edges, and thus, i we can obtain a subgraph H of G by union of the all edge sets of H i ’s. Then the obtained H has O(n1+1/k ) edges as follows: ⌈log ∆⌉
X
⌈log ∆⌉
O(n1+1/k /d0.48 + |Vi |) = O(n1+1/k · i
i=1
X i=1
1+1/k
≤ O(n
1 + n) 20.48(i−1)
+ n) = O(n1+1/k ).
We show that the obtained H is an O(k)-spanner of G. Precisely, for an edge {u, v} ∈ Ei in G but not in H, we show that the distance between u and v in H is at most O(k). Here, we let c(u) and c(v) be the vertices in Di adjacent to u and v, respectively. Note that there is an edge between c(u) and c(v) in the clustering graph Ci , and thus, the distance between c(u) and c(v) is at most O(k) in Hi . Since we replace each cluster center of Hi as a star graph, the distance between u and v in H i is at most a constant times the distance between c(u) and c(v) in Hi , that is O(k) as shown [DFKL21]. Therefore, in H i , the distance between u and v is at most O(k), and thus, it holds in H since it is a supergraph of H i . In conclusion, our algorithm satisfies the following theorem. Theorem 5.2. There exists a deterministic algorithm that, given a positive integer k and an unweighted undirected graph G of n vertices, computes an O(k)-spanner with O(n1+1/k ) edges in O(1) rounds in the linear MPC model with O(m) total space. 5.1.2
Sparsification Lemma
Lemma 5.1. Let F = (VF , EF ) be a graph with N vertices and M edges but no isolated vertex. For any positive s ≥ 3, we can deterministically construct a (2k − 1)-spanner for F with O(M 1/s N 1−1/s+1/k ) edges in O(1)-rounds in the MPC model with O(M 1−2/s · N 2/s ) local space and O(M ) total space. Proof. Let p = (2M/N )1/s through this proof. Since F has no isolated vertex, p are at least one. Furthermore, for any fixed constant c, M/pc is in Ω(N ) due to M/pc = Ω(M 1−c/s · N c/s ) ≥ Ω(N 1−c/s ·N c/s ) = Ω(N ). In this proof, we derive the MPC algorithm using O(p2 ) machines with 5
Precisely, in Section 3.1 of [DFKL21], the reduction is proven from a spanner of a clustering graph to a spanner of the original graph.
43
L = c(M/p2 + N ) local space for some constant c ≥ 3. Note that N ≤ M , so N 1−2/s ≤ M 1−2/s and hence N ≤ M 1−2/s N 2/s = M/p2 , so can simplify the local space to L = O(M/p2 ). Then Observation 3.2 guarantees that it can work in any MPC model with O(M ) total space and O(M/p2 ) = O(M 1−2/s N 2/s ) local space, which completes the proof. Our algorithm consists of two phases, like the algorithm of Leitersdorf [Lei22]. In the first phase, we distribute the given edges so that they are evenly organized across O(p2 ) machines so that: Each machine stores at most M/p2 + 2N edges while the induced subgraph of F by the edges has at most O(N/p) vertices. Therefore, we suppose that each of the O(p2 ) machines stores an induced subgraph. In the next phase, each of the O(p2 ) machines simultaneously runs the centralized algorithm [ADDJ+93] to get a (2k − 1)-spanner with O((N/p)1+1/k ) edges of its induced subgraph. Since the induced subgraphs form a decomposition of the whole graph F , the union of (2k − 1)-spanners forms a (2k − 1)-spanner of the graph F . Furthermore, the obtained spanner has the desired size O(M 1/s N 1−1/s+1/k ) as follows: O(p2 ) · O((N/p)1+1/k ) = O(p1−1/k · N 1+1/k ) ≤ O(p · N 1+1/k ) = O((N ps )1/s · N 1−1/s+1/k ) ≤ O(M 1/s N 1−1/s+1/k ). Note that the first inequality and the last equation holds by the definition of p = (2M/N )1/s , which is at least one. In conclusion, we can return all the edge information of the (2k − 1)spanner of F at termination. In the following, we implement our first phase since it is clear that the second phase can be done in one round. Implementation of the edge distributing phase. Our goal is to distribute the given edges into O(p2 ) machines so that each machine stores at most M/p2 + 2N edges, while their induced subgraph has at most O(N/p) vertices. Initially, the edges EF of F are arbitrarily distributed across the machines. As a preprocessing step, we reorganize the edge information so that all the edges incident to a same vertex are stored in a single machine by the sorting algorithm of Lemma 3.1 while all the edge information is stored in the first half consecutive machines. For this, we assume an arbitrary ordering ≺ in the vertices VF . Each machine replaces the edge information {u, v} ∈ EF into two pairs (u, v) and (v, u). Then we sort the 2M pairs in O(logL M ) = O(1) rounds along the lexicographical ordering by Lemma 3.1 and L ≥ c(M/p2 + N ) while M ≤ N 2 . Note that it guarantees that the edges incident to one vertex are stored in consecutive machines. After that, if one machine stores two pairs whose first elements are different, then it sends all the pairs (umin , ·) (and all the pairs (umax , ·) to its previous machine (and next machine), where umin and the umax are the smallest and largest first vertex of the pairs in the machine. After that, for each vertex v of VF , all the edges incident to the vertex are stored in a single machine, denoted by Mv . Note that it is possible that Mv and Mu are the same for u ̸= v ∈ VF . Therefore, we can compute and store the degrees for every vertex in one round at Mv in O(1) rounds. In the following, we describe how to decompose the edges into O(p2 ) machines. Note that after the preprocessing, only the first half machines have some information but the others are empty. We first decompose the vertex set into O(p) subsets, each of which has at most N/p vertices and is incident to at most M/p + N edges. Our goal is to inform to the machine Mv which part in the decomposition belongs to v. We claim to do this process in O(1) rounds. For this, we first fix the last empty machine M and broadcast its id to all machines Mv for v ∈ VF that are consecutive machines using Lemma 3.1. Then each machine Mv sends the tuples (v, degF (v), idv ) to M for every v ∈ VF , where idv is the id of the machine Mv . In the next round, M sorts the tuples with respect to ≺ ordering of the vertices. Then it cuts the sorted sequence into O(p) chunks S1 , . . . , SO(p) so that each Si consists of at most N/p vertices and the 44
sum of degF (v) for all vertices v in the chunk Si is at most M/p + N . The existence P is proven since adding one vertex into Si increases the size of Si by one while increasing v∈Si degF (v) by at most N . Furthermore, it gives a simple algorithm simulated in one round by M without any communication. In the next round, M allocates the O(p) consecutive empty machines O(p) Ni1 , . . . Ni to each Si chunk. Then M sends the information of two vertices f (i), t(i), and ids of Mt(i) and Ni1 to the machine Mf (i) for each Si , where f (i) and t(i) are the first and the last, respectively, vertices in the Si chunk. Note that a vertex v with f (i) ⪯ v ⪯ t(i) is in Si , and thus the machines Mv with v in the same chunk Si are consecutive. Therefore, each Mf (i) can broadcast the received messages to the machines Mv that belong to the chunk Si in O(logL N/p) = O(1) rounds by Lemma 3.1 and L ≥ c(M/p2 + N ). We can do the broadcasting simultaneously for every i ∈ [O(p)] in O(1) rounds by Observation 3.2. In the following, we fix a chunk Si , and we let Ti be the set of vertices adjacent to a vertex belongs to Si . Although we do not know the exact vertices in Ti , we do not need the information O(p) here. Our goal is to partition the vertex set Ti into O(p) subsets Ti1 , . . . , Ti so that each Tij j has at most N/p vertices while the number of edges between Si and Ti is at most M/p2 + 2N edges. Recall that the number of incident edges to Si is at most M/p + N , and thus, the process is analogous to the previous decomposition if we have the number of edges between a vertex u and Si for every u ∈ V . Furthermore, computing all the numbers can be done analogously to the preprocessing phase in O(1) rounds as follows. Recall that an edge incident to some vertex in Si is stored as a pair (v, u) whose first element v is a vertex of Si . Furthermore, each machine knows whether the first element v of a pair (v, u) in it belongs to Si or not. In the case that O(p) 6 v belongs to Si , the machine also has the ids for the allocated O(p) machines Ni1 , . . . , Ni . Therefore, analogously to the preprocessing phase, we can sort all of the pairs corresponding to O(p) incident edges to Si into Ni1 , . . . , Ni along ≺ ordering of the second elements in O(1) rounds. Furthermore, we can also count the number of pairs (v, u) whose first element v is in the chunk Si for every vertex u ∈ V simultaneously as we did in the preprocessing. In conclusion, we can O(p) compute the decomposition of the vertex set into O(p) subsets Ti1 , . . . , Ti so that each Tij has at most N/p vertices while the number of edges between Si and Tij is at most M/p2 + 2N edges. O(p) Furthermore, we can inform to all Ni1 , . . . , Ni so that for a pair (v, u), the second element u O(p) 1 belongs to which part of Ti , . . . , Ti as we did in the previous decomposition phase. O(p) Although we described the implementation of decomposing the vertex set into Ti1 , . . . , Ti by fixing one chunk Si , we can simultaneously do the process for every chunks Si ’s in a constant O(p) round by Observation 3.2. Furthermore, since the machines Ni1 , . . . , Ni are consecutive and j j each machine Ni knows for a pair (v, u) in Ni , the index k ∈ [O(k)] with u ∈ Tik , the machines can send their pairs (v, u) to the machine Nik with v ∈ Si and u ∈ Tik in one round. This is because the number of such pairs is at most M/p2 + 2N ≤ L. Then at termination, each machine Nij has the information of all M/p2 + 2N edges between Si and Tij for each i ∈ [O(p)] and j ∈ [O(p)]. Therefore, Nij has all the information of the edges and vertices of the induced subgraph Hij of F induced by the edges. Since the vertices of Hij is subset of Si ∪ Tij of size at most 2N/p, it has at most 2N/p vertices. This completes the O(1) rounds implementation in the MPC model for the edge distribution.
5.2
Weighted Spanners in Linear MPC and Congested Clique
In this section, we extend our unweighted spanner algorithm to weighted graphs. Thus, we let G be an edge weighted graph with n vertices. Furthermore, we assume that the weights of edges are non-negative and the maximum weight is a polynomial in n. O(p)
6
Although the machine has the id of Ni1 only, it can contact to any other machines in Ni1 , . . . , Ni they are consecutive machines.
45
since
There is a standard reduction from weighted graphs to unweighted graphs, by bucketing the edges according to weight into O(log n) graphs: Ei := {e ∈ E : 2i ≤ w(e) < 2i+1 } for i ∈ [0, O(log n)]. We then compute an O(k)-spanner Hi on each of these as an unweighted graph. We observe that Hi is a 2 · O(k) = O(k) spanner of the weighted graph Gi . Hence we obtain an O(k)-spanner of G of size O(n1+1/k log n) in constant rounds. Note that we need to run O(log n) algorithms in parallel now, leading to an O(log n) overhead in the number of machines and the size. See also [DFKL21], where they detail this using their randomized algorithm. However, there exist more involved reductions that do not incur a log n-overhead. In particular, the following lemma shows that the deterministic Congested Clique reduction of Chechik and Zhang [CZ22, Section 5] also works in the MPC model. This reduction is a distributed implementation of a version in the sequential setting, see, e.g., [ADFS+22; EN18; LS22]. Lemma 5.3. Let ε ∈ (0, 1/6] be a constant. Given a deterministic constant-round linear MPC algorithm A using O(m + n) total space that computes an α-spanner of size O(n1+1/k ) in an unweighted graph, there exists a deterministic constant round linear MPC algorithm us ing O logε1/ε (m + n) total space that computes an (1 + ε)α-spanner of size O logε1/ε n1+1/k in a weighted graph. Proof. We divide theSedge set into µε := ⌈log1+ε 1/ε⌉ sets E 1 , . . . , E µε . Each such set is defined as the union E σ := i≥1 Eiσ , where Li ≤ w(e) < Li }, where Li := L0 /εi , L0 := (1 + ε)σ . Eiσ := {e ∈ E : 1+ε 1+1/k ), for each σ ∈ [µ ]. We show how to compute a spanner H σ of Gσ = (V, E σ ) of size ε O(n S log 1/ε σ 1+1/k 1+1/k Then we output H = σ H , which has size O(µε n )=O . ε n σ So now we consider G . Before we describe the algorithm, consider the following claim.
Claim 5.4 (Lemma 5.1 from [CZ22]). For any tree T = (U, F ) that contains more than a single vertex, it can be divided into a set of at most |U |/2 vertex-disjoint star subgraphs, and the computation is done in linear time O(|U |) under the classical centralized model. Compute a minimum spanning tree T ⊆ Gσ deterministically in constant rounds [Now21, Corollary 2.4]. Note that if Gσ is not connected, we can make it connected by adding some virtual edges of large weight. Since T is a tree, it is of size O(n) and we can make it known to every machine in O(1) rounds as follows. In total, we only need O(n) memory to describe the tree. In 1 round, every machine can send the edges it knows after computing T to a designated leader. This leader than distributes all tree edges over the machines. There are m/n machines, each with memory O(n). The leader sends each machine n/(m/n) tree-edges in 1 round. Now each machine sends its n/(m/n) edges to all m/n other machines in 1 round, hence every machine receives and sends O(n) edges in total – as required. Now each machine internally creates the following sequence of trees T = T0 , T1 , T2 , . . . , TO(log n) . Each tree Ti+1 is some contraction of the previous tree Ti , defined by the following inductive S procedure. Consider the forest Fi spanned by the edges E(Ti ) \ j>i Ejσ . For each non-singleton tree T ′ ∈ Fi , apply Claim 5.4, which divides T ′ into at most |V (T ′ )|/2 stars. Then for each such star, we contract it into a single vertex. The tree resulting from these contractions is the next tree Ti+1P . Note that this can be stored in O(n) space, since each tree has size |V (Ti+1 )| ≤ |V (Ti )|/2. So i |V (Ti )| = O(n). For each i ≥ 0, let Vi ⊆ V (Ti ) denote all the vertices from Fi which are not single vertices. Define Gσi := (Vi , Eiσ ), where edges contracted within the same vertex are removed, and parallel edges are removed. Now, we want to run algorithm A on this graph to compute an unweighted α-spanner Hiσ using O(|Eiσ | + |Vi |) total space. We first argue the total space and then detail how to formulate the input and execute A.
46
Next, we show that any edge e ∈ E appears in at most two sets Eiσ (ranging over i and σ). Suppose e ∈ Eiσ , consider any other set Ejτ . We show that there is only one possible combination of j and τ , such that e ∈ Ejτ . To investigate this, let j and τ be arbitrary, and suppose e ∈ Ejτ . If i = j, {Eiσ }σ clearly forms a partition. So, without loss of generality, we assume j < i. For the two regions to overlap, we must have that (1 + ε)σ−1 (1 + ε)τ ≥ εj εi This implies that εi−j ≥ (1 + ε)σ−τ −1 and hence i − j ≤ (σ − τ − 1) logε (1 + ε) (since ε < 1). This implies that (note that logε (1 + ε) is a negative number) σ − τ − 1 < (i − j)/ logε (1 + ε) = (i − j) log1+ε ε; or equivalently τ − σ + 1 > (i − j) log1+ε (1/ε). Simultaneously, we have τ − σ + 1 ≤ µε + 1 − 1 = ⌈log1+ε (1/ε)⌉. We immediately see that for i ≥ j + 2 we get a contradiction. For i = j + 1, we µε need τ = µε and σ = 1. This means that only edges from Ei1 could also appear in Ei−1 , and all other edges appear exactly once. P Hence, we have that i O(|Eiσ | + |Vi |) = O(m + n). Therefore, we can compute all Hiσ ’s for each i and σ ∈S[µε ] in parallel on the linear MPC model with O(µε · (m + n)) total space. We S σ σ σ output H := i Hi . And finally output H = T ∪ σ H . Next, we elaborate on how we deploy algorithm A on Gσi to compute Hiσ . First, we can resort all edges using Lemma 3.1 to delete parallel edges within Gσi . Next, we use Observation 3.2 to run all calls of A for all i, σ in parallel in a constant number of rounds. log 1/ε 1+1/k To show that H indeed has stretch (1 + ε)α with O n edges, we refer to [CZ22, ε Lemma 5.4 and Corollary 5.1]. Combining Lemma 5.3 with Theorem 5.2, we obtain the following result. Theorem 1.2. There exists a deterministic algorithm that, given a positive integer k and a weighted graph G = (V, E, w) with w : E → [poly n] on n vertices, computes an O(k)-spanner with O(n1+1/k ) edges in constant rounds in the linear MPC model using O(m + n) total space. Furthermore, it can be simulated in the Congested Clique.
5.3
Weighted Spanners in Sublinear MPC
In this section, we let G be an edge weighted graph with n vertices. Our goal is to derandomize the spanner construction algorithm of Biswas, Dory, Ghaffari, Mitrović, and Nazari [BDGM+21] in the sublinear MPC model. The following theorem summarizes this section. Theorem 1.3. [Simplified version of Theorem 5.7] For constants δ, ε < 1, given a weighted graph G on n vertices and positive parameter k ≥ 1, we can deterministically construct an O(k 1+ε )spanner of G with O(n1+1/k ) edges in O(log k) rounds in the sublinear MPC model with O(nδ ) local space and O(m + n) total space. Notably, the authors said that their randomized algorithm returns a spanner with high probability by the algorithm in the near-linear total space Õ(m), instead of O(m+n) total space [BDGM+21, Theorem 1.1]. This is because they used expected size analysis for the obtained spanner by their randomized algorithm, and then they turn the expected size guarantee into a high probability bound using a Chernoff-bounds argument. To do this, they allowed O(log n) overhead on the overall memory to repeat the randomized algorithm in parallel. Here, we design a deterministic algorithm, and thus, we do not need the overhead for the repetition. Therefore, our algorithm works with O(m + n) total space. Briefly, [BDGM+21] gave a hierarchical algorithm to compute a clustering graph and merge adjacent clusters by computing a hitting set obtained by random sampling. Here, we adapt 47
our deterministic hitting set algorithm instead of the sampling algorithm to derandomize their algorithm. Precisely, we use the hitting set algorithm that gives a suboptimal size in constant rounds as illustrated by the first parts of Theorems 1.7 and 1.8. Here, the suboptimal size of the hitting set computed at each of the hierarchy levels does not affect either the final computed spanner size or the total round complexity asymptotically. This is because we rebalance the depth of the hierarchical structure of the algorithm, which has a trade-off between the total round complexity and the returned spanner size. Briefly, we increase the hierarchical levels until we reach the desired spanner size, but do not affect the total round complexity. Randomized of algorithm [BDGM+21]. The randomized algorithm initially starts with the clustering graph G(0) = G, where each cluster corresponds to a single vertex of G. Furthermore, it sets E = E(G) and ES = ∅. During the process, the algorithm removes some edges from E while inserting some edges into ES , and finally returns a spanner consisting of the edges ES . The algorithm recursively repeats ℓ epochs, where each epoch also recursively performs t iterations. We define the parameters ℓ and t later with respect to k and ε to compute a spanner with stretch O(k 1+ε ). The ith epoch grows the cluster by merging clusters in G(i−1) to obtain another clustering graph G(i) . Recall that each vertex, that is a cluster, of a clustering graph G(i) corresponds to its center vertex and an edge {c, c′ } in G(i) corresponds to an edge in G whose two end vertices belong to the clusters of c and c′ , respectively. During the algorithm, we suppose that the edge {c, c′ } corresponds to the minimum weight edge between two clusters of c and c′ in the current remaining edge set E. Furthermore, the weight of an edge {c, c′ } is the weight of its corresponding edge in E. Each ith epoch has two phases. The first phase inserts edges to ES by t iterations of BaswanaSen [BS07] algorithm on G(i−1) with probability p(i), that is an algorithm constructing a (2t−1)spanner of G(i−1) by selecting O(tni−1 /p(i)) edges, with high probability, in t iterations. The second phase contracts the clusters formed by the selected edges during the first phase, and returns the obtained contracted G(i) . The Baswana-Sen algorithm for ith epoch runs on G(i−1) and decomposes it into clusters in iterations. It initializes the set C0 of clusters as the family of the singletons {v} for every v ∈ V (G(i−1) ). Then, at the jth iteration of the ith epoch, it obtains the clusters for Cj from the input Cj−1 by merging some clusters. In the following, we refer to the nodes on G(i−1) as super-nodes, while the clusters refer to the clusters in Cj ’s. Each jth iteration randomly samples each cluster from Cj−1 with probability p(i) to construct a set Dj ⊆ Cj−1 . Then for each super-node v in V (G(i−1) ), let c∗ be the closest cluster among Dj that is adjacent to v in G(i−1) connected by the current edges in E.7 Then we add the shortest edge {u, u′ } ∈ E to ES that is between two vertices u and u′ belonging to the super-node v and the cluster c∗ , respectively, while deleting all the edges between v and c∗ from E. Furthermore, for every adjacent, but not selected, clusters c ∈ Cj−1 \ Dj to the super-node v in G(i−1) by an edge in E shorter than w(u, u′ ) to v, we analogously insert the shortest edge in E between the super-node v and the cluster c to ES , and remove all the edges between v and c from E. If there is no adjacent cluster in Dj to v, then we insert the shortest edges in E between the super-node v and the cluster c to ES for every adjacent cluster c ∈ Cj−1 to v in G(i−1) , and remove all the edges incident to v from E. The jth clusters of Cj are formed by taking each cluster in Dj , and then extending it using the edges newly inserted to ES during the jth iteration, to absorb the super-nodes connected to Dj by ES . Note that during each iteration, we do not contract the super-nodes in G(i−1) , we just extend the clusters Cj ’s step by step. After t iterations, the ith epoch terminates and returns G(i) obtained by contracting each cluster in Ct from G(i−1) . Then the super-nodes in G(i) correspond to the clusters in Ct . If G(i) has parallel edges due to the contracting phase, we only save the shortest edge and remove the 7
We define a proper p(i) later, that is related to the size of the output spanner and round complexity of the algorithm.
48
others from G(i) and E. After ℓ epochs, in the obtained G(ℓ) , we consider all remaining edges in E for the Final phase. For each super-nodes v and u in G(ℓ) , if there is a remaining edge in E between two vertices belonging to the super-nodes v and u, respectively, then we choose the shortest edge among them and insert it into ES . The quality of the output ES is guaranteed by the following lemma. Precisely, we can obtain Lemma 5.5 and Corollary 5.6 by restating the previous lemmas and theorems of [BDGM+21, Lemma 4.12, Theorem 5.11, and Lemma 5.14]. The original statements in [BDGM+21] described (t+1)i−1
the special case when ℓ = ⌈logt+1 k⌉ and p(i) = q(i) = n− k for i ∈ [ℓ] which are satisfying all inequalities of Corollary 5.6. The authors showed that such p(i)’s and q(i)’s satisfy the conditions of Lemma 5.5 with high probability for all i ∈ [ℓ], and thus, the final returned subgraph induced by ES is a spanner with O(t · n1+1/k ) edges. Lemma 5.5. By repeating ℓ epochs with t iterations, the subgraph of G induced by the finally obtained edges in ES is an O((2t + 1)ℓ )-spanner. Furthermore, if there are 0 < p(i), q(i) ≤ 1 for all i ∈ [ℓ] so that during every jth iteration of ith epoch: • The size of Dj (and Cj ) is at most O(|Cj−1 | · q(i)), and • For each v ∈ G(i−1) adjacent to at least 1/p(i) clusters of Cj−1 in G(i−1) , Dj ∩ Sv ̸= ∅, where Sv is the set of 1/p(i) closest adjacent clusters of v among Cj−1 , then the following holds: Q i t super-nodes, • The ith epoch returns G(i) with ni = O n · (q(x)) x=1 • The ith epoch inserts O (t · ni−1 /p(i)) edges to ES , and 2 Qℓ 2 t • The Final phase inserts O(nℓ ) = O n· edges to ES . x=1 (q(x)) Sketch of the proof. Here, we consider the simple case with t = 1. The ith epoch starts with G(i−1) with ni−1 super-nodes and computes D of size O(ni−1 · q(i)). With respect to the clusters in D, we insert at most 1/p(i) edges to ES per super-node of G(i−1) , and we obtain G(i) . Therefore, the number ni of the super-nodes in G(i) is at most O(ni−1 · q(i)), inductively, it is at most O(n · q(i)q(i − 1) . . . q(1)). And the number of edges inserted by ith epoch is O(ni−1 /p(i)). After ℓ epochs, since G(ℓ) has nℓ super-nodes, the Final phase inserts O(n2ℓ ) edges. For t ≥ 2, each epoch t times reduces the size of Dj ’s recursively so that the G(i) has at most O(ni−1 · (q(i))t ) nodes by inserting O(t · ni−1 /p(i)) edges to ES . For the stretch, as proven in the previous paper [DM24, Lemma 5.8 and Theorem 5.11], an edge with weight w is removed during the ith epoch between two super-nodes u and v in G(i−1) only if there is a path between them in G(i−1) consisting of at most (2t + 1) edges of weight at most w. Analogously, for the Final phase, if an edge was removed, then the two end super-nodes in G(ℓ) have a shorter edge which is contained in ES . These claims guarantee that the recursive ℓ epochs give at most O((2t + 1)ℓ ) stretch. The lemma implies that when we increase the parameters t and ℓ, then the obtained spanner has a larger stretch while the number of edges inserted by Final phase is decreased. Furthermore, even if q(i) is slightly increased, by rebalancing the p(i)’s and repeating t iterations, we can still guarantee that a sufficiently small portion of clusters remain at the end of the epoch. Therefore, the obtained spanner is sufficiently small. Corollary 5.6 formalizes it. Corollary 5.6. Let k > 1 be a constant. The number of edges in ES is at most O(t · n1+1/k ) if: Pℓ Qi−1 t 1/k , 1. i=1 x=1 (q(x)) /p(i) ≤ n 49
2.
Qℓ
t −0.5+1/(2k) . x=1 (q(x)) ≤ n
Proof. By Lemma 5.5, the number of edges inserted by ℓ epochs is bounded by: ! ! X ℓ ℓ i−1 X Y ni · t t t ≤ O n· O (q(x)) · p(i) p(i) x=1 i=1 i=1 ! ℓ Y i−1 X (q(x))t = O tn ≤ O(t · n1+1/k ). p(i) i=1 x=1
The last inequality holds by Condition 1. Furthermore, Condition 2 implies that the Final phase inserts at most O(n1+1/k ) edges. Therefore, the total size of ES is at most O(t · n1+1/k ). In the following, we set p(i) = n− (t+1)i−1 − k
(0.7t+1)i−1 k
and q(i) = p(i)0.99 , unlike the randomized one
set p(i) = n and q(i) = p(i),so that we can achieve Dj ’s satisfying the conditions in Lemma 5.5 by the deterministic hitting set algorithms of Theorems 1.7 and 1.8. Note that the hitting set algorithm gives non-optimal sized Dj ’s for each of the iterations unlike to the previous randomized algorithm that assumed the optimal size with q(i) = p(i). However, those parameters still satisfy all the inequalities of Corollary 5.6 by slightly increasing ℓ := ⌈log0.5t+1 k⌉ compared to the original randomized algorithm that set ℓ := ⌈logt+1 k⌉. That means we increase the depth of the hierarchical structures by a constant factor. Derandomization. We derandomize the algorithm of [BDGM+21]. Note that during their algorithm, randomness only occurs for sampling Dj ’s in each iteration of every epoch. We will replace this step with the hitting set algorithms of Theorems 1.7 and 1.8. Precisely, at the jth iteration (of the ith epoch), we are given Cj−1 and claim to compute the hitting set Dj by solving the hitting set problem defined by the N := |V ′ | sets Sv := the 1/p(i) closest clusters of Cj−1 in G(i−1) for each v ∈ V ′ ⊆ V (G(i−1) ), and the universe U := Cj−1 . Here, V ′ is the set of vertices of G(i−1) adjacent to at least 1/p(i) clusters of Cj−1 in G(i−1) and Sv ’s are of size d := 1/p(i). When the size 1/p(i) of the sets Sv ’s is at most nδ , then we are essentially in the ‘linear memory’ case for the hitting set: every set fits in one machine. In this case, we use the algorithm of Lemma 4.6 with L := nδ local space. If nδ < 1/p(i) ≤ n, we are in the truly sublinear case. ′ Hence, we apply the algorithm of Lemma 4.18 with L := (1/p(i))δ = nδ local space by setting some constant δ ′ = δ/ log(1/p(i)). In both of the cases, the output hitting set Dj has a size at most O(|Cj−1 |p(i)0.99 log1/p(i) |V ′ |) and satisfies Dj ∩ Sv ̸= ∅ for any v ∈ V ′ . Furthermore, the ′
round complexity is O(log1/p(i) |C|Vj−1| | ) using the MPC model with nδ local space and O(m + n) total space. This is because N = |V ′ | and U = Cj−1 , and thus the following holds for a sufficiently large n δ ′ /4 δ/4 dd = dn ≥ n ≥ N = |V ′ |. Recall that n and m refer to the number of vertices and the edges, respectively, of the entire input graph G. Round complexity and the space complexities. In [BDGM+21], each iteration is implemented by O(1) rounds in the sublinear MPC algorithm of O(nδ ) local space and O(m + n) total space [BDGM+21, Lemma 6.1 and Theorem 1.1], including the sampling process. Notably, it also supports organizing the remaining edge set E with respect to the clusters (and the supernodes) belonging to its end vertices and the weight while the clusters (and the super-nodes) are updated. Therefore, we can formulate and deterministically solve the hitting set problem above, ′ computing Sv ’s and V ′ , at each iteration in O(log1/p(i) |C|Vj−1| | ). 50
For parameters k and ε, we can return O(tk 1+ε )-spanner of G deterministically by setting (0.7t+1)i−1
k . Here, we can derive Theorem 5.7 ℓ := ⌈log0.5t+1 k⌉, t := ⌈2 · (41/ε − 1)⌉, and p(i) := n− from Lemma 5.5 and Corollary 5.6 by setting the defined ℓ, t, p(i), and q(i) = p(i)0.99 log1/p(i) n for i ∈ [ℓ]. Note that q(i) ≤ p(i)0.98 because the following holds for sufficiently large n
log1/p(i) n = 1/ logn (1/p(i)) ≤ k ≤ n1/100k ≤ (1/p(1))0.01 ≤ (1/p(i))0.01 . Details are in the proof. Theorem 5.7. For a constant δ < 1, given a weighted graph G on n vertices and positive 1+ε parameters k ≥ 1 and 0 < ε≤ 1, we can deterministically construct a O(tk )-spanner of G 2 log k with O(t · n1+1/k ) edges in O t log rounds in the sublinear MPC model with O(nδ ) local space t and O(m + n) total space, where t := ⌈2 · (41/ε − 1)⌉. Note that Theorem 1.3 is a special case when ε (and hence t) is a fixed constant. Furthermore, we can choose the parameters ε and k such that we obtain a spanner: 3
log k 1. with k 1+o(1) stretch and O(n1+1/k log k) size in O( log log k ) rounds; 3
log log n 2. with log1+o(1) n stretch and O(n log log n) size in O( log log log n ) rounds.
Proof of Theorem 5.7. Recall that by Lemma 4.6 and Lemma 4.18, each jth iteration for j ∈ [t] takes O(log1/p(i) |V ′ |/|Cj−1 |) rounds during ℓ epoches. When 1/p(i) ≥ nδ , it takes a constant round since |V ′ | ≤ n. In the other case, we have |V ′ | = |V (G(i−1) )| and |Cj−1 | = |V (G(i−1) )|(q(i))j−1 = |V (G(i−1) )|(p(i))0.98(j−1) . Therefore, the j-th iteration for j ∈ [t] takes O(0.98j). Totally, the round complexity is O(t2 ℓ) = O(t2 log k/ log t) since we set ℓ := ⌈log0.5t+1 k⌉. Furthermore, Lemma 5.5 implies that the subgraph of G induced by the finally obtained edges in ES is a spanner of G with stretch: O((2t + 1)⌈log0.5t+1 k ⌉) ≤ O((2t + 1)k log0.5t+1 (2t+1) ) ≤ O(tk log0.5t+1 (2t+1) ) ≤ O(tk 1+log0.5t+1 4 ) ≤ O(tk 1+log41/ε 4 ) = O(tk 1+ε log4 4 ) = O(tk 1+ε ). The second line holds due to t := ⌈2(41/ε − 1)⌉.
(0.7t+1)i−1
k Furthermore, during the t iterations of ith epoch, we can set p(i) = n− and q(i) ≤ p(i)0.98 as desired in Lemma 5.5. Precisely, the jth iteration of epoch i computes O(|Cj−1 |q(i)) sized Dj who has at least one of 1/p(i) closest adjacent clusters of v ∈ V (G(i−1) ) among Cj−1 for every vertex v if it is adjacent to at least 1/p(i) clusters of Cj−1 in G(i−1) . In the following, we show that the inequalities of Corollary 5.6 are satisfied. Condition 1 of Corollary 5.6 holds by the geometric series as follows:
ℓ Y i−1 X
(q(x))t /p(i) =
i=1 x=1
ℓ X
(0.7t+1)i−1 −Pi−1 0.98t(0.7t+1)x−1 x=1 k O n
i=1
≤
≤
ℓ X i=1 ℓ X
(0.7t+1)i−1 −1.4(0.7t+1)i−1 +1.4 k O n −0.4(0.7t+1)i−1 +1.4 k O n
i=1
≤ O(n1/k ). 51
Note that the second line holds due to 0.98/0.7 = 1.4. Condition 2 holds due to ℓ = ⌈log0.5t+1 k⌉ as follows: ℓ Y
t
(q(x)) ≤ O n
−
1.4(0.7t+1)ℓ −1.4 k
≤O n
−
ℓ 1.4· 0.7t+1 0.5t+1 (0.5t+1) −1.4
!
k
x=1
1.58k ≤ O n− k +1.4/k ≤ O(n−0.5+0.5/k )
The first inequality holds since ℓ ≥ 1. Additionally, the second one holds since t ≥ 1. The last inequality holds since k is at least 1, and thus, 0.9/k is at most 0.9. Therefore, Corollary 5.6 implies that the size complexity of Theorem 5.7 holds.
52
6
Application II: APSP Algorithms
In this section, we give deterministic algorithms for the approximate shortest paths problems including weighted APSP. In the previous section, we designed deterministic spanner algorithms. These spanner algorithms can be used for APSP in weighted graphs as follows. O(log n)-approximate APSP in linear MPC and Congested Clique. Theorem 1.2 gives an O(log n)-spanner of size O(n). Since this fits in one machine, we can obtain the following APSP result in linear MPC and Congested Clique. In Congested Clique, the output is explicit: the full distance table can be computed within a node. In the linear MPC model, the output is implicit: any distance query can be asnwered without additional communication rounds. Corollary 6.1. There exists a deterministic algorithms that, given a weighted graph G = (V, E, w) with w : E → [poly n] on n vertices, computes O(log n)-approximate APSP in O(1) rounds in the linear MPC model with O(m) total space or in Congested Clique. Proof. First, we consider the linear MPC model. In constant rounds, we compute an O(log n)spanner H of size O(n) using Theorem 1.2. Next, using Lemma 3.1 we can store all O(n) edges of the spanner on one machine. This machine can now answer any distance query dG (u, v) without additional communication, by outputting dH (u, v), which is an O(log n)-approximation. This can de done with any linear-space SSSP algorithm, e.g., Dijkstra’s algorithm, since H has size O(n). Next, we consider the Congested Clique. In constant rounds, we compute an O(log n)spanner H of size O(n) using Theorem 1.2. In O(1) rounds, we can make H known to every machine using Lenzen’s routing [Len13], since each node only sends and receives O(n) messages. Then, each node can internally compute APSP on H, which gives an O(log n)-approximation of APSP on G. (log1+o(1) n)-approximate APSP using a single near-linear machine. Theorem 5.7 provides a spanner with Õ(n) edges and log1+o(1) n stretch in the sublinear MPC model. Therefore, if we allow a single machine with Õ(n) local space, then we can immediately compute a log1+o(1) n-approximation for the distance between any two vertices. The proof of Corollary 6.2 is analogous to Corollary 6.1. Furthermore, we can simulate the algorithm of Corollary 6.2 in the near-linear MPC model with Õ(n) local space and O(n + m) total space by Observation 3.2. Corollary 6.2. For a constant δ < 1, there exists a deterministic algorithm that, given a weighted undirected graph G = (V, E, w) with n vertices and m edges, computes log1+o(1) napproximate APSP in O(log2 log n) rounds in the MPC model with a single machine with Õ(n) local space and additional machines with O(nδ ) local space while the total space is O(n + m). In the following, we give constant-approximate distance algorithms. In Section 6.1, we give an approximation algorithm for weighted APSP in Congested Clique. Then, in Section 6.2, we give algorithms for unweighted approximate SSSP, MSSP, and APSP in the near-linear MPC model.
6.1
A Constant Approximate Weighted APSP in the Congested Clique
In the Congested Clique model, we can compute a O(1)-approximate APSP in O(log log log n) rounds. Theorem 1.4. There exists a deterministic algorithm that, given a weighted graph G = (V, E, w) with w : E → [poly n] on n vertices, computes O(1)-approximate APSP in O(log log log n) rounds in Congested Clique. 53
Proof. Bui, Chandra, Chang, Dory, and Leitersdorf [BCCD+24] give an algorithm that computes a constant approximation of APSP in O(log log log n) rounds in Congested Clique. Their algorithm uses two randomized subroutines that can be used as a blackbox: 1) A hitting set; and 2) A spanner. For each of these, we detail what the requirements are, and how our algorithms satisfy these. 1. Hitting set. In [BCCD+24, Lemma 6.1], we have set Ñk (u) ⊆ V for every u ∈ V . The sets Ñk (u) are known to the node u and of size at least k. We need to find a hitting set VS for these sets. We need to do this four times, using our linear MPC hitting sets (Lemma 4.3 and Lemma 4.8) and Lemma 3.3. −1/4
(i) When applying this in [BCCD+24, Lemma 2.1], we set k = n2a for some param−1/2 eter a ≥ 1, and need that the size of the hitting set is bounded by |VS | ≤ n1−a . 0.99 We can compute a hitting set of size |VS | = O(n/k ) using Lemma 4.3 in constant −1/4 −1/2 rounds. We see that n/k 0.99 = n1−0.99·2a ≤ n1−a whenever 0.99 · 2a−1/4 ≥ −1/2 −4 a , or equivalently a ≥ (0.99 · 2) . The latter is satisfied since a ≥ 1 √ (ii) When applying this in [BCCD+24, Lemma 7.2], we set k = n and need |VS |3/2 = O(n). Again, using Lemma 4.3 in constant rounds, we obtain a hitting set of size √ O(n/k 0.99 ). Filling in that k = n gives |VS | = O(n0.505 ), and hence |VS |3/2 = O(n0.7575 ), which is less than O(n) as required. √ (iii) When applying this in [BCCD+24, Lemma 7.3], we set k = n and need |VS |3/2 = O(n). We obtain this by the same settings as above. Note that in the original lemma, they get that |VS |2 small enough that they can collect it in one node and compute √ APSP exactly. Our hitting set is slightly bigger (O(n0.7575 ) instead of Õ( n)), but small enough that we can compute a constant-approximate spanner of size O(n) with Theorem 1.2 and then compute APSP on the spanner. This extra constant affects the final constant, but has no impact on the running time. (iv) When applying this in [BCCD+24, Theorem 7.1], we set k = log4 n and need |VS | = O(n log k/k). We obtain this size with Lemma 4.8 in O(log log k) = O(log log log n) rounds. We note that this only needs to be done once, so leads to an additive O(log log log n) in the running time. 2. Constant-approximation spanner. In [BCCD+24, Lemma 7.1], they cite the randomized spanner from [CZ22, Theorem 1.2]. They need this spanner to have constant approximation O(k) and size O(n1+1/k ). Our deterministic Theorem 1.2 fulfills these criteria and takes constant rounds. Since subroutines 1 Items (i) to (iii) and 2 take constant rounds and are called at most O(log log log n) times and 1 Item (iv) takes O(log log log n) rounds and is called once, we obtain total round complexity O(log log log n). We note that current randomized spanners that take O(1) rounds give a better constant approximation than our deterministic constant round spanner Theorem 1.2. This difference will result in a different constant in the approximation factor of the final result, but has no impact otherwise.
6.2
A Constant Approximate Unweighted Shortest Paths in Near-Linear MPC
In this section, we consider an unweighted graph G, and we give a deterministic algorithm for a constant approximation for shortest paths in the near-linear MPC model by derandomizing the 54
algorithms of Dory and Matar [DM24]. In fact, the algorithms require few machines with nearlinear local space while the additional machines can have sublinear local space. This model is also called the heterogeneous MPC model, introduced by [FHO25]. Although the space complexities of our algorithms are analyzed by assuming the heterogeneous MPC model, the algorithms can be simulated in the near-linear MPC model, of which every machine has Õ(n) local space, with the asymptotically same total space by Observation 3.2. Dory and Matar [DM24] presented a poly(log log n)-round randomized algorithm for the Single-Source Shortest Paths (SSSP) problem for unweighted and undirected graphs. Precisely, they built a data structure in the sublinear MPC model in poly(log log n) rounds with high probability, then they store the data structure in a single near-linear spaced machine so that it can answer any query of SSSP problem in O(1) rounds. They generalized the SSSP data structure for the APSP problem by additional modification. In the other direction, they also generalized the SSSP algorithm for the Multi-Source Shortest Paths (MSSP) problem by allowing multiple machines with near-linear local space. In this section, we derandomize their MSSP and APSP algorithms, and Theorems 6.3 and 6.4 summarize the performances. Note that when we set S as a singleton {s} in Theorem 6.3, we can get the algorithm for the SSSP problem using a single near-linear spaced machine. Theorem 6.3. Let G = (V, E) be an unweighted graph on n vertices and m edges, let δ > 0 be a constant, and let ε < 1/2, ρ ∈ [1/ log log n, 1/2] be parameters. For a fixed source set S ⊆ V of size O(nρ ), there is a deterministic algorithm that computes all (1 + ε)approximate shortest 2+1/ρ log log n(log log log n−log ε) paths for every pairs (s, v) ∈ S × V in O rounds in the MPC ερ model using |S| machines with Õ(n) space and additional machines with O(nδ ) local space and Õ((m + n1+ρ )nρ ) total space. Theorem 6.4. Let G = (V, E) be an unweighted graph on n vertices and m edges, let δ > 0 be a constant, and let ε< 1/2, ρ ∈ [1/ log log n, 1/2]and 2 ≤ k ≤ 1/ρ be parameters. 2+1/ρ log log n(log log log n−log ε) There is a deterministic O rounds algorithm that computes a ερ distance oracle of size Õ(kn1+1/k ) in the MPC model using a single machine with Õ(n) space and additional machines with O(nδ ) local space and Õ((m + n1+ρ )n1/k ) total space. Our oracle supports O(1) round algorithm for (1 + ε)(2k − 1)-approximation distance query between any two vertices in G. Optimizing the total space. Recall that the algorithms of Theorem 6.3 (and Theorem 6.4) give near-linear MPC algorithms with local space Õ(n) and total space Õ((m+n1+ρ )nρ ) (and Õ((m + n1+ρ )n1/k )) with asymptotically same round complexity by Observation 3.2. As shown in [DM24], it is possible to improve the total space complexity at the cost of increasing the approximation factor by a constant factor by running the algorithms on a spanner. Specifically, they adapt the constant spanner (randomized) algorithm as a preprocessing step which reduces the number of edges, and then run the algorithms on the spanner. Recall that we have deterministic algorithms to compute sparse spanners (Section 5), and thus, we can also reduce the total space requirements to O(m + n1+c ) for some constant c ≤ 1 to obtain an O(1/c)-approximate MSSP (or an O(1/c2 )-approximate APSP algorithm) in the near-linear MPC model within poly(log log n) rounds. This space complexity is O(m) if m = Ω(n1+c ). First, we construct an O(1/c)-spanner G′ of size O(n1+c/3 ) for the input graph G in O(1) rounds by Theorem 1.2, that is an O(1) rounds deterministic algorithm to compute such a spanner in the linear MPC model. Then we run Theorem 1.5 on G′ choosing ρ = c/3 and a fixed constant ε. Then we get an O(1)-approximate MSSP algorithm on G′ , that is O(1/c)approximate on G, using O(m + n) + Õ((n1+c/3 + n1+c/3 )nc/3 ) = O(m + n1+c ) total space in poly(log log n) rounds in the near-linear MPC model. Analogously, by running Theorem 1.6 on 55
G′ with ρ = c/3, k = 2/c, and a fixed constant ε, we can get O(1/c2 )-approximate APSP data structure on G within poly(log log n) near-linear MPC rounds. Note that even in the heterogeneous MPC model with the same number of near-linear local space machines in Theorem 6.3 and Theorem 6.4, we can reduce the total space by using the spanner algorithm of Theorem 5.7, which computes an O(1/c2 )-spanner G′′ of size O(n1+c/3 ) within O(log(1/c)) sublinear MPC rounds. Since c is a constant, this process takes constant rounds. Then by running the algorithms of Theorem 6.3 (and Theorem 6.4) on G′′ with ρ = c/3 (and k = 2/c and a fixed constant ε), we can get O(1/c2 )-approximate MSSP algorithm (and O(1/c3 )-approximate APSP data structure) on G within poly(log log n) heterogeneous MPC rounds using O(m + n1+c ) total space. The algorithms of [DM24] are based on a randomized framework inspired by Thorup-Zwick approach. They demonstrate that the framework can be used to effectively generate the data structures for the approximate distance problems. The randomness occurs for the framework only. Therefore, in this section, we focus on following their framework deterministically, and we omit the details on how to apply it. Framework of [DM24]. For an unweighted graph G = (V, E), we first set good probabilities ⟨p1 , . . . , pℓ̄ ⟩ for ℓ̄ = O(log log n).8 The framework begins by hierarchically sampling the vertex sets V = A0 ⊇ A1 ⊇ Aℓ̄ with respect to the probabilities ⟨p1 , . . . , pℓ̄ ⟩, where the vertices Ai are sampled from Ai−1 with probability pi . After the hierarchical sampling of A0 = V ⊇ A1 ⊇ . . . ⊇ Aℓ̄ , their algorithm deterministically runs ℓ̄ iterations, of which the ith iteration takes O(hi ) rounds. The ith iteration is given a weighted edge set Ei , a hop parameter hi , and a distance threshold xi as input. The goal of the iteration is to compute a non-negative weighted edge set (h) Qi as follows. In the following, we use distG∪Ei (u, v) to refer to the length of the shortest path between u and v in G ∪ Ei using at most h edges. For each vertex v ∈ Ai−1 (or v ∈ V (G)),9 if (hi ) v has a vertex s ∈ Ai with distG∪E (s, v) ≤ xi , then it inserts an edge {s, v} to Qi weighted by i (h )
(h )
i i distG∪E (s, v). Otherwise, it computes all vertices u of Ai−1 so that distG∪E (v, u) ≤ xi /2. Then i i
(h )
i it inserts edges {v, u} to S Qi weighted by distG∪Ei (v, u). After ℓ̄ iterations, the algorithm returns the union of edge sets i Qi . During the algorithm, the following conditions hold for each i ∈ [ℓ̄] with high probability [DM24, Lemmas 3.5, 3.10, and 3.11]:
1. |Ai | ≤ O(|Ai−1 |pi ) and (h )
i 2. For each v ∈ V (G), there is either a sampled vertex u ∈ Ai with distG∪E (v, u) ≤ xi , or at i
(h )
i most O(log n/pi ) non-sampled vertices u′ ∈ Ai−1 \ Ai such that distG∪E (v, u′ ) ≤ xi /2. i
The performance of their algorithms is based on these properties. In the following, we define and use the hop dominating set as follows to connect our deterministic hitting set algorithm and the random framework. Note that when Ai is a hi -hop ⌊log n/pi ⌋-dominating set of Ai−1 in G ∪ Ei , then Condition (2) holds: for a vertex v ∈ V (G), if there are at least ⌊log n/pi ⌋ vertices of Ai−1 at distance at most xi /2 from v with respect to (hi ) distG∪E (v, ·), then at least one of them is selected to Ai by the definition. i Definition 6.5. We refer to a vertex set A′ ⊆ A as a h-hop d-dominating set of A ⊆ VH in an edge-weighted graph H = (VH , EH ) if either |Sv | < d or Sv ∩ A′ ̸= ∅ for every v ∈ VH , (h) where Sv is the d closest vertices in A from v with respect to the distance distH (v, ·) (or all such vertices in A if fewer than d exist). 8 Setting good parameters ensures that the output gives a useful data structure for distance approximation. Computation of the parameters is described in [DM24], and we can use the same parameters. 9 Depending on the stage and the application in which this framework is invoked, we need to consider both cases v ∈ Ai−1 and v ∈ V (G).
56
In the following, we compute the hop dominating set by the hitting set problem to derandomize the framework. Overview of the derandomized algorithms. Instead of the hierarchical implicit sampling process, our deterministic algorithm starts each ith iteration for i ∈ [ℓ̄] by explicitly defining the hitting set problem for a hi -hop ⌊log n/pi ⌋-dominating set Ai of Ai−1 in G ∪ Ei of size O(|Ai−1 |pi ). Here, we assume that Ai−1 is given by the previous (i − 1)th iteration. Then we solve the hitting set problem Lemmas 4.8 and 4.21, and we run the remaining process for the ith iteration of [DM24] which is deterministic. Our deterministic algorithm runs in O(hi + log log n) rounds per ith. Dory and Matar described how to set the good probabilities pi ’s used in the sampling process and hop parameters hi ’s, distance thresholds xi ’s, and the input edges in Ei ’s used in each iteration so that the framework gives subroutines for SSSP, MSSP, and APSP problems [DM24, Theorem 4.6 and Theorem 5.2]. Furthermore, for the applications, the hop parameters hi ’s are set at least Ω(log1+ρ log n) for some ρ > 0. Therefore, the round complexity O(hi + log log n) = O(hi ) of our deterministic iteration does not affect the total round complexity. Formulating the hitting set problem for Ai . Here, we deterministically compute a hi -hop ⌊log n/pi ⌋-dominating set Ai of Ai−1 in G ∪ Ei by solving the hitting set problem on the universe U := Ai−1 and the sets Sv ’s of size d := ⌊log n/pi ⌋ defined as follows. To define the sets, we let Vi be the set of vertices v ∈ V (G) that is reachable from at least ⌊log n/pi ⌋ vertices of Ai−1 using at most hi edges. Then we define N := |Vi | sets Sv for v ∈ Vi : (h )
i Sv := {the ⌊log n/pi ⌋ closest vertices of Ai−1 from v with respect to distG∪E (v, ·)}. i
Our goal is to compute the set Vi ⊆ V (G) and Sv ’s. The computation is implemented by O(hi ) rounds in the sublinear MPC model with O(nδ ) local space and Õ((|E| + |Ei | + n)/pi ) total space by Lemma 6.6. Precisely, we recursively apply Lemma 6.6 O(hi ) times by setting H := G ∪ Ei , the source set S := Ai−1 , and d := ⌊log n/pi ⌋. It is analogous to the multisources restricted Bellman-Ford algorithm of [DM24, Lemma 3.7]. Detailed implementation is in Section 6.2.1. Lemma 6.6. Let H = (VH , EH ) be an edge-weighted graph, let S ⊆ VH , and let h, d ≥ 1. Suppose that for every vertex v ∈ VH , we are given the d closest sources in S from v with respect (h) to the distance distH (v, ·) (or all such sources if fewer than d exist). Then we can compute, for every vertex v, the d closest sources in S with respect to the (h+1) distance distH (v, ·) (again truncated at d) in O(1/δ) rounds in the sublinear MPC model using O(|VH |δ ) local memory per machine and Õ(|EH | d) total memory. Computing Ai of size O(pi |Ai−1 |). Our goal is to compute a hitting set Ai of the universe set U := Ai−1 over the N := |Vi | sets Sv ’s of size at least d := ⌊log n/pi ⌋ defined by v ∈ Vi . We solve the hitting set problem in O(log log n) rounds by Lemmas 4.8 and 4.21 within the sublinear MPC model with L = O(nδ ) local space. Precisely, if d ≤ L := O(nδ ) (or d > L), then Lemma 4.8 (or Lemma 4.21) deterministically computes a set Ai so that: pi • |Ai | ≤ O( log n |Ai−1 | log n) = O(pi |Ai−1 |), and
• Ai ∩ Sv ̸= ∅ for every v ∈ Vi−1 . 1/4
δ/4
Note that the algorithm holds when N = poly(d, L) (and N < dL = dn when d > L), that δ/4 are hold for sufficiently large n as follows |Vi | = poly(log n, nδ ) and |Vi | < nδn in this problem. Furthermore, the round complexity is at most O(log log(d + N )) = O(log log n). In other words, we can deterministically compute Ai ⊆ Ai−1 satisfying the two invariants in O(log log n) rounds. 57
Computing Qi edge set with respect to Ai ⊆ Ai−1 . During the ith iteration, we are given the vertex set Ai−1 and the weighted edge set Ei along with the parameters hi and xi . We have computed Ai with respect to the Ai−1 . Recall that the randomized algorithm computes the edges as follows for each v ∈ Ai−1 (or v ∈ V (G)): (h )
i 1. If a vertex u ∈ Ai exists with distG∪E (v, u) ≤ xi , then add an edge {u, v} weighted by i
(h )
i distG∪E (v, u) to Qi . i
(h )
i 2. Otherwise, for every vertex u ∈ Ai−1 \ {v} with distG∪E (v, u) ≤ xi /2, add an edge {u, v} i
(h )
i weighted by distG∪E (v, u) to Qi . i
The previous randomized algorithm also gives the deterministic algorithm to compute the edges, we also give the details for completeness. The first case edges can be computed in O(hi ) rounds in the sublinear MPC model by using the single-source Bellman-Ford algorithm [BR94] by adding a dummy source s connected to each vertex in Ai by zero-weighted edges. Then, for the second case edges, we use the computed sets Sv ’s of the ⌊log n/pi ⌋ closest vertices of Ai−1 in G ∪ Ei from v. Recall that in the previous (hi ) phase, we computed the distance distG∪E (v, u) for pairs v ∈ V and u ∈ Sv , and we selected the i vertices Ai so that Sv ∩ Ai ̸= ∅ for any v ∈ V . Therefore, for the second case, it suffices to add (hi ) (hi ) the edges {u, v} weighted by distG∪E (v, u) to Qi for each vertex u ∈ Sv if distG∪E (v, u) ≤ xi /2 i i (h )
i and distG∪E (v, u′ ) > xi for every u′ ∈ Sv ∩ Ai . In conclusion, we can compute the weighted i edge set Qi in O(hi ) rounds.
6.2.1
Multi-source restricted Bellman-Ford: Proof of Lemma 6.6
In this section, we prove Lemma 6.6, restated here for convenience. Lemma 6.6. Let H = (VH , EH ) be an edge-weighted graph, let S ⊆ VH , and let h, d ≥ 1. Suppose that for every vertex v ∈ VH , we are given the d closest sources in S from v with respect (h) to the distance distH (v, ·) (or all such sources if fewer than d exist). Then we can compute, for every vertex v, the d closest sources in S with respect to the (h+1) distance distH (v, ·) (again truncated at d) in O(1/δ) rounds in the sublinear MPC model using O(|VH |δ ) local memory per machine and Õ(|EH | d) total memory. Proof. Recall that we need the subroutine for two purposes: (1) to explicitly formulate the set systems Sv ’s of the hitting set problem for Ai with respect to Ai−1 , and (2) to compute the weighted edge set Qi with respect to Ai and the sets Sv ’s. Although the previous randomized algorithm of [DM24] does not explicitly formulate the set system, it also requires a similar subroutine to deterministically compute the weighted edges Qi . Their subroutine [DM24, Lemmas (h+1) (h+1) 3.6-3.7] is designed to compute distH (v, s) for every v ∈ VH and s ∈ S if distH (v, s) ≤ x for a given distance threshold x, under the assumption that the number of such sources is at most d for each fixed vertex v ∈ VH . By slightly modifying their deterministic algorithm, we obtain the subroutine of Lemma 6.6. Briefly, both our algorithm and the previous one start (h) by updating the distance estimates distH (u, s) + w(u, v) for each edge {u, v} ∈ EH and given (h) distH (u, s)’s for s ∈ S and u ∈ VH . After this step, the previous algorithm first discards the distance estimates exceeding the threshold x, and then rearranges the remaining ones to main(h+1) tain the desired values distH (v, s)’s. In contrast, our algorithm first rearranges all updated (h+1) distance estimates to maintain the values distH (v, s), and later prunes (at most) d closest sources for each vertex v ∈ V with respect to the updated distances. In the following, we give the implementation in the sublinear MPC model with Õ(|EH |d) total space for completeness. For v ∈ VH , we let dv (and d′v ) be the number of reachable sources in S from v using at most h (and (h + 1)) edges in H if the number of such sources is fewer than d, otherwise, dv = d (and 58
d′v = d). Let Sv be the set of dv closest sources in S from S v in H using at most h edges. We ′ claim to compute the dv closest sources to v among Sv ∪ ( {u,v}∈EH Su ) using at most h + 1 edges for all vertices v ∈ VH in O(1/δ) rounds. We prove that it is sufficient to consider the S sources Sv ∪ ( {u,v}∈EH Su ) instead of the whole source set S in the analysis phase. (h)
The algorithm has three phases: Redistributing the input distances distH (v, s) between S (h+1) s ∈ Sv and v, computing the distance distH (v, s) for s ∈ Sv ∪ ( {v,u}∈EH Su ), and selecting S (h+1) d′v closest sources in Sv ∪ ( {v,u}∈EH Su ) with respect to the computed distH . Redistributing the input distances. In O(1/δ) rounds, we can redistribute the initially P (h) given O( v∈VH dv ) = O(|VH |d) distances distH (v, s)’s with s ∈ Sv by replacing the distance (h)
information as a tuple (v, distH (v, s), s) and sorting them along the lexicographical ordering so that: The tuples are stored on consecutive machines, and especially for each vertex v, its |Sv | tuples are stored on consecutive machines by applying Lemma 4.1. Then, in constant rounds, we (h) (h) can replace each tuple (v, distH (v, sj ), sj ) as (v, j, distH (v, sj ), sj ), where sj is the jth closest source in Sv to v in H. To achieve this, we apply the broadcasting algorithm from Lemma 3.1, which ensures that, for each fixed vertex v, the ID of the first machine containing tuples whose first element is v becomes known to all relevant machines. Moreover, by Observation 3.2, this broadcasting can be performed simultaneously for all vertices v ∈ VH . Consequently, each machine can locally determine the correct order of its tuples. We start by duplicating each edge {v, u} ∈ EH weighted by w(u, v) into d tuples (u, j, w(u, v), v) for j ∈ [d] and d tuples (v, j ′ , w(v, u), u) for j ′ ∈ [d]. We can do the duplicating process within O(1/δ) rounds [DM24, Lemma 3.6]. Then resort O(|VH |d) number of distance tuples (h) (v, j, distH (v, sj ), sj )’s and O(|EH |d) number of duplicated edge tuples (v, j ′ , w(v, u), u)’s along (h) the lexicographical ordering by Lemma 3.1 so that two tuples (v, j, w(u, v), u) and (v, distH (v, sj ), sj ) are stored in the single machine, denoted by M(u,v,j) . Note that in [DM24, Section 3.2], there is a detailed implementation so that M(u,v,j) can detect the id of M(v,u,j) by its local computation, but we omit this part here. Computing the distance estimates using h + 1 edges. We let M(v) be the consecutive machine storing the tuples whose first element is the vertex v. For each j ∈ [d] and {u, v} ∈ EH , (h) the machine M(u,v,j) computes the distance distH (v, sj ) + w(u, v) that is the distance estimate (h)
from sj to u through v, by using at most h+1 edges. Then it sends the distance to distH (v, sj )+ w(u, v) to the machine M(v,u,j) ∈ M(u) which is storing the jth tuple (u, j, w(v, u), v). (h)
The machines in M(u) have du distances distH (u, si )’s for si ∈ Su received as inputs and at S (h) most O(d · degH (u)) distance estimates (distH (v, sj ) + w(u, v))’s for sj ∈ {u,v}∈EH Sv received by the machines M(u,v,j) ’s. By Lemma 3.1, we sort the distances and distance estimates within the machines M(u) in O(1/δ) rounds with respect to the starting source s. Then in O(1/δ) (h) rounds, we can compute the minimum value over all distances distH (u, s) and distance estimates S (h) distH (v, s) + w(u, v) within the machines M(u) for each s ∈ Su ∪ ( {u,v}∈EH Sv ), and we define (h+1)
distH (u, s) as the minimum value. (h+1) Selecting at most d closest sources with respect to distH . For each u ∈ VH , we S (h+1) can prune the d′u closest sources s among Su ∪ ( {u,v}∈EH Sv ) and the distances distH (u, s) as we desired by applying Lemma 4.1. Recall that d′u is the number of reachable sources in S from u using at most (h + 1) edges in H if the number of such sources is fewer than d, otherwise, d′u = d. Analysis. Note that the three phases used the constant number of calls for the subroutines of Lemma 3.1, Lemma 4.1, and the duplicating process [DM24, Lemma 3.6] that are implemented by O(1/δ) rounds in the sublinear MPC model with at most Õ(|EH |d) total space. Totally, our algorithm achieves the desired space complexities and the round complexity. In the following, we prove the correctness of the algorithm. Note that the correctness of the algorithm is guaranteed 59
by the claim: For every vertex u ∈ VH , Su′ is subset of Su ∪ (
′ {u,v}∈EH Sv ). Recall that Su (and (h+1) (h) Sv ’s) is the d′u closest sources in S to u (and v) with respect to distH (u, ·) (and distH (v, ·)). Note that if d′u < d, then there are at most d′u sources of S reachable to u using at most h + 1
S
edges. By the definition, these sources are reachable to u or its neighbor using at most h edges, S ′ which implies that Su ⊆ Su ∪ ( {u,v}∈EH Sv ). Therefore, the claim holds. In the following, we ′ consider S the case that du = d. For′ the contradiction, we assume that there is a source s not in Su ∪ ( {u,v}∈EH Sv ) but it is in Su . We consider a shortest path π from s to u using at most h + 1 edges, we let {u, v} be the last edge of π. Then the prefix subpath π ′ of π obtained by removing {u, v} is a shortest path between s and v using at most h edges. Since s is not in Sv while it is a source in S reachable to v using at most h edges, there are π1′ , . . . , πd′ paths from d sources s1 , . . . , sd in S \ {s} to v that use at most h edges and shorter than the path π ′ . Then we can obtain the path π1 , . . . , πd paths from s1 , . . . , sd to u by concatenating the paths π1 , . . . , πd and {u, v}, respectively. The paths are shorter than π and use at most h + 1 edges in H. This implies that s1 , . . . , sd are closer to u than s when we allow at most h + 1 edges, which contradicts the assumption that s is one of the d closest sources from u using at most h + 1 edges. This completes the proof of this lemma.
60
References [ADDJ+93]
Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. “On sparse spanners of weighted graphs”. In: Discrete & Computational Geometry 9.1 (1993), pp. 81–100 (cit. on pp. 2, 16, 40, 42, 44).
[ADFS+22]
Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen. “Constructing light spanners deterministically in near-linear time”. In: Theoretical Computer Science 907 (2022). Announced at ESA ’19, pp. 82–112. arXiv: 1709.01960 (cit. on p. 46).
[AR20]
Udit Agarwal and Vijaya Ramachandran. “Faster Deterministic All Pairs Shortest Paths in Congest Model”. In: SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020. Ed. by Christian Scheideler and Michael Spear. ACM, 2020, pp. 11–21. doi: 10.1145/3350755.3400256. arXiv: 2005.09588. url: https://doi.org/10. 1145/3350755.3400256 (cit. on pp. 14, 15).
[ASSW+18]
Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. “Parallel graph connectivity in log diameter rounds”. In: FOCS. IEEE. 2018, pp. 674–685 (cit. on pp. 1, 14).
[ASZ20]
Alexandr Andoni, Clifford Stein, and Peilin Zhong. “Parallel approximate undirected shortest paths via low hop emulators”. In: STOC. 2020, pp. 322–335 (cit. on p. 2).
[BBDF+19]
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M Karp, and Jara Uitto. “Massively parallel computation of matching and MIS in sparse graphs”. In: PODC. 2019, pp. 481– 490 (cit. on p. 1).
[BCCD+24]
Hong Duc Bui, Shashwat Chandra, Yi-Jun Chang, Michal Dory, and Dean Leitersdorf. “Improved All-Pairs Approximate Shortest Paths in Congested Clique”. In: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024. Ed. by Ran Gelles, Dennis Olivetti, and Petr Kuznetsov. ACM, 2024, pp. 391–400. doi: 10.1145/ 3662158 . 3662804. arXiv: 2405 . 02695. url: https : / / doi . org / 10 . 1145 / 3662158.3662804 (cit. on pp. 2, 4, 5, 12, 13, 54).
[BDEL+19]
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab Mirrokni. “Near-optimal massively parallel graph connectivity”. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2019, pp. 1615–1636 (cit. on pp. 1, 14).
[BDGM+21]
Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari, Slobodan Mitrović, and Yasamin Nazari. “Massively parallel algorithms for distance approximation and spanners”. In: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. 2021, pp. 118–128. arXiv: 2003 . 01254 (cit. on pp. 1–5, 12, 39, 47–50).
[BDH18]
Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. “SemiMapReduce Meets Congested Clique”. In: CoRR abs/1802.10297 (2018). arXiv: 1802.10297. url: http://arxiv.org/abs/1802.10297 (cit. on pp. 3, 13, 20).
[BEGG+22]
Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň. “Deterministic distributed sparse and ultra-sparse spanners and connectivity certificates”. In: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. 2022, pp. 1–10. arXiv: 2204.14086 (cit. on pp. 2, 4, 8, 14, 29). 61
[BFKL21]
Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen. “Near-optimal approximate shortest paths and transshipment in distributed and streaming models”. In: SIAM Journal on Computing 50.3 (2021), pp. 815–856 (cit. on p. 2).
[BHH19]
Soheil Behnezhad, Mohammad Taghi Hajiaghayi, and David G Harris. “Exponentially faster massively parallel maximal matching”. In: FOCS. IEEE. 2019, pp. 1637–1649 (cit. on p. 1).
[BR94]
Mihir Bellare and John Rompel. “Randomness-Efficient Oblivious Sampling”. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, November 20-22, 1994. IEEE Computer Society, 1994, pp. 276– 287. doi: 10.1109/SFCS.1994.365687. url: https://doi.org/10.1109/SFCS. 1994.365687 (cit. on pp. 20, 58).
[BRS94]
Bonnie Berger, John Rompel, and Peter W. Shor. “Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry”. In: J. Comput. Syst. Sci. 49.3 (1994). Announced at FOCS ’89, pp. 454–477. doi: 10.1016/S00220000(05)80068-6. url: https://doi.org/10.1016/S0022-0000(05)80068-6 (cit. on pp. 14, 15).
[BS07]
Surender Baswana and Sandeep Sen. “A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs”. In: Random Structures & Algorithms 30.4 (2007), pp. 532–563 (cit. on pp. 12, 14, 48).
[CC23]
Sam Coy and Artur Czumaj. “Deterministic Massively Parallel Connectivity”. In: SIAM J. Comput. 52.5 (2023). Announced at STOC ’22, pp. 1269–1318. doi: 10.1137/22M1520177. arXiv: 2108.04102. url: https://doi.org/10.1137/ 22m1520177 (cit. on pp. 1, 6, 8, 10, 14, 15).
[CDKL21]
Keren Censor-Hillel, Michal Dory, Janne H Korhonen, and Dean Leitersdorf. “Fast approximate shortest paths in the congested clique”. In: Distributed Computing (2021), pp. 463–487 (cit. on pp. 2, 4, 13).
[CDP21a]
Artur Czumaj, Peter Davies, and Merav Parter. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space”. In: ACM Trans. Algorithms 17.2 (2021). Announces at SPAA ’20, 16:1–16:27. doi: 10 . 1145 / 3451992. arXiv: 1912.05390. url: https://doi.org/10.1145/3451992 (cit. on p. 1).
[CDP21b]
Artur Czumaj, Peter Davies, and Merav Parter. “Improved deterministic (∆+ 1) coloring in low-space MPC”. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 2021, pp. 469–479 (cit. on pp. 8, 14).
[CDP21c]
Artur Czumaj, Peter Davies, and Merav Parter. “Simple, deterministic, constantround coloring in congested clique and MPC”. In: SIAM journal on computing 50.5 (2021), pp. 1603–1626 (cit. on pp. 1, 7, 8, 14, 15).
[CFGU+19]
Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. “The complexity of (∆ + 1) coloring in congested clique, massively parallel computation, and centralized local computation”. In: PODC. 2019, pp. 471–480 (cit. on p. 1).
[CHKKL+19]
Keren Censor-Hillel, Petteri Kaski, Janne H Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. “Algebraic methods in the congested clique”. In: Distributed Computing 32.6 (2019), pp. 461–478 (cit. on p. 13).
[CHLT19]
Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. “Sparse matrix multiplication and triangle listing in the congested clique model”. In: Theoretical Computer Science (2019) (cit. on p. 13). 62
[CKPU23]
Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. “Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem”. In: 37th International Symposium on Distributed Computing (DISC 2023). Schloss Dagstuhl– Leibniz-Zentrum für Informatik. 2023, pp. 11–1 (cit. on p. 15).
[CŁMM+18]
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. “Round compression for parallel matching algorithms”. In: STOC. 2018, pp. 471–484 (cit. on p. 1).
[CPS20]
Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. “Derandomizing local distributed algorithms under bandwidth restrictions”. In: Distributed Comput. 33.3-4 (2020). Announced at DISC’17, pp. 349–366. doi: 10.1007/S00446020-00376-1. arXiv: 1608.01689. url: https://doi.org/10.1007/s00446020-00376-1 (cit. on pp. 8, 13).
[CZ22]
Shiri Chechik and Tianyi Zhang. “Constant-round near-optimal spanners in congested clique”. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. 2022, pp. 325–334 (cit. on pp. 2, 3, 11, 13, 46, 47, 54).
[DFKL21]
Michal Dory, Orr Fischer, Seri Khoury, and Dean Leitersdorf. “Constant-Round Spanners and Shortest Paths in Congested Clique and MPC”. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC’21. Virtual Event, Italy: Association for Computing Machinery, 2021, 223–233. isbn: 9781450385480. doi: 10.1145/3465084.3467928. url: https://doi.org/10. 1145/3465084.3467928 (cit. on pp. 1–3, 5, 11, 13, 39, 40, 42, 43, 46).
[DG08]
Jeffrey Dean and Sanjay Ghemawat. “MapReduce: simplified data processing on large clusters”. In: Communications of the ACM 51.1 (2008), pp. 107–113 (cit. on p. 1).
[DGPV08]
Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. “On the locality of distributed sparse spanner construction”. In: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing. 2008, pp. 273–282 (cit. on p. 4).
[DM24]
Michal Dory and Shaked Matar. “Massively parallel algorithms for approximate shortest paths”. In: Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures. 2024, pp. 415–426. arXiv: 2412 . 06952 (cit. on pp. 1–3, 5, 12, 13, 17, 49, 55–59).
[DN19]
Michael Dinitz and Yasamin Nazari. “Massively Parallel Approximate Distance Sketches”. In: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Vol. 153. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 2019, p. 35 (cit. on p. 17).
[DN20]
Michael Dinitz and Yasamin Nazari. “Massively Parallel Approximate Distance Sketches”. In: OPODIS. 2020 (cit. on p. 2).
[DP22]
Michal Dory and Merav Parter. “Exponentially Faster Shortest Paths in the Congested Clique”. In: J. ACM (2022), 29:1–29:42 (cit. on pp. 4, 8, 13, 14).
[EM21]
Michael Elkin and Shaked Matar. “Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work”. In: SPAA ’21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021. Ed. by Kunal Agrawal and Yossi Azar. ACM, 2021, pp. 198–207. doi: 10.1145/3409964.3461809. arXiv: 2009.14729. url: https: //doi.org/10.1145/3409964.3461809 (cit. on p. 2).
63
[EN18]
Michael Elkin and Ofer Neiman. “Efficient algorithms for constructing very sparse spanners and emulators”. In: ACM Transactions on Algorithms (TALG) 15.1 (2018). Announced at SODA ’17, pp. 1–29. arXiv: 1607 . 08337 (cit. on p. 46).
[FGG22]
Manuela Fischer, Jeff Giliberti, and Christoph Grunau. “Improved Deterministic Connectivity in Massively Parallel Computation”. In: 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA. Ed. by Christian Scheideler. Vol. 246. LIPIcs. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022, 22:1–22:17. doi: 10.4230/LIPICS.DISC. 2022.22. arXiv: 2206.01568. url: https://doi.org/10.4230/LIPIcs.DISC. 2022.22 (cit. on pp. 1, 6, 10, 14, 15).
[FGG23]
Manuela Fischer, Jeff Giliberti, and Christoph Grunau. “Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs”. In: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2023, Orlando, FL, USA, June 17-19, 2023. Ed. by Kunal Agrawal and Julian Shun. ACM, 2023, pp. 89–100. doi: 10.1145/3558481.3591081. arXiv: 2301.11205. url: https://doi.org/10.1145/3558481.3591081 (cit. on pp. 1, 7, 8, 10, 14, 15).
[FHO22]
Orr Fischer, Adi Horowitz, and Rotem Oshman. “Massively Parallel Computation in a Heterogeneous Regime”. In: PODC. 2022, pp. 345–355 (cit. on pp. 1– 3).
[FHO25]
Orr Fischer, Adi Horowitz, and Rotem Oshman. “Massively parallel computation in a heterogeneous regime”. In: Distributed Comput. 38.3 (2025). Announced at PODC’22, pp. 185–206. doi: 10 . 1007 / S00446 - 025 - 00479 - 7. arXiv: 2302 . 14692. url: https://doi.org/10.1007/s00446-025-00479-7 (cit. on pp. 4, 17, 55).
[GGHI+23]
Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň. “Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization”. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023. Ed. by Nikhil Bansal and Viswanath Nagarajan. SIAM, 2023, pp. 2532– 2566. doi: 10.1137/1.9781611977554.CH97. arXiv: 2209.11669. url: https: //doi.org/10.1137/1.9781611977554.ch97 (cit. on pp. 8, 14).
[GGJ20]
Mohsen Ghaffari, Christoph Grunau, and Ce Jin. “Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond”. In: 34th International Symposium on Distributed Computing. 2020 (cit. on p. 14).
[GGKM+18]
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. “Improved massively parallel computation algorithms for mis, matching, and vertex cover”. In: PODC. 2018, pp. 129–138 (cit. on p. 1).
[GHK18]
Mohsen Ghaffari, David G Harris, and Fabian Kuhn. “On derandomizing local distributed algorithms”. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2018, pp. 662–673 (cit. on p. 8).
[GK18]
Mohsen Ghaffari and Fabian Kuhn. “Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set”. In: 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018. Ed. by Ulrich Schmid and Josef Widder. Vol. 121. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, 29:1–29:17. doi: 10. 4230/LIPICS.DISC.2018.29. url: https://doi.org/10.4230/LIPIcs.DISC. 2018.29 (cit. on pp. 8, 14). 64
[GKU19]
Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. “Conditional hardness results for massively parallel computation from distributed lower bounds”. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2019, pp. 1650–1663 (cit. on pp. 2, 4, 14).
[GN20]
Mohsen Ghaffari and Krzysztof Nowicki. “Massively parallel algorithms for minimum cut”. In: PODC. 2020, pp. 119–128 (cit. on p. 1).
[Goo96]
Michael T Goodrich. “Communication-efficient parallel sorting (preliminary version)”. In: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing. 1996, pp. 247–256 (cit. on p. 17).
[GP24]
Jeff Giliberti and Zahra Parsaeian. “Massively Parallel Ruling Set Made Deterministic”. In: 38th International Symposium on Distributed Computing, DISC 2024, October 28 to November 1, 2024, Madrid, Spain. Ed. by Dan Alistarh. Vol. 319. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, 29:1– 29:21. doi: 10.4230/LIPICS.DISC.2024.29. arXiv: 2406.12727. url: https: //doi.org/10.4230/LIPIcs.DISC.2024.29 (cit. on pp. 1, 7, 8, 10, 14, 15).
[GSZ11]
Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. “Sorting, searching, and simulation in the mapreduce framework”. In: International Symposium on Algorithms and Computation. Springer. 2011, pp. 374–383 (cit. on pp. 2, 17).
[GU19]
Mohsen Ghaffari and Jara Uitto. “Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation”. In: SODA. 2019, pp. 1636–1653 (cit. on p. 14).
[GY20]
Parikshit Gopalan and Amir Yehudayoff. “Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials”. In: Theory Comput. 16 (2020), pp. 1–29. doi: 10.4086/TOC.2020.V016A017. url: https: //doi.org/10.4086/toc.2020.v016a017 (cit. on pp. 9, 13, 20).
[HLSS19]
MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin, and Cliff Stein. “MapReduce meets fine-grained complexity: MapReduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond”. In: arXiv preprint arXiv:1905.01748 (2019) (cit. on p. 2).
[IBYB+07]
Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. “Dryad: distributed data-parallel programs from sequential building blocks”. In: ACM SIGOPS operating systems review. ACM. 2007, pp. 59–72 (cit. on p. 1).
[JKPS25]
Hongyan Ji, Kishore Kothapalli, Sriram V Pemmaraju, and Ajitanshu Singh. “Fast deterministic massively parallel ruling sets algorithms”. In: Proceedings of the 26th International Conference on Distributed Computing and Networking. 2025, pp. 152–160 (cit. on pp. 1, 7, 8, 15).
[KPP20]
Kishore Kothapalli, Shreyas Pai, and Sriram V Pemmaraju. “Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model”. In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Vol. 182. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. 2020, pp. 28–1. arXiv: 2009.12477 (cit. on p. 15).
[KSV10]
Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. “A model of computation for MapReduce”. In: SODA. SIAM. 2010, pp. 938–948 (cit. on p. 1).
[Lei22]
Dean Leitersdorf. “Fast Distributed Algorithms via Sparsity Awareness”. PhD thesis. Technion - Israel Institute of Technology, Israel, 2022. url: https:// www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2022/PHD/PHD2022-09 (cit. on pp. 11, 40, 44). 65
[Len13]
Christoph Lenzen. “Optimal deterministic routing and sorting on the congested clique”. In: ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013. Ed. by Panagiota Fatourou and Gadi Taubenfeld. ACM, 2013, pp. 42–50. doi: 10 . 1145 / 2484239 . 2501983. arXiv: 1207.1852. url: https://doi.org/10.1145/2484239.2501983 (cit. on pp. 20, 53).
[LG16]
François Le Gall. “Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems”. In: DISC. 2016, pp. 57–70 (cit. on p. 13).
[Li20]
Jason Li. “Faster parallel algorithm for approximate shortest path”. In: STOC. 2020, pp. 308–321 (cit. on p. 2).
[LMSV11]
Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. “Filtering: a method for solving graph problems in mapreduce”. In: SPAA. 2011, pp. 85–94 (cit. on p. 1).
[Lov75]
L. Lovász. “On the ratio of optimal integral and fractional covers”. In: Discrete Mathematics 13.4 (1975), pp. 383–390. issn: 0012-365X. doi: https://doi. org/10.1016/0012- 365X(75)90058- 8. url: https://www.sciencedirect. com/science/article/pii/0012365X75900588 (cit. on pp. 5, 41).
[LPSPP05]
Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. “Minimum-weight spanning tree construction in O (log log n) communication rounds”. In: SIAM Journal on Computing 35.1 (2005), pp. 120–131 (cit. on p. 3).
[LS22]
Hung Le and Shay Solomon. “Near-Optimal Spanners for General Graphs in (Nearly) Linear Time”. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2022, pp. 3332–3361. arXiv: 2108.00102 (cit. on p. 46).
[Lub93]
Michael Luby. “Removing Randomness in Parallel Computation without a Processor Penalty”. In: J. Comput. Syst. Sci. 47.2 (1993). Announced at FOCS ’88, pp. 250–286. doi: 10.1016/0022-0000(93)90033-S. url: https://doi.org/ 10.1016/0022-0000(93)90033-S (cit. on p. 8).
[MNN+89]
Rajeev Motwani, Joseph Naor, Moni Naor, et al. The probabilistic method yields deterministic parallel algorithms. IBM Thomas J. Watson Research Division, 1989 (cit. on p. 8).
[MU17]
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017 (cit. on p. 20).
[New91]
Ilan Newman. “Private vs. Common Random Bits in Communication Complexity”. In: Inf. Process. Lett. 39.2 (1991), pp. 67–71. doi: 10 . 1016 / 0020 0190(91)90157-D. url: https://doi.org/10.1016/0020-0190(91)90157-D (cit. on p. 15).
[Now21]
Krzysztof Nowicki. “A deterministic algorithm for the MST problem in constant rounds of congested clique”. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021, pp. 1154–1165. arXiv: 1912.04239 (cit. on pp. 1, 14, 15, 46).
[NS22]
Danupon Nanongkai and Michele Scquizzato. “Equivalence classes and conditional hardness in massively parallel computations”. In: Distributed computing 35.2 (2022), pp. 165–183 (cit. on p. 2).
[Pel00]
David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000 (cit. on p. 14). 66
[PP22]
Shreyas Pai and Sriram V. Pemmaraju. “Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets”. In: PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022. Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 366–368. arXiv: 2205. 12686. url: https://doi.org/10.1145/3519270.3538472 (cit. on pp. 1, 7, 8, 15).
[PY18]
Merav Parter and Eylon Yogev. “Congested Clique Algorithms for Graph Spanners”. In: 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018. Ed. by Ulrich Schmid and Josef Widder. Vol. 121. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, 40:1–40:18. doi: 10.4230/LIPICS.DISC.2018.40. arXiv: 1805.05404. url: https://doi.org/10.4230/LIPIcs.DISC.2018.40 (cit. on pp. 2, 3, 8, 13, 14).
[RGHZ+22]
Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li. “Undirected (1 + ϵ)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms”. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 2022, pp. 478–487 (cit. on p. 2).
[TZ05]
Mikkel Thorup and Uri Zwick. “Approximate distance oracles”. In: Journal of the ACM (JACM) 52.1 (2005), pp. 1–24 (cit. on p. 12).
[Vad12]
Salil P. Vadhan. “Pseudorandomness”. In: Found. Trends Theor. Comput. Sci. 7.1-3 (2012), pp. 1–336. doi: 10.1561/0400000010. url: https://doi.org/ 10.1561/0400000010 (cit. on pp. 9, 20).
[Whi12]
Tom White. Hadoop: The definitive guide. " O’Reilly Media, Inc.", 2012 (cit. on p. 1).
[ZCFS+10]
Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, and Ion Stoica. “Spark: Cluster computing with working sets.” In: HotCloud 10.10-10 (2010), p. 95 (cit. on p. 1).
67
A
Proof of the Conditional Expectation Lemma in MPC
Lemma 3.8. We are given a family H of hash functions and k objective functions f1 , . . . , fk : H → R such that: 1. The hash functions of H are encoded by s-bit random seeds, P 2. Eh∼H [ ki=1 fi (h)] ≤ x, and 3. Eh∼H [fi (h) | the prefix of h ∈ H is r ] can be computed in a single machine with L local space for any i ∈ [k] and any prefix string r ∈ {0, 1}∗ of length at most s. P There exists a deterministic MPC algorithm that computes a function h∗ ∈ H with ki=1 fi (h∗ ) ≤ x in O(s log k/ log2 L) rounds with O(L) local space and O(kL) total space. P Proof. Let f (h) = ki=1 fi (h). We claim to compute a hash function h∗ in H with f (h∗ ) ≤ x. The first condition, Eh∼H [f (h)] ≤ x, guarantees that such a hash function exists, and the hash functions in H are encoded by s-bit random seeds. The conditional expectation method determines the s-bit random seed of h∗ . This algorithm decomposes the random seeds into t = O(s/ log L) chunks R1 , . . . , Rt of ⌊log L⌋ bits random seeds, and iteratively determines each chunk. More precisely, at the j-th iteration, we assume that the chunks R1 = r1 , . . . , Rj−1 = rj−1 are known and determine rj for the chunk Rj so that E[f (h) | the prefix of h is r1 . . . rj ] is at most E[f (h) | the prefix of h is r1 . . . rj−1 ]. After t = O(s/ log L) iterations, we determine all chunks of the random seed of h∗ so that: f (h∗ ) = E[f (h) | the prefix of h is r1 . . . rt ] ≤ E[f (h)] ≤ x. In the following, we describe how to implement each iteration in O(log k/ log L) rounds in the MPC model, which concludes that our algorithm runs in O(s log k/ log2 L) rounds, and thus, the lemma holds. We assume that the j − 1 chunks R1 , . . . , Rj have been fixed, and we describe how to compute a proper Rj+1 . We consider all O(L) possible assignments r of Rj+1 . Individually, we assign a machine M i for each objective function fi with i ∈ [k]. The algorithm has three steps. Each step takes a constant round with L local space and O(Lk) total space. First, for each index i ∈ [k], the machine M i locally computes and stores all expectations E[fi (h) | the prefix of h is r1 . . . rj r] for every possible assignments r. Hereto, we do the process for every i ∈ [k] in the machines M 1 , . . . , M k simultaneously.P Next, we let Eir := E[fi (h) | the prefix of h is r1 . . . rj r], and we compute the sum ki=1 Eir for each assignment r. Note that by the linearity of the expectations, it matches the desired expectation value of f as follows: " k # X E [f (h) | the prefix of h is r1 . . . rj r] = E fi (h) | the prefix of h is r1 . . . rj r i=1
=
k X
E[fi (h) | the prefix of h is r1 . . . rj r] =
i=1
k X
Eir .
i=1
For each computed values Eir that is stored in M 1 , . . . , M k , we replace it as a tuple (i, r, Eir ) of
the index i ∈ [k], the assignment r, and the expectation value. Then we sort the tuples along P the lexicographical ordering. Then we compute ki=1 Eri for all L assignments r simultaneously. These sorting and summation take O(log k/ log L) rounds Pk byi Lemma 3.1. Finally, we compute Rj+1 = r∗ which minimizes the expectation value i=1 Er∗ over L assignments. It takes a constant time by Lemma 3.1. In conclusion, each iteration takes O(log k/ log L) rounds, and thus, we can compute the desired hash function h∗ in O(s log k/ log2 L) rounds. 68