Improved Massively Parallel Shortest Path Computation

Improved Massively Parallel Shortest Path Computation Yi-Jun Chang∗

Shaun Quek†

Abstract

arXiv:2610.16787v1 [cs.DC] 12 Oct 2026

We present new algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model. Specifically, we construct an a-approximate Single-Source Shortest Path (SSSP) oracle: Given a query consisting of a source vertex u ∈ V , the oracle returns a-approximate distances δ(u, v) for all v ∈ V . Fix an n-vertex weighted undirected graph. We consider two regimes of the MPC model: the near-linear regime, where each machine has Θ̃(n) memory, and the heterogeneous regime, where all machines have Θ(nγ ) memory for some constant γ ∈ (0, 1], except for a single machine with Θ̃(n) memory. We develop randomised algorithms that construct O(1)-approximate SSSP oracles in O(log log n) rounds in the near-linear regime and in O(log2 log n) rounds in the heterogeneous regime. These oracles answer distance queries in O(1) rounds. Our results improve upon the recent work of Dory and Matar (SPAA 2024) which, for the same total memory, 2+O(1/γ) requires (log log n) rounds and applies only to unweighted graphs in the heterogeneous setting. We say that Ñk (u) is the approximate k-nearest neighbourhood of a vertex u if there exists an approximate distance estimate δ such that Ñk (u) consists of the k vertices closest to u according to δ, breaking ties by vertex ID. The main technical ingredient is a new method for efficiently computing approximate nO(γ) -nearest neighbourhoods in the heterogeneous MPC model in O(log2 log n) rounds.

∗ †

National University of Singapore. ORCID: 0000-0002-0109-2432. Email: cyijun@nus.edu.sg National University of Singapore. ORCID: 0009-0004-6682-742X. Email: shaun.quek@u.nus.edu

Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 3 4 5

2 Preliminaries 2.1 Graph Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Distance-Preserving Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Useful Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 A Connectivity Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 6 6 7 8

3 Technical Overview 3.1 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Skeleton Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Constructing the k-Nearest Edge Set . . . . . . . . . . . . . . . . . . . . . . . 3.2 Building the SSSP Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 From Approximate k-Nearest Neighbourhoods to SSSP Oracles . . . . . . . . 3.2.2 Computing Approximate k-Nearest Neighbourhoods . . . . . . . . . . . . . . 3.3 Comparison with Prior Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 9 9 11 12 12 13 14

4 O(1)-Approximate SSSP Oracles 15 4.1 From Approximate k-Nearest Neighbourhoods to SSSP Oracles . . . . . . . . . . . . 15 4.1.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 The Near-Linear MPC Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 The Heterogeneous MPC Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.3.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3.3 Wrapping it Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Computing k-Nearest Hopsets

30

6 Extracting k-Nearest Neighbourhoods 34 6.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 7 Skeleton Graphs 37 7.1 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 7.2 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 A MPC Tools

53

B Reporting the Path

54

1

Introduction

Shortest-path computation is one of the most fundamental problems in computer science. In this work, we study the problem in the Massively Parallel Computation (MPC) model [KSV10], a theoretical abstraction of widely used large-scale data processing frameworks such as Hadoop [Whi12], MapReduce [DG04], and Spark [ZCF+ 10]. The MPC model has received significant attention across a wide range of computational problems, including graph coloring [CFG+ 19; CDP20; GKU19; GGJ20], independent set [BBD+ 19; GGK+ 18; GKU19; GU19; GGJ20], matching [ABB+ 19; BBD+ 19; BHH23; CŁM+ 18; GGK+ 18; GKU19; GGJ20; LMS+ 11], set cover [JPP+ 25; DDŁ+ 24; HLL18], graph connectivity [ASS+ 18; ASW19; BDE+ 19; CC22; GWZ25], minimum spanning tree [LMS+ 11; Now21; ABJ+ 25], clustering [BEF+ 21; BW18; CMZ22; CLN+ 21; CCM23; CGJ+ 24], subgraph finding [BEL+ 22; CC11; PT12; SV11], string problems [BEG+ 21; GK25; HSS19; IMS17; Koo24], and geometric problems [ANO+ 14; CZ24; HT23; JMN+ 24]. The MPC Model. The MPC model is a synchronous distributed computation model in which all machines can directly communicate with one another. The input is initially distributed between machines, where each machine has limited local memory S. Computation proceeds in synchronous message-passing rounds, where the total amount of information a machine can send or receive each round is bounded by S. The objective is to minimise the number of communication rounds, which we refer to as the round complexity. The local computation power of each machine is usually ignored in the algorithm analysis as communication is the main bottleneck in most settings; in this work, we require at most polynomial (in S) running time per machine between rounds. In this work, we study the MPC model for graph problems on weighted undirected graphs. Specifically, the input is a graph G = (V, E) with n vertices and poly(n)-bounded positive weights ωG : V × V → Z. The edge set { (u, v, ωG (u, v)) : { u, v } ∈ E } is initially arbitrarily distributed across all machines; each vertex is represented by a unique vertex ID of O(log n) bits. MPC graph algorithms are typically classified based on the local memory size S, where memory is measured in words of O(log n) bits. The following three regimes are well-studied: Super-Linear: S ∈ Θ(n1+c ), where c > 0 is any constant. Near-Linear: S ∈ Θ̃(n). Sublinear: S ∈ Θ(nγ ), where γ ∈ (0, 1) is any constant. We note that the round complexity can vary significantly across different memory regimes. For instance, the state-of-the-art upper bounds on round complexity for maximal matching, maximal independent set, (1 − ε)-approximation of maximum matching, and (2 + ε)-approximation of minimum vertex cover in the MPC model are as follows: O(1) in the superlinear regime [LMS+ 11; √ AG18; HLL18], O(log log n) in the near-linear regime [BHH23; GGK+ 18], and O( log n log log n) in the sublinear regime [GU19]. Typically, the total memory available across all machines is Õ(|E|), near-linear in the total input size (we use the notations Õ(·), Θ̃(·), and Ω̃(·) to suppress factors of log±O(1) n). However, following the work of Dory and Matar [DM24], we will be considering a small amount of additional total memory, i.e., Õ(|E| + n1+c ) for a small constant c ∈ (0, 1]. Alternatively, one might view our results as applying to graphs that are slightly dense (|E| ∈ Ω(n1+c )).

1

Distance Oracles and SSSP Oracles. In this work, we are interested in the All-Pairs Shortest Paths (APSP) problem on weighted undirected graphs. A typical formulation of the problem is to output the shortest-path distances between all pairs of vertices. However, a subtle but important

challenge arises in the MPC model: Explicitly storing all-pairs shortest distances requires Ω n2 total memory. Unless the graph is sufficiently dense, the available total memory is insufficient to
store all n2 distances. To overcome this, a data structure approach is usually taken and we instead construct a distance oracle, a sparse structure that approximately preserves distances and supports efficient queries. Specifically, an a-approximate distance oracle returns, for any query pair (u, v), an estimate of the distance between u and v that is within a factor a of the true shortest-path distance. The number of rounds needed to build the oracle is called the preprocessing time, and the number of rounds needed to answer a query is the query time. We will be mainly concerned with constant-round query times, and instead focus on optimising the approximation ratio and preprocessing time. In fact, our work considers a slightly stronger data structure: an a-approximate single-source shortest paths (SSSP) oracle which, given a query source vertex u ∈ V , returns a-approximate distances δ(u, v) for all v ∈ V . We emphasise that the query received by the oracle is a single source vertex u, while the output comprises approximate shortest-path distances from u to every vertex in the graph G, so we refer to it as an SSSP oracle. Observe that an SSSP oracle immediately yields a distance oracle. Approaches in the Near- and Sub-Linear Regimes. Given a graph G, a t-spanner H is a spanning subgraph of G in which the distance between every pair of vertices is at most t times their distance in G [PS89]. It is known that every weighted undirected graph over n vertices has a (2t − 1)-spanner with O(n1+1/t ) edges [ADD+ 93], and this bound is tight assuming the Erdős girth conjecture [Erd65]. In the near-linear MPC model, Dory, Fischer, Khoury, and Leitersdorf [DFK+ 21] showed a near-optimal spanner construction: O(t)-spanners of size Õ(n1+1/t ) in constant rounds for any positive integer t. Setting t = Θ(log n), we can build an Õ(n)-size spanner and store it on a single machine. The spanner acts as an O(log n)-approximate distance oracle, where queries are answered by a local computation of shortest distances over the spanner. Similar results have been shown by Biswas et al. [BDG+ 21] and Fischer, Horowitz, and Oshman [FHO22]. While spanner constructions exist for the sublinear MPC model [BDG+ 21], it is not clear how to transform a spanner into a constant-round query-time distance oracle when each machine only has sublinear memory. Alternatively, Dinitz and Nazari [DN20] adopted a different approach based on classical techniques for distance sketches [TZ05], and showed that constant-approximate, constantround query-time distance oracles can be constructed in poly(log n) rounds in the sublinear MPC model. A natural question that arises in the sublinear MPC model is whether we can achieve both O(1) distance approximations and o(log n) rounds simultaneously. However, it is understood that the polylogarithmic round complexity of [DN20] is necessary under the widely-believed 1-vs-2-cycles conjecture [BKS17; KLM+ 14; KSV10; NS22; RMC+ 13; RVW18], which asserts that distinguishing between a single n-cycle and two disjoint (n/2)-cycles requires Ω(log n) rounds in this model. Assuming this conjecture, even basic tasks such as computing s-t distances or s-t connectivity require Ω(log n) rounds in the sublinear regime.

2

The Heterogeneous MPC Model. Consequently, achieving faster algorithms necessitates allowing one machine to have near-linear local memory. Motivated by the 1-vs-2-cycles conjecture, Fischer, Horowitz, and Oshman [FHO22] recently introduced the heterogeneous MPC model: All machines have local memory S ∈ Θ(nγ ) for some constant γ ∈ (0, 1], except for a single machine with local memory of size Θ̃(n). Intuitively, the heterogeneous MPC model is a hybrid between the sublinear and near-linear regimes and allows for a possibility to break the logarithmic barrier given by the 1-vs-2-cycles conjecture. For instance, while the best-known graph connectivity algorithm in the sublinear regime runs in O(log D + log log n) rounds [BDE+ 19] (where D is the graph diameter), the same problem can be solved in O(1) rounds in the heterogeneous regime [FHO22; AGM12]. In a recent work, Dory and Matar [DM24] presented a poly(log log n)-round construction of constant-approximate distance oracles for unweighted undirected graphs in the heterogeneous MPC regime, where the total memory is Õ(|E| + n1+c ) for a small constant c > 0. Their construction relies on two separate distance-preserving structures to handle different distance scales: A distance sketch for short distances and a linear-sized emulator for long distances. The distance sketches are based on the classical techniques of Thorup and Zwick [TZ05], while the emulator builds on the more recent methods of Elkin and Neiman [EN18]. A key limitation of this approach, however, is that the emulator construction only applies to unweighted graphs. Although there have been efforts to extend this to weighted graphs [EGN22], these do not achieve the same stretch guarantees and introduce an undesirable dependence on the edge weights of the graph. Consequently, the approach of Dory and Matar [DM24] remains restricted to unweighted graphs, with no immediate extension to the weighted setting. This leads us to consider the following question: Question 1. Does there exist a poly(log log n)-round algorithm for constructing O(1)-approximate distance oracles for weighted graphs in the heterogeneous regime?

1.1

Our Contributions

We answer the above question in the affirmative by presenting an algorithm for constructing constant-approximate SSSP oracles on weighted undirected graphs that runs in O(log2 log n) rounds in the heterogeneous MPC model. Furthermore, in the near-linear MPC regime, we improve the round complexity to O(log log n). Throughout this paper, we say that an event occurs with high probability (w.h.p.) if it holds with probability at least 1 − 1/ poly(n), where n = |V | is the number of vertices in the input graph G = (V, E). Moreover, we reserve the symbol γ to refer to the exponent of the local memory Θ(nγ ) of the machines in the sublinear or heterogeneous MPC model, where the model being referenced is made clear in context. Theorem 1 (SSSP Oracles in Near-Linear MPC). Let G = (V, E) be a weighted undirected graph with n vertices, and let c ∈ (0, 1] be a constant. In the near-linear MPC model with Õ(|E| + n1+c ) total memory, there exists a randomised algorithm that w.h.p. constructs an O(1/c2 )-approximate SSSP oracle in O(log log n) rounds. Every subsequent query can then be answered in O(1) rounds. Theorem 2 (SSSP Oracles in Heterogeneous MPC). Let G = (V, E) be a weighted undirected graph with n vertices. In the heterogeneous MPC model with Õ(|E| + n1+γ ) total memory, there exists a randomised algorithm that w.h.p. constructs an O(1/γ 2 )-approximate SSSP oracle in O(log2 log n) rounds. Every subsequent query can then be answered in O(1) rounds. 3

Our oracle improves upon that of Dory and Matar [DM24] in two aspects. First, it applies to weighted graphs, whereas their construction is limited to unweighted graphs. Second but less significantly, it achieves a polynomial (in log log n) speed-up in preprocessing time in the heterogeneous regime, reducing the complexity from (log log n)2+O(1/γ) to O(log2 log n) when the total memory is Õ(|E| + n1+γ ). This completely removes the dependence on the parameter γ in the exponent. We remark that while both our work and [DM24] obtain a constant approximation of distances, the oracle of [DM24] provides better stretch guarantees. When the total memory is Õ(|E| + n1+γ ), while both our distance oracle and that of [DM24] achieve O(1/γ 2 )-approximations, [DM24] was able to achieve a better O(1/γ)-approximation if we allow a poly(log log n) query time. Moreover, [DM24] showed that with more total memory, their distance oracles can achieve 3(1 + ε)-approximations under constant-round query times (and poly(log log n) preprocessing time), or (1+ε)-approximations under poly(log log n) query times (and O(1) preprocessing time) for any 0 < ε < 1/2. We also remark that our algorithms can be modified to report both the approximate distance as well as a path that witnesses this distance. Specifically, we construct a constant-approximate path-reporting distance oracle: Given a query pair (u, v), output a path P connecting u and v such that the length of P (i.e., the sum of the weights of all edges in P ) is within a constant factor of the true shortest-path distance between u and v. We refer to Section B for more details. In view of these results, a natural question to ask is if increasing the total memory of the MPC model to, say, poly(n) leads to faster APSP algorithms. We first note that once we have Ω(n2 ) total memory, we are no longer restricted to constructing a distance oracle and can instead explicitly output approximate distances for all vertex pairs. Namely in the near-linear MPC regime, Ω(n2 ) total memory also allows us to directly apply congested-clique algorithms (see below), for which faster constant-approximate APSP algorithms are known (e.g., [BCC+ 24]). In the heterogeneous MPC regime, however, it is unclear to us whether additional total memory alone can lead to faster algorithms. We believe this is an interesting direction for future research.

1.2

Related Work

Bypassing the 1-vs-2-cycles conjecture. It is well known that the logarithmic barrier imposed by the 1-vs-2-cycles conjecture can be bypassed using geometric information [ANO+ 14]. Concretely, an embedded planar graph is a planar graph equipped with a straight-line drawing, where the coordinates of each vertex in the plane are provided as input. For such graphs, in the sublinear MPC model, a (1 + ε)-approximate SSSP can be computed in O(1) rounds using O(n) total memory, and a (1 + ε)-approximate APSP can be computed in O(1) rounds using O(n2 ) total memory [CZ24; HT23]. Congested Clique. Of related interest is the distributed model known as the congested clique. In this model, the communication network forms a fully connected clique of n vertices, where each vertex can send Θ(log n)-bit messages to every other vertex in synchronous rounds. Given an nvertex graph G as input, each vertex initially knows only the edges incident to it in G. By the end of an APSP algorithm, every vertex should know the (approximate) distances to all other vertices in G. While G can be an arbitrary graph on n vertices, the communication network itself is a clique. The MPC and congested clique models share several similarities. For instance, any congested clique algorithm for dense graphs with O(n2 ) edges that uses at most O(n) local memory per vertex can be simulated directly in the near-linear MPC model with nearly the same round complex-

4

ity [BDH18]. In fact, it is common for algorithms developed for one model to be adapted for the other [DFK+ 21; BDG+ 21; CDP20]. APSP in the congested clique has received considerable attention in recent years. Of particular relevance is the work of Dory and Parter [DP22], which presented a poly(log log n)-round algorithm for (2 + ε)-approximate APSP in unweighted graphs, and the more recent work of Bui et al. [BCC+ 24], which achieved an O(log log log n)-round algorithm for O(1)-approximate APSP in weighted graphs. Notably, both the heterogeneous MPC algorithm of Dory and Matar [DM24] and the congested clique algorithm of Dory and Parter [DP22] rely on the emulator of Elkin and Neiman [EN18] as a central component. Skeleton Graphs. Our work adapts several ideas from Bui et al. [BCC+ 24], the most significant of which is the skeleton graph (Definition 3.1). The general skeleton graph concept refers to the notion of building a new graph over a sampled subset of the original vertices. As far as we know, [UY90, Algorithm 2.3] is the earliest application of this technique; we however refer to the particular version used in [BCC+ 24], which differs significantly from that of [UY90]. At a high level, our work involves a hierarchical construction of the skeleton graph to build a polylog-stretch low-hopbound emulator (Definition 2.2) as a key step towards constructing the SSSP oracle. We note that this manner of hierarchical construction also shares similarities with the work of Andoni, Stein, and Zhong [ASZ20]. We defer the comparisons to [BCC+ 24] and [ASZ20] to Section 3.3. From Randomised to Deterministic. A very recent work by Cho, Dory, Maus, and de Vos [CDM+ 26] introduced techniques for de-randomising randomised shortest-path algorithms in the MPC and congested clique models. Their approach is based on de-randomising hitting-set computations, and applies, in particular, to the aforementioned O(1)-approximate APSP congested clique algorithm of [BCC+ 24] and the shortest-path MPC algorithms of [DM24]. Given the similar nature of the randomisation used in our work to that of previous works, we expect that the techniques of [CDM+ 26] can be adapted to obtain deterministic variants of Theorem 1 and Theorem 2.

1.3

Organisation

In Section 2, we introduce the terminology and tools used throughout the paper. In Section 3, we provide a technical overview of our algorithms. In Section 4, we present our main results, the SSSP oracle algorithms. In Sections 5 to 7, we describe the three building blocks underlying these algorithms: constructing k-nearest hopsets, extracting k-nearest neighbourhoods, and constructing skeleton graphs, respectively. In Section A, we review the basic communication primitives for MPC algorithms. In Section B, we extend our construction to output the paths corresponding to the approximate distances.

2

Preliminaries

In this section, we present the terminology and the tools used throughout the paper.

5

2.1

Graph Notations

For a weighted graph G = (V, E), we let dG (u, v) denote the distance between vertices u and v in G; if there is no path connecting u and v, then we denote dG (u, v) = ∞. The weighted diameter of G is defined as the maximum distance between any pair of vertices, i.e., maxu,v∈V dG (u, v). We (β) write dG (u, v) to denote the distance between u and v via a path consisting of at most β edges. Unless otherwise specified, all graphs considered in this paper are assumed to be simple and undirected. Each vertex has a distinct ID of O(log n) bits. As is standard, we assume that the input graph G has positive edge weights that are polynomially bounded integers. For any edge e = {u, v} ∈ E, we denote its weight by ωG (u, v) = ω(e). As convenient shorthands, for any pair {u, v} ∈ / E with u ̸= v, we let ωG (u, v) = ∞; for any u ∈ V , we let ωG (u, u) = 0. When convenient, we may use the subscript to indicate the specific edge set under consideration. For any path P , we use ω(P ) to denote its length, defined as the sum of the weights of all edges in P . Approximations. We say that ∆ ∈ R is an a-approximation of a value d if d ≤ ∆ ≤ a · d. Similarly, we call a function δ : V × V → R ∪ { ∞ } an a-approximate distance estimate for the graph G if dG (u, v) ≤ δ(u, v) ≤ a · dG (u, v) for all pairs of vertices u, v ∈ V . k-Nearest Neighbourhoods. Consider a graph G = (V, E). For any vertex v ∈ V and positive integer k, we define NG,k (v) ⊆ V as the k-nearest neighbourhood of v, consisting of the k vertices in G that are closest to v, including v itself. We often omit G from the subscript when the graph is clear in context. We also define the edge set Ek := {{u, t} : u ∈ V ∧ t ∈ Nk (u)}

with ωEk (u, t) = dG (u, t).

We refer to Ek as the k-nearest edge set of G. In most instances throughout this work, computing the k-nearest neighbourhoods of all the vertices in G amounts to computing the k-nearest edge set of G – in such cases, we use the terms interchangeably. (h) We also consider additional useful variants of k-nearest neighbourhoods. We denote Nk (v) ⊆ V as the k-nearest h-hop neighbourhood of v, which consists of the k vertices closest to v according (h) to the distances given by the function dG . We say that Ñk (v) is an a-approximate k-nearest neighbourhood of v if there exists an a-approximate distance estimate δ for G such that Ñk (v) consists of the k vertices closest to v according to δ. Unless otherwise specified, all references to k-nearest neighbourhoods and their variants in this work assume that ties are broken by vertex ID.

2.2

Distance-Preserving Structures

Throughout this paper, we consider three types of distance-preserving structures. Definition 2.1 (Spanners). Given a graph G = (V, E), a t-spanner is a subgraph H ⊆ G over the same vertex set V such that for any two vertices u, v ∈ V , dG (u, v) ≤ dH (u, v) ≤ t · dG (u, v). 6

The parameter t is called the stretch of the spanner. Definition 2.2 (Hop-bounded Emulators). Given a graph G = (V, E), a t-stretch β-hopbound emulator is an edge set H over the vertices V such that for any two vertices u, v ∈ V , (β)

dG (u, v) ≤ dH (u, v) ≤ dH (u, v) ≤ t · dG (u, v). Definition 2.3 (k-Nearest Hopsets). Given a graph G = (V, E), a k-nearest β-hopbound hopset is an edge set H over the vertices V such that for any two vertices u, v ∈ V , dG∪H (u, v) = dG (u, v), i.e., distances are not shortened. Moreover, if u ∈ NG,k (v) or v ∈ NG,k (u), then (β)

dG∪H (u, v) = dG (u, v). Here, G ∪ H = (V, E ∪ H), where the smallest-weight edge is taken in the case of parallel edges.

2.3

Useful Tools

We identify machines in the MPC model by their integer IDs in {1, 2, . . . , M }, where M is the total number of machines. We refer to a set of machines as a contiguous segment if their IDs form a consecutive sequence. We use the following tools for various purposes throughout this work. The first tool is a constantround O(t)-spanner construction in the heterogeneous MPC model, which also trivially extends to the near-linear MPC model. Lemma 2.4 (Spanners in Heterogeneous MPC [DFK+ 21],[FHO22]). Let G = (V, E) be a weighted graph with n vertices and let t ≤ log n be a parameter. In the heterogeneous MPC model with Õ(|E|) total memory, there exists a randomised algorithm that, w.h.p., constructs an O(t)-spanner for G of size Õ(n1+1/t ) in O(1) rounds. The next tool comprises four subroutines that will be useful in the design of our MPC algorithms. At a high level, each subroutine involves constructing a tree with branching factor O(nγ ) and depth O(1/γ) over a contiguous segment of machines. Lemma 2.5 (Basic MPC Tools [DN20; GSZ11]). Consider the sublinear MPC model with Õ(|E|) total memory and O(nγ ) memory per machine. Suppose we have a contiguous segment of machines and a set of comparable items S = { x1 , x2 , . . . , xn } stored across these machines. The following tasks can be accomplished in O(1) rounds: Sorting: Sort the items in S across the contiguous segment of machines. Find Minimum: Find the minimum value in S. Prefix Sum: If S is a set of numbers, compute the value pi =

Pi

j=1 xj for each xi ∈ S.

Broadcast: Broadcast a message of size b ∈ O(nγ ) across the contiguous segment of machines.

7

2.4

A Connectivity Assumption

In this work, we will implicitly assume throughout that the input graph to our distance oracle algorithms is connected. To justify this assumption, we show that a distance oracle for disconnected graphs can be reduced to a distance oracle for connected graphs. Specifically, we do this by connecting high-weight edges between different connected components. Lemma 2.6. Let G = (V, E) be a weighted graph with n vertices, let T ∈ Ω̃(|E|), R := R(n), Q := Q(n) be functions, and let a ∈ poly(n). Suppose that in the heterogeneous MPC model with T total memory, there exists a randomised algorithm A that, when G is connected, w.h.p. constructs an a-approximate SSSP oracle in O(R) rounds which answers queries in O(Q) rounds. Then in the same model of computation, there exists another randomised algorithm A′ that, regardless if G is connected or disconnected, w.h.p. constructs an a-approximate SSSP oracle in O(R + 1) rounds which answers queries in O(Q + 1) rounds. Proof. We suppose the existence of A and describe the algorithm A′ . For readability, we describe only the essential details. Given the input graph G = (V, E), the near-linear-space machine M ∗ first chooses an arbitrary vertex z ∈ V . The entire set of incident edges on z is collected onto M ∗ in O(1) rounds using the tools from Lemma 2.5. Also using the same set of tools, we find the heaviest edge weight W of G in O(1) rounds which is communicated to M ∗ . Locally, M ∗ now adds the following additional edges to the graph G: For each vertex v ∈ V such that { z, v } ∈ / E, add the edge { z, v } with weight a(n) · W (n − 1) + 1. This constructs a new weighted graph G′ . Crucially, G′ is also a connected graph. We run the algorithm A on G′ (instead of G). This requires O(R) rounds and constructs an a(n)-approximate SSSP oracle OG′ for G′ which answers queries in O(Q) rounds. For a query vertex u, let OG′ (u)[v] be the a(n)-approximate distance from u to v returned by OG′ . We claim that u and v are connected in G if and only if OG′ (u)[v] ≤ a(n) · W (n − 1). Using this claim, we adapt OG′ into an SSSP oracle OG for the original graph G as follows: ( OG′ (u)[v] if OG′ (u)[v] ≤ a(n) · W (n − 1) OG (u)[v] := ∞ otherwise. It is quick to verify that OG satisfies the following: (1) it requires at most O(R + 1) rounds of preprocessing, and (2) it is an a(n)-approximate SSSP oracle for G that answers queries in O(Q + 1) rounds. It now suffices to justify the earlier claim. If u and v are connected in G, we then have that dG′ (u, v) = dG (u, v) ≤ W (n − 1) (as there are at most n − 1 edges in any shortest path between u and v). Therefore, we must have that OG′ (u)[v] ≤ a(n) · dG′ (u, v) ≤ a(n) · W (n − 1). Conversely, suppose that u and v are not connected in G. By the definition of G′ , we have that dG′ (u, v) ≥ a(n) · W (n − 1) + 1. Therefore, OG′ (u)[v] ≥ dG′ (u, v) ≥ a(n) · W (n − 1) + 1 > a(n) · W (n − 1). The claim follows.

3

Technical Overview

We first provide an informal, high-level overview of our SSSP oracle construction. Given the input graph G with n vertices, 8

1. Build an O(1)-spanner graph G′ of G. 2. Determine approximate k-nearest neighbourhoods for all vertices in G′ . 3. Transform the approximate k-nearest neighbourhoods into exact k-nearest neighbourhoods, building the k-nearest edge set Ek . 4. Using Ek , build the skeleton graph G′S for G′ . 5. Build an Õ(n)-sized constant-stretch spanner F for G′S , which is stored on a near-linear memory machine. 6. F and Ek together act as our distance oracle for all future distance queries. We present the technical overview as follows. We first describe the three “building blocks” in Section 3.1, which cover Steps 3 and 4 above. We then give a more precise technical description of the oracle construction in Section 3.2, with a particular focus on the construction of approximate k-nearest neighbourhoods (Step 2 above) for the heterogeneous MPC regime. We conclude with a comparison with prior work in Section 3.3.

3.1

Building Blocks

The first of the building blocks is a skeleton graph construction (Section 3.1.1), which forms the foundation of our SSSP oracle. This is supported by two additional tools: A k-nearest hopset construction and an algorithm for extracting k-nearest neighbourhoods (Section 3.1.2). 3.1.1

Skeleton Graphs

Informally, in the context of distance computation, a skeleton graph GS = (VS , ES ) is a weighted graph over a subset VS ⊆ V of vertices such that approximate distances in the original graph G can be efficiently inferred from the approximate distances in GS . In this work, we consider a specific skeleton graph definition from Bui et al. [BCC+ 24], which is based on the concept of k-nearest neighbourhoods. Recall that the k-nearest edge set Ek is defined in Section 2. Definition 3.1 (Skeleton Graphs [BCC+ 24]). Let G = (V, E) be a weighted graph with n vertices, and let k > 1 be an integer. A skeleton graph GS = (VS , ES ) is a weighted graph on a vertex set VS ⊆ V

with |VS | ≤

CS · n log k , k

where CS > 0 is a universal constant. This is subject to the following conditions: • (No shrinking distances) For any pair of vertices u, v ∈ VS , we have dGS (u, v) ≥ dG (u, v). • (Clusters as good approximations) For all u, v ∈ V such that u ∈ / Nk (v) and v ∈ / Nk (u), there exists a path P in Ek ∪ ES from u to v satisfying: (P1) The length of P is a 7-approximation of dG (u, v). (P2) The first and last edges of P belong to Ek , while all intermediate edges belong to ES . 9

• (Small edge weights) If the edge weights of G are bounded above by a function f (n), then the edge weights of GS are bounded above by g(n) := 3k · f (n). • (Connectivity) If G is connected, then so is GS . Intuitively, the path P in the above definition enables us to derive O(1)-approximate distances in the original graph G from O(1)-approximate distances in the skeleton graph GS . The approximate distances in GS can be efficiently obtained via spanners constructed using Lemma 2.4. In particular, when k ∈ nΘ(1) , the entire spanner can be stored on a machine with near-linear memory, allowing us to obtain the desired O(1)-approximate SSSP oracle. Following the definition of skeleton graphs, two questions remain: First, how do we construct the edge set Ek ; second, how do we build a skeleton graph? The former question requires the two remaining building blocks. We address the latter question in the discussion below. Existing Construction. We begin by reviewing the construction of Bui et al. [BCC+ 24] in the congested   clique model. The first step is to compute, via random sampling, a hitting set of size n log k O for the k-nearest neighbourhoods Nk (v) for all v ∈ V (i.e., a set that intersects every k k-nearest neighbourhood). These sampled vertices serve as cluster centers, and each vertex v ∈ V joins the cluster of its nearest center. Let c(v) denote the cluster center assigned to vertex v. The set of cluster centers forms the vertex set of the skeleton graph. To construct the edge set of the skeleton graph, consider all paths of the form c(u) ⇝ u ⇝ t → v ⇝ c(v),

where t ∈ Nk (u) and

{ t, v } ∈ E.

For each such path, add the edge {c(u), c(v)} to the skeleton graph, with weight equal to the total length of the path. In the case of parallel edges, retain the edge with the minimum weight. While this construction is sufficient for the congested clique algorithm of Bui et al. [BCC+ 24], it is not suitable for the MPC model, as the total number of edges can reach O(n2 /k 2 ) in the worst case, exceeding the total memory available. Namely, consider the scenario where a vertex t belongs to the k-nearest neighbourhood of every other vertex and is adjacent to all of them. In
this case, t leads to an edge between every pair of cluster centers, resulting in a total of O |VS |2 ⊆ O((n log k)2 /k 2 ) edges in the skeleton graph. Moreover, the construction of Bui et al. [BCC+ 24] relies on a sparse matrix multiplication algorithm that critically exploits the high total bandwidth of the congested clique model (i.e. O(n2 ) total memory across all machines), and therefore does not extend to the MPC model. Modified Construction. We address the issue by modifying the construction to directly include any vertex t ∈ V that would otherwise induce an excessive number of edges in the skeleton graph. Specifically, for each such t and for each candidate path of the form c(u) ⇝ u ⇝ t → v ⇝ c(v), rather than adding the edge {c(u), c(v)} to the skeleton graph, we instead add the edges {t, c(u)} and {t, c(v)}. This modification ensures that the total number of edges in the skeleton graph is bounded by Õ(|E|k 2 ). We also provide an MPC implementation that runs in O(1) rounds. Crucially, we show that this change preserves all structural guarantees required by Definition 3.1. The construction is formalized in the following lemma.

10

Lemma 3.2 (Skeleton Graph Construction). Let G = (V, E) be a connected, weighted graph with n vertices, and let k > 1 be an integer. Suppose the k-nearest edge set Ek for G is given. If k 2 ∈ O(nγ ), then in the sublinear MPC model with Õ(|E|k 2 ) total memory, there exists a randomised algorithm that w.h.p. constructs a skeleton graph GS = (VS , ES ) in O(1) rounds. We note that in all applications of Lemma 3.2 in this paper, we do not apply it on the input graph directly, but on a sparse O(1)-spanner of the input graph – this reduces the total memory requirement from Õ(|E|nγ/2 ) to Õ(|E| + n1+γ ). 3.1.2

Constructing the k-Nearest Edge Set

We now describe how to construct the k-nearest edge set Ek . However, instead of constructing Ek directly, we will show how to transform any given knowledge of the approximate k-nearest neighbourhoods into the exact k-nearest edge set Ek . Constructing the k-Nearest Hopset. The first step of the transformation is to construct a knearest hopset, based on an MPC implementation of the corresponding congested clique algorithm by Bui et al. [BCC+ 24]. The algorithm starts with an a-approximate k-nearest neighbourhood Ñk (u) for each vertex u ∈ V . By requesting the k shortest edges for each vertex in Ñk (u), vertex u can recover exact distances to a sufficiently large fraction of its true k-nearest neighbourhood Nk (u). Shortcutting paths using this distance information yields a k-nearest hopset with hopbound O(a log d), where d is the weighted diameter of the graph. Lemma 3.3 (k-Nearest Hopset). Let G = (V, E) be a connected, weighted graph with n vertices, and let k > 0 be an integer. Suppose that for every vertex u ∈ V , we are given the set {(u, t) : t ∈ Ñk (u)}, where Ñk (u) is an a-approximate k-nearest neighbourhood of u. If k 2 ∈ O(nγ ), then in the sublinear MPC model with Õ(|E| + nk 2 ) total memory, there exists a deterministic algorithm that constructs a k-nearest O(a log d)-hopbound hopset H in O(1) rounds, where d is the weighted diameter of G. Constructing the k-Nearest Edge Set. Building on the k-nearest hopset construction from Lemma 3.3, we now turn to the problem of extracting the k-nearest neighbourhoods. Specifically, given a graph G = (V, E) and a hopset with hopbound h, the goal is to compute the k-nearest (h) h-hopbound neighbourhoods Nk (u) for all vertices u ∈ V in O(log h) rounds in the MPC model. This task has been studied in the congested clique model and appears as a key subroutine in several APSP algorithms [BCC+ 24; CDK+ 21; DP22]. It can be solved via a standard graph (1) exponentiation approach. Initially, each vertex u knows its 1-hop k-nearest neighbourhood Nk (u). (2i−1 )

In iteration i, each vertex u collects the sets Nk

(2i−1 )

(t) for all t ∈ Nk

(u), which is sufficient to

(2i ) compute Nk (u). Repeating this process for O(log h) iterations yields the desired k-nearest h-hop

neighbourhoods. We show that each iteration can be implemented in O(1) rounds in the sublinear MPC model, and thus the overall procedure completes in O(log h) rounds. The result is summarised in the following lemma. Lemma 3.4 (Extracting k-Nearest Neighbourhoods). Let G = (V, E) be a connected, weighted graph with n vertices, and let k > 0 and r > 0 be integers, setting h = 2r . Suppose that k 2 ∈ O(nγ ).

11

Then, in the sublinear MPC model with Õ(|E| + nk 2 ) total memory, there exists a deterministic O(r)-round algorithm that constructs the set n  o (h) (h) u, t, dG (u, t) : u ∈ V and t ∈ Nk (u) . In this work, we apply the above lemma in two contexts. First, in conjunction with the k-nearest hopset from Lemma 3.3, it enables an efficient construction of the exact k-nearest edge set Ek , as previously discussed. Second, it allows us to extract c-approximate k-nearest neighbourhoods from a given c-stretch h-hopbound emulator. We remark that the round complexity of Lemma 3.4 constitutes one of the main bottlenecks in our overall algorithm. In particular, an improved algorithm for Lemma 3.4 would directly lead to a faster implementation in the near-linear MPC model.

3.2

Building the SSSP Oracle

In this section, we provide a technical overview of our SSSP oracle, organised in two parts. In Section 3.2.1, we describe how to construct the oracle assuming access to approximate k-nearest neighbourhoods. This part follows by combining the previously introduced building blocks in a straightforward manner. In Section 3.2.2, we address the main technical challenge: efficiently computing approximate k-nearest neighbourhoods in the heterogeneous MPC model. Our approach is based on constructing an emulator via a hierarchical application of the skeleton graph construction. We remark that in the following discussion, we hide the dependence on c and γ in the stretch terms for ease of presentation. This is justified as we consider both c and γ as constants. We treat this more carefully in the full proofs in Section 4. 3.2.1

From Approximate k-Nearest Neighbourhoods to SSSP Oracles

Using Lemmas 3.3 and 3.4, we construct the set Ek from the given approximate k-nearest neighbourhoods and apply Lemma 3.2 to build a skeleton graph GS = (VS , ES ). We then compute an O(1)-spanner of GS and store it on a machine with near-linear memory. Together, the spanner and Ek yield the desired O(1)-approximate SSSP oracle. We now describe the setup in more detail. Suppose we are given a-approximate k-nearest neighbourhoods Ñk (u) for every vertex u ∈ V , where log a = O(log log n) and k = nc/4 for some constant c > 0. We also assume |E| = O(n1+c/2 ), which can be ensured by replacing G with an O(1)-spanner, which is acceptable since it only stretches the distances by a constant factor. 1. Construct a k-nearest O(a log n)-hopbound hopset H for G using Lemma 3.3, which takes O(1) rounds. 2. Apply Lemma 3.4 to the graph G ∪ H, setting the parameter r so that 2r = h ∈ O(a log n) is at least the hopbound of the hopset. This yields the exact k-nearest neighbourhoods for all vertices in O(log(a log n)) = O(log log n) rounds and also the edge set Ek . 3. Using Ek , construct a skeleton graph GS = (VS , ES ) for G via Lemma 3.2 in O(1) rounds. 4. For a constant t ≥ 4/c, construct an O(t)-spanner F of GS with Õ(|VS |1+1/t ) ⊆ Õ(n) edges using Lemma 2.4 in O(1) rounds. Collect the spanner on a machine M ∗ with near-linear memory. Overall, the algorithm completes in O(log log n) rounds and uses Õ(n1+c ) total memory. 12

SSSP Queries. To compute an O(1)-approximate SSSP from a source vertex u ∈ V , we consider two cases: Case 1: v ∈ Nk (u) or u ∈ Nk (v). Return the exact distance ωEk (u, v) = dG (u, v). Case 2: v ∈ / Nk (u) and u ∈ / Nk (v). Return the minimum length over all paths of the form: u → s ∈ VS via an edge in Ek , followed by a path s ⇝ s′ ∈ VS in the spanner F , and then s′ → v via an edge in Ek . In Case 2, the returned value is an O(1)-approximation of the true distance dG (u, v), guaranteed by the properties of the skeleton graph. Moreover, the path lengths to all vertices v ∈ V can be computed simultaneously in O(1) rounds. In other words, using the edge set Ek and the spanner F of GS , we can answer O(1)-approximate SSSP queries in O(1) rounds. 3.2.2

Computing Approximate k-Nearest Neighbourhoods

We now describe the construction of the required a-approximate k-nearest neighbourhoods. The Near-Linear MPC Model. In the near-linear MPC model, the problem can be solved easily by constructing an O(log n)-spanner with Õ(n) edges using Lemma 2.4. This spanner can then be broadcast to all machines, allowing each machine to compute an O(log n)-approximate k-nearest neighbourhood for each vertex locally. Since the spanner construction takes only O(1) rounds, the overall round complexity for constructing the SSSP oracle is O(log log n). The Heterogeneous MPC Model. The spanner-based approach used in the near-linear MPC model does not extend to the heterogeneous regime, as we cannot afford to store a linear-sized spanner on each machine. To overcome this, we construct a 2O(log log n) -stretch, O(log log n)-hopbound emulator via a recursive application of skeleton graph constructions. This emulator is built in O(log2 log n) rounds and constitutes the main bottleneck in the overall SSSP oracle construction. Once the emulator is constructed, we apply Lemma 3.4 to extract the desired a = 2O(log log n) approximate k-nearest neighbourhoods, for k being a small polynomial in n, using an additional O(log log log n) rounds. This suffices for our purposes. The Emulator Construction. The key idea behind the emulator construction is that the spanner-based approach used in the near-linear regime still works in the heterogeneous regime when k is polylogarithmic. Once the spanner is stored on the near-linear memory machine M ∗ , it can locally compute the desired approximate k-nearest neighbourhoods for all vertices using the spanner. Since k is polylogarithmic, the total output size is nk ∈ Õ(n) and fits within the local memory of M ∗ . We apply the skeleton  graph construction to G with parameter k, obtaining a slightly smaller  n log k skeleton graph G1 with O vertices. For simplicity, in this technical overview, we assume k the bound is O(n/k). Next, we apply the same skeleton graph construction to G1 = (V1 , E1 ). The reduced
size of G31 2 2 allows us to increase the parameter to k , yielding a new skeleton graph with O |V1 |/k = O(n/k ) vertices. This, in turn, enables us to increase k even further in the next iteration. Due to the growth rate of the parameter k, the recursion terminates after O(log log n) iterations. We show that the union of the edge sets Ek across all levels of the recursion forms the desired emulator. 13

We now describe the idea more concretely. We initialize H := ∅ and proceed in iterations. At the beginning of the ith iteration, we maintain a graph Gi = (Vi , Ei ) and a parameter ki , where G0 = G and k0 = log n. We assume that ki · |Vi | ∈ O(n log n) and that the weighted diameter of Gi is bounded by poly(n). 1. We begin by sparsifying Gi by constructing an O(1)-stretch spanner G′i using Lemma 2.4, to ensure that the number of edges remains bounded. 2. Next, we construct an O(log n)-stretch spanner S of G′i with Õ(n) edges using Lemma 2.4. We store S on the machine M ∗ with near-linear memory. Since ki · |Vi | ∈ O(n log n), M ∗ can locally compute the ki -nearest neighbourhoods for all vertices in the spanner S. This yields a = O(log n)-approximate ki -nearest neighbourhoods for all vertices in Vi , and takes O(1) rounds. 3. As in Section 3.2.1, we apply Lemmas 3.3 and 3.4 to construct the edge set Eki in O(log(a log n)) ⊆ O(log log n) rounds. 4. We add Eki to the emulator edge set H. 5. Finally, we construct the skeleton graph GS for G′i and set Gi+1 := GS and ki+1 ∈ O(ki2 ). We continue the process until the graph becomes small enough that all-pairs distances can be computed locally on a single machine. A minor technical detail is that once ki reaches a small polynomial in n, we keep ki fixed in all subsequent iterations to ensure that the local memory requirements of the building blocks are satisfied. Since there are O(log log n) iterations, where each iteration takes O(log log n) rounds, the overall emulator construction completes in O(log2 log n) rounds.

3.3

Comparison with Prior Work

Comparison with [BCC+ 24]. While both our algorithm and that of Bui et al. [BCC+ 24] rely on skeleton graphs, they are used in different ways. We apply the skeleton graph construction recursively to build an emulator with small stretch and hopbound. In contrast, the O(log log √ log n)round congested clique algorithm of Bui et al. [BCC+ 24] uses a skeleton graph with k ∈ 2Θ( a) as an √ intermediate step to improve an a-approximate APSP to an O( a)-approximate one in O(1) rounds – starting with a = O(log n), they repeat this for O(log log log n) iterations to obtain constantapproximate APSP. Their approach is infeasible in our setting for two main reasons. First, constructing such a skeleton graph in O(1) rounds requires a fast k-nearest neighbourhood computation algorithm that √ leverages the high total bandwidth of the congested clique model. Second, obtaining the O( a)√ approximation relies on broadcasting an O( a)-spanner of the skeleton graph to all machines, which demands linear local memory per machine. Comparison with [ASZ20]. In the work of Andoni, Stein, and Zhong [ASZ20], they demonstrated a similar recursive construction of a hop-bounded emulator in the PRAM model of computation using a structure known as a subemulator (as opposed to our use of the skeleton graph). Although both Andoni, Stein, and Zhong [ASZ20] and our work employ similar recursive constructions of emulators, the motivations for the recursion and the roles played by the resulting 14

emulators differ substantially. In Andoni, Stein, and Zhong [ASZ20], the emulator is used to construct Bourgain’s embedding, metric tree embeddings, and low-diameter decompositions, whereas in our work it is used to find the required a-approximate k-nearest neighbourhoods. Moreover, Andoni, Stein, and Zhong [ASZ20] adopt the recursive construction, in which a smaller vertex set permits a larger choice of k, to satisfy the work-efficiency constraint. In contrast, we arrive at the same condition to ensure that the k-nearest neighbourhoods of all vertices can be stored on a single machine with near-linear memory.

4

O(1)-Approximate SSSP Oracles

In this section, we present the main algorithms of the paper in detail: O(1)-approximate SSSP oracles with O(1) query time. The construction requires O(log log n) rounds in the near-linear MPC model and O(log2 log n) rounds in the heterogeneous MPC model. We first state the following lemma, which is a tool to “convert” approximate k-nearest neighbourhoods to exact k-nearest neighbourhoods. Lemma 4.1 (Approximate to Exact k-Nearest). Let G = (V, E) be a connected, weighted graph with n vertices, and let integer k > 0 be a parameter. Suppose that for every vertex u ∈ V , we are given the set {(u, t) : t ∈ Ñk (u)}, where Ñk (u) is an a-approximate k-nearest neighbourhood of u. Given that k 2 ∈ O(nγ ), in the sublinear MPC model with Õ(|E|+nk 2 ) total memory, there exists a deterministic algorithm for constructing the k-nearest edge set Ek for G in O(log log d + log a) rounds, where d is the weighted diameter of G. Proof. We first apply Lemma 3.3 to obtain a k-nearest (Ca log d)-hopbound hopset H in O(1) rounds, where C is a suitable constant. We now apply Lemma 3.4 on the graph G ∪ H, setting the parameter r such that 2r = h ≥ Ca log d. This constructs the h-hop k-nearest neighbourhoods (h) NG∪H,k (u) for all vertices u ∈ V in G ∪ H. We recall by the definition of k-nearest hopsets (Definition 2.3) that for all vertices u, v ∈ V such that v ∈ NG,k (u), we have (h)

(Ca log d)

dG∪H (u, v) ≤ dG∪H

(u, v) = dG (u, v).

Moreover, H does not shorten distances in G, i.e., dG∪H (u, v) = dG (u, v) for vertex pairs u, v ∈ V . This implies that the k-nearest neighbourhood of any vertex in G ∪ H is the same as that in G (noting that in both cases, we are breaking ties by vertex ID). (h) Altogether, this implies NG∪H,k (u) = NG,k (u) for all u ∈ V , and therefore we have equivalently constructed the k-nearest edge set Ek , as desired. Constructing the hopset H requires Õ(|E| + nk 2 ) total memory, while extracting out the knearest neighbourhoods requires Õ(|G ∪ H| + nk 2 ) total memory. Therefore, our entire algorithm only requires Õ(|E| + nk 2 ) total memory, and runs in O(r) = O(log(a log d)) = O(log a + log log d) rounds.

4.1

From Approximate k-Nearest Neighbourhoods to SSSP Oracles

In this section, we aim to prove the following lemma. Notice that while the lemma is stated explicitly for the heterogeneous regime, it trivially extends to the near-linear regime with the same total memory and round complexity. In subsequent sections, we show how to relax our input assumptions depending on the MPC regime being considered. 15

We remark that the restriction on the edge set |E| ∈ Õ(n1+c/2 ) is only to ensure that the additional total memory as stated in Theorem 1 and Theorem 2 is represented as an additive term n1+c as opposed to a multiplicative term nc , i.e., Õ(|E| + n1+c ) instead of Õ(|E|nc ) total memory. Namely by choosing k = nc/4 as the parameter for the k-nearest neighbourhoods, we ensure that the skeleton graph construction of Lemma 3.2 requires only Õ(|E|k 2 ) = Õ(n1+c ) total memory. Lemma 4.2. Let G = (V, E) be a connected, weighted graph with n vertices, and let c > 0 be a constant such that |E| ∈ Õ(n1+c/2 ). Suppose that for every vertex u ∈ V , we are given the set {(u, t) : t ∈ Ñk (u)}, where Ñk (u) is an a-approximate k-nearest neighbourhood of u with k = nc/4 . Given that c ≤ γ, in the heterogeneous MPC model with Õ(n1+c ) total memory, there exists a randomised algorithm that w.h.p. constructs an O(1/c)-approximate SSSP oracle in O(log a + log log n) rounds. Every subsequent SSSP query can then be answered in O(1) rounds. The key idea is to construct the skeleton graph GS = (VS , ES ) for the input graph G, and subsequently construct an O(1/c)-stretch spanner F for GS . We will show by an appropriate choice of parameters that F can be made linear-sized, and therefore can be stored on a single near-linear memory machine. The spanner F and edge set Ek are then sufficient to handle any future SSSP queries in O(1) rounds. 4.1.1

Algorithm Description

As input, we are given the weighted n-vertex graph G = (V, E), whose edge weights are polynomially-bounded (i.e., ωG (u, v) ∈ poly(n) for all { u, v } ∈ E). Step 1: Get Exact k-Nearest. Denote k = nc/4 . By the input assumptions, we have aapproximate k-nearest neighbourhoods Ñk (u) for all vertices u ∈ V . Since k 2 = nc/2 ≤ nγ , this allows us to find the exact k-nearest neighbourhoods for all vertices by applying Lemma 4.1 on G. This constructs the k-nearest edge set Ek for G. Denoting the weighted diameter of G as d, we observe that this step runs in O(log a+log log d) rounds. The total memory required is Õ(|E| + nk 2 ) = Õ(n1+c/2 ), which fits within our total memory constraints. Step 2: Construct Skeleton Graph. We apply Lemma 3.2 on G with k = nc/4 to obtain the skeleton graph GS = (VS , ES ). This step runs in O(1) rounds. We note that the total memory needed is Õ(|E|k 2 ) = Õ(n1+c/2 · nc/2 ) = Õ(n1+c ), which fits within our total memory constraints. Step 3: Sparsify GS . We further sparsify GS into a spanner F = (VS , EF ). Namely, we apply Lemma 2.4 to obtain an O(4/c)-spanner of size |EF | ∈ Õ(|VS |1+c/4 ) in O(1) rounds. For now, we may assume that |EF | ∈ Õ(n); we justify this assumption in Lemma 4.3. Step 4: Storing the Spanner. We store the spanner F on the single near-linear memory machine M ∗ . This requires O(1) rounds. Our final SSSP oracle consists of the following: • The edge set Ek , stored arbitrarily across the machines. • The graph F , stored entirely on the machine M ∗ . This concludes our construction. 16

4.1.2

Correctness

We first justify our claim that the spanner F is sufficiently small to store in a single near-linear memory machine. Lemma 4.3. For any constant c > 0, the size of the graph F is bounded by |EF | ∈ Õ(n). Proof. By the definition of the skeleton graph in Definition 3.1, we may denote the number of
vertices in the skeleton graph GS as |VS | ≤ (CS · n log k)/k = CS (c/4) n1−(c/4) · log n , where k = nc/4 and CS is the constant defined in Definition 3.1. Additionally by Step 3 of the algorithm, we may denote the number of edges in the graph F as |EF | ≤ C1 · |VS |1+c/4 logC2 n, where C1 , C2 are suitable constants. We find that |EF | ≤ C1 · |VS |1+c/4 logC2 n   CS · c log n 1+c/4  1−(c/4) 1+c/4 ≤ C1 · · n logC2 n 4   CS · c log n 1+c/4 1−(c/4)2 = C1 · ·n logC2 n. 4 Since we treat all other variables as constants except for n, we have that |EF | ∈ n·polylog(n) ⊆ Õ(n) as desired. We next show the round complexity of the algorithm. Lemma 4.4. The above algorithm runs in O(log a + log log n) rounds. Proof. From the algorithm description, we observe that except for Step 1, all remaining steps run in O(1) rounds. It therefore suffices to show that Step 1 runs in O(log a + log log n) rounds. Denoting g(n) ∈ poly(n) as the upper bound of the edge weights in G, we find that the weighted diameter of G is at most d = (n − 1) · g(n) ∈ poly(n) as any shortest path in G has at most n − 1 edges. Therefore, Step 1 runs in O(log a + log log d) = O(log a + log log n) rounds as claimed. Answering Queries. For any given source vertex u ∈ V and any other vertex v ∈ V , we consider all paths constructed as follows: • u → x ∈ VS using an edge in Ek , • x ⇝ y ∈ VS using a path in F , and lastly, • y → v using another edge in Ek . Given that v ∈ / Nk (u) and u ∈ / Nk (v), we show by properties (P1) and (P2) in Definition 3.1 there must exist such a path that witnesses an O(1/c)-approximation of the distance dG (u, v). More concretely, for any source vertex u ∈ V , consider the distance estimate δu : V → R, defined as follows: δu (v) = min (ωEk (u, x) + dF (x, y) + ωEk (y, v)) . x,y∈VS

We first show an upper bound for the estimate δu . 17

Lemma 4.5. For all vertices v ∈ V such that v ∈ / Nk (u) and u ∈ / Nk (v), the estimate δu (v) is at most O(1/c) · dG (u, v). Proof. We first consider the path P from u to v which has the properties (P1) and (P2) as defined in Definition 3.1, and denote P as u → u∗ ⇝ v ∗ → v. Additionally, we denote the edges u → u∗ and v ∗ → v as e1 and e2 respectively, and denote the subpath from u∗ ⇝ v ∗ in P as Q. Recall from property (P1) that ω(P ) ≤ 7 · dG (u, v). Moreover, recall from property (P2) that e1 , e2 ∈ Ek , and that Q is contained entirely in the graph GS . In particular, there must exist a path Q′ from u∗ to v ∗ in F such that ω(Q′ ) ≤ C(4/c) · dGS (u∗ , v ∗ ) (where C is a suitable constant). We are therefore able to bound δu (v) as δu (v) ≤ ω(e1 ) + ω(Q′ ) + ω(e2 ) ≤ ω(e1 ) + C(4/c) · dGS (u∗ , v ∗ ) + ω(e2 ) ≤ ω(e1 ) + C(4/c) · ω(Q) + ω(e2 ) ≤ C(4/c) · (ω(e1 ) + ω(Q) + ω(e2 )) = C(4/c) · ω(P ) ≤ 7C(4/c) · dG (u, v) The desired claim follows. We next show how to compute the estimates δu . Since the algorithm itself does not require any new techniques, we only emphasise the important points for the sake of presentation. Lemma 4.6. There exists a deterministic algorithm for constructing the values δu (v) for all v ∈ V in O(1) rounds. Proof. Computation of the values δu (v) is broken up into two parts: For every vertex y ∈ VS , we first compute the values ∆u (y) = min (ωEk (u, x) + dF (x, y)) , x∈VS

which describe the length of the path u → x ⇝ y. Subsequently, for every vertex v ∈ V , we compute the values ∆′u (v) = min (∆u (y) + ωEk (y, v)) , y∈VS

which now fully describe the length of the path u → x ⇝ y → v. By definition, we observe that ∆′u (v) = δu (v) for all vertices v ∈ V . We now describe the MPC algorithm: For readability, we describe only the essential details. Below, we recall that M ∗ refers to the single near-linear memory machine. 1. For every vertex x ∈ VS such that { u, x } ∈ Ek , we send the value (x, ωEk (u, x)) to the machine M ∗ . Observe that there are at most n such values, and therefore we have sufficient local memory in M ∗ . This requires O(1) rounds. 2. For every vertex y ∈ VS , M ∗ locally computes the values ∆u (y). This requires no communication rounds. 3. For every vertex y ∈ VS and v ∈ V such that { y, v } ∈ Ek , we label the edge { y, v } with the value ∆u (y). Using the MPC tools in Lemma 2.5 (namely sorting and broadcasting), this requires O(1) rounds. 18

4. For every vertex v ∈ V , we now compute the values ∆′u (v). Using the MPC tools in Lemma 2.5, this also requires O(1) rounds. Overall, we require only O(1) rounds as claimed. We now summarise the previous two results in the following lemma. Lemma 4.7. Given the edge set Ek stored across the machines and the spanner F stored entirely on the machine M ∗ , we can answer O(1/c)-approximate SSSP queries in O(1) rounds. Proof. For a given SSSP query u ∈ V , we first construct the values δu (v) for all vertices v ∈ V in O(1) rounds using Lemma 4.6. For every vertex v ∈ V , we separate them into two cases: Case 1: v ∈ Nk (u) or u ∈ Nk (v). By definition of Ek , there must exist an edge { u, v } ∈ Ek . It therefore suffices to return the edge weight ωEk (u, v) = dG (u, v). Case 2: v ∈ / Nk (u) and u ∈ / Nk (v). We return the value δu (v). By Lemma 4.5, we have that δu (v) ≤ O(1/c) · dG (u, v). Additionally, for any vertices x, y ∈ VS , we have dF (x, y) ≥ dGS (x, y) ≥ dG (x, y) by definition of the skeleton graph in Definition 3.1. Thus, we necessarily have that δu (v) ≥ dG (u, v) as well. In other words, it suffices to return the value min(ωEk (u, v), δu (v)) for all vertices v ∈ V , which always gives an O(1/c)-approximation of the distance dG (u, v) as desired. The Final Proof. We summarise this section on correctness with the following proof for Lemma 4.2. Proof of Lemma 4.2. We execute the algorithm described in Section 4.1.1 to construct the edge set Ek and the spanner graph F , the latter of which is stored on the single near-linear machine M ∗ . By Lemma 4.4, this requires O(log a + log log n) rounds. Furthermore, from the algorithm description, observe that the algorithm requires only Õ(n1+c ) total memory. Lastly applying Lemma 4.7, we find that this construction suffices as an O(1/c)-approximate SSSP oracle with a query time of O(1) rounds.

4.2

The Near-Linear MPC Model

In this section, we aim to prove Theorem 1. Namely, we will describe an algorithm for constructing O(log n)-approximate k-nearest neighbourhoods for all vertices, from which a direct application of Lemma 4.2 will give our desired claim. Finding Approximate Neighbourhoods. In order to construct O(log n)-approximate neighbourhoods, we construct an O(log n)-spanner of near-linear size which can be done in O(1) rounds. The entire spanner can be stored on every machine, which enables us to determine the k-nearest neighbourhoods of every vertex in the spanner – these suffice as O(log n)-approximate k-nearest neighbourhoods for the original graph. We formalise this idea in the following lemma.

19

Lemma 4.8. Let G = (V, E) be a connected, weighted graph with n vertices and let integer k > 0 be a parameter. In the near-linear MPC model with Õ(|E| + nk) total memory, there exists a randomised algorithm that w.h.p. constructs the set { (u, t) : u ∈ V ∧ t ∈ Ñk (u) } where Ñk (u) is an O(log n)-approximate k-nearest neighbourhood of u. This algorithm runs in O(1) rounds. Proof. Using Lemma 2.4 with t = log n, we construct an O(log n)-spanner H of size Õ(n) in O(1) rounds. We collect the spanner H onto a single machine, which we then broadcast to every machine using Lemma 2.5. In other words, after O(1) rounds, every machine now knows the entire spanner H. What remains is to construct the k-nearest neighbourhood Nk (u) of every vertex u ∈ V in the spanner H, which suffices as our O(log n)-approximate k-nearest neighbourhoods in G. This is done by a delegation of tasks: The machine with ID 1 determines the neighbourhoods for the first n/k vertices, the machine with ID 2 determines the neighbourhoods for the next n/k vertices, and so on. Since the size of each set |Nk (u)| ≤ k by definition, this requires only O(n) memory per machine. Moreover, we only need O(nk) total memory to fully compute the sets Nk (u) for all n vertices, and therefore the total memory of Õ(|E| + nk) suffices. Additionally, since only local computation is needed, this requires no rounds of communication. We are now ready to prove Theorem 1. By applying Lemma 4.8 and subsequently Lemma 4.2, we get the desired result. Proof of Theorem 1. By Lemma 2.6, we may assume that G is a connected graph. We first apply the spanner construction in Lemma 2.4 (setting t = 2/c) to construct an O(2/c)-spanner G′ for G of size Õ(n1+c/2 ) in O(1) rounds. We now apply Lemma 4.8 on G′ to construct a = O(log n)approximate k = nc/4 -nearest neighbourhoods Ñk (u) for all vertices u ∈ V in G′ using another O(1) rounds. Lastly, we apply Lemma 4.2, which constructs an O(1/c)-approximate SSSP oracle for G′ in O(log a + log log n) = O(log log n) rounds. In total, we require Õ(|E| + n1+c ) memory across all steps. Since G′ is an O(2/c)-spanner for G, an O(1/c)-approximate SSSP oracle for G′ directly gives an O(1/c2 )-approximate SSSP oracle for G, and we are done.

4.3

The Heterogeneous MPC Model

Similar to the near-linear MPC regime, in this section we propose a fast method for constructing approximate k-nearest neighbourhoods, which together with Lemma 4.2, gives the final oracle construction. However, instead of constructing an O(log n)-spanner that is distributed to all machines, we instead construct a (2/γ)O(log log n) -stretch O(log log n)-hopbound emulator, which we show can be done in O(log2 log n) rounds. On this emulator we apply Lemma 3.4 to obtain (2/γ)O(log log n) approximate k-nearest neighbourhoods. We will show that this approximation ratio is sufficient for us to apply Lemma 4.2 and construct the SSSP oracle using O(log2 log n) rounds overall. High Level Idea. We iteratively construct a series of skeleton graphs G = G0 , G1 , G2 , . . . until the final skeleton graph Gℓ is small enough that all-pairs distances can be determined entirely locally. The edges of our emulator H then consist of the following: • The ki -nearest edge sets Eki taken from each graph Gi . • The all-pairs distances taken from the final graph Gℓ . 20

By choosing an appropriate sequence of polynomially increasing { ki }, we show that each iteration requires only O(log log n) rounds and that we require at most ℓ ∈ O(log log n) iterations. Consequently, we show that H is a (2/γ)O(log log n) -stretch, O(log log n)-hopbound emulator for the input graph G which can be constructed in O(log2 log n) rounds. Before stating the lemma, there are some minor implementation details to take note of: • We sparsify the skeleton graph Gi into a spanner G′i at the start of each iteration. This is to ensure that the number of edges in G′i is well-bounded. As long as the spanner also maintains a constant approximation of distances, this will not affect the stretch analysis of the algorithm up-to a constant factor (in the exponent of the stretch term). • The sequence { ki } increases polynomially until it reaches a small polynomial in n. Namely, once k ∈ nO(γ) , we maintain k at this value until the termination condition. This is to ensure we never exceed the local computation capabilities of the machines. Following from the above discussion, we will now prove the following lemma. Lemma 4.9. Let G = (V, E) be a connected, weighted graph with n vertices. In the heterogeneous MPC model with Õ(|E| + n1+γ ) total memory, there exists a randomised algorithm that w.h.p. constructs a (2/γ)O(log log n) -stretch, O(log log n)-hopbound emulator H in O(log2 log n) rounds. We first state the algorithm description in Section 4.3.1 before showing the correctness of the algorithm in Section 4.3.2. 4.3.1

Algorithm Description

As input, we are given the weighted n-vertex graph G = (V, E), whose edge weights are initially polynomially-bounded. We begin with G0 = G and an empty edge set H = ∅. We first define the sequence { ki } for all integers i ∈ { 0, 1, 2, . . . } recursively as follows: k0 = log n,  1.99  ki−1 γ/4 ki = min ,n , CS where CS is the constant defined in Definition 3.1. During iteration i ∈ { 0, 1, 2 . . . }, we start with the graph Gi = (Vi , Ei ) and parameter ki . Assume that ki · |Vi | ∈ O(n log n); we justify this assumption in Lemma 4.10. We also assume that Gi is connected; this is justified in Lemma 4.11. Lastly, we may assume that |Vi | ≤ n; this is clear in the following algorithm description. The edges of Gi are stored arbitrarily across all the machines. Step 1: Sparsify Gi . We first sparsify Gi into a spanner graph G′i = (Vi , Ei′ ). Namely, we apply Lemma 2.4 on Gi with t = 2/γ to obtain a C(2/γ)-spanner of size |Ei′ | ∈ Õ(n1+γ/2 ) in O(1) rounds, where C is a suitable constant. In all subsequent steps, we will work directly with the graph G′i rather than Gi . Step 2: Get Approximate ki -Nearest. Our goal for this step is to obtain O(log n)-approximate ki -nearest neighbourhoods for all vertices in Vi . We accomplish this in the following manner: 1. We first apply Lemma 2.4 on G′i with t = log |Vi | to obtain an O(log |Vi |) ⊆ O(log n)spanner S of size Õ(|Vi |) ⊆ Õ(n) in O(1) rounds. 21

2. Since the size of S is Õ(n), we can collect the spanner S onto the single near-linear memory machine M ∗ . 3. Locally, M ∗ constructs the ki -nearest neighbourhoods Nki (u) for every vertex u ∈ Vi in the spanner S – these suffice as O(log n)-approximate ki -nearest neighbourhoods in the graph G′i . By our previous assumption, we have ki · |Vi | ∈ O(n log n), and this therefore fits within the local memory constraints of M ∗ . At the end of this step, we now have O(log n)-approximate ki -nearest neighbourhoods Ñki (u) for all vertices u ∈ Vi . This step runs in O(1) rounds. Step 3: Get Exact ki -Nearest. Now that we have constructed a = O(log n)-approximate ki nearest neighbourhoods, we can find the exact ki -nearest neighbourhoods for all vertices in Vi . Namely, since ki2 ≤ nγ/2 ≤ nγ , we can apply Lemma 4.1 on G′i with parameter k = ki . This constructs the ki -nearest edge set Eki for G′i . Denoting di as the weighted diameter of G′i , this step runs in O(log a + log log di ) ⊆ O(log log n + log log di ) rounds. This step requires Õ(|Ei′ | + nki2 ) = Õ(n1+γ/2 ) total memory. Step 4: Add Edges to H. We add the edge set Eki to H. That is, H := H ∪ Eki . Step 5: Construct Skeleton Graph. We apply Lemma 3.2 on G′i (with k = ki ) to obtain the skeleton graph GS = (VS , ES ). We set Gi+1 := GS and proceed to the next iteration. This step runs in O(1) rounds. This step requires Õ(|Ei′ |ki2 ) ⊆ Õ(n1+γ/2 · nγ/2 ) = Õ(n1+γ ) total memory. Termination. We terminate at iteration ℓ once the graph Gℓ = (Vℓ , Eℓ ) is sufficiently small such that |Vℓ |2 ∈ O(n). We collect Gℓ onto the single near-linear memory machine M ∗ , which determines all-pairs distances for vertices in Gℓ . An edge for every pair of vertices in Vℓ is then added into the edge set H with the shortest-path distances as the edge weights. (i.e., H := H ∪{ { u, v } : u, v ∈ Vℓ } with edge weights dGℓ (u, v)). This concludes the construction, and the final edge set H is our emulator. 4.3.2

Correctness

We first justify our claims that ki |Vi | = O(n log n) and Gi is connected for all iterations i. We may assume that n is sufficiently large such that ki0.01 ≥ log ki always. Lemma 4.10. For all i ∈ { 0, 1, 2, . . . }, we have ki |Vi | ≤ n log n. Proof. We prove by induction on i. For the base case i = 0, we have k0 = log n and |V0 | = n, and therefore k0 |V0 | = n log n as desired. Proceeding to the inductive case: Suppose the claim holds for iteration i = j. Recalling Step 5 of the algorithm and the skeleton graph definition in Definition 3.1, we observe that |Vj+1 | ≤ (CS |Vj | log kj )/kj . Additionally, we have that kj+1 ≤ kj1.99 /CS by construction. Therefore, applying our induction hypothesis, kj1.99 kj+1 |Vj+1 | ≤ CS



CS |Vj | log kj kj



≤ kj1.99 22

|Vj |kj0.01 kj

! = kj |Vj | ≤ n log n.

Lemma 4.11. For all i ∈ { 0, 1, 2, . . . }, the graph Gi is connected. Proof. This is proved straightforwardly using induction. In the base case, we have that G0 is connected by the input assumptions. In the inductive case, supposing Gj is connected for some j ≥ 0, the properties of spanners and skeleton graphs (Definition 3.1) ensure that G′j is connected, and therefore Gj+1 is also connected. Organisation. For the remainder of the section on correctness, it is convenient to describe the algorithm in terms of phases. In particular, we define the first phase and second phase as follows: First Phase: This phase consists of the iterations where ki < nγ/4 . Second Phase: This phase consists of the remaining iterations where ki = nγ/4 , up until iteration i = ℓ when the termination condition is satisfied. In particular, denote i = ℓ∗ as the first iteration for which kℓ∗ = nγ/4 . We present the proof of correctness in three parts: • We first show that the algorithm terminates in O(log log n) iterations. In particular, we will show that the first phase requires O(log log n) iterations while the second phase only requires O(1/γ) iterations. • We next show that each iteration runs in O(log log n) rounds. The crux of the argument is to show that for both the first and second phases, the edge weights of all graphs Gi are bounded by poly(n). • Lastly, we show that H is indeed a (2/γ)O(log log n) -stretch and O(log log n)-hopbound emulator for the input graph G. For convenience and ease of presentation, we assume that the constant CS defined in Definition 3.1 is at least unity, i.e., CS ≥ 1; the case in which CS < 1 is argued similarly. Number of Iterations. We first argue that the first phase requires only O(log log n) iterations. Lemma 4.12. ℓ∗ ∈ O(log log n). Proof. Let p = 1.99. By the definition of ki , observe that for all iterations i < ℓ∗ , we have  ki =

1 CS

 pi −1 p−1

pi

· (log n)

" ≥

1 CS

 1

p−1

#pi · (log n)

,

using the fact that CS ≥ 1. Therefore, after " # 1 γ log n imin = · log ∈ O(log log n) 1/(1−p) log p 4 log(C log n) S

iterations, we necessarily have that kimin ≥ nγ/4 . It follows that ℓ∗ ∈ O(log log n) as claimed.

23

Proceeding to the second phase, observe that the number of vertices reduces roughly by a factor of nγ/4 between iterations. Accounting for the additional log factor, we first provide an upper bound on the number of vertices Vi . Subsequently, we show that this phase requires only O(1/γ) iterations. Lemma 4.13. For all i ∈ { 0, 1, 2 . . . , ℓ − ℓ∗ }, we have that  γ i · n1−(iγ/4) logi n, |Vi+ℓ∗ | ≤ CSi 4 where CS is the constant as defined in Definition 3.1. Proof. We prove by induction on i. In the base case of i = 0, we have |Vℓ∗ | ≤ n as expected. Consider now the inductive case: Suppose the claim holds for i = j. Recalling the skeleton graph definition in Definition 3.1, we observe that |Vj+1+ℓ∗ | ≤ (CS · |Vj+ℓ∗ |/kj+ℓ∗ ) log kj+ℓ∗ . Since we are in the second phase, we also have kj+ℓ∗ = nγ/4 . This allows us to invoke our induction hypothesis to obtain " # |Vj+ℓ∗ | log(nγ/4 ) |Vj+1+ℓ∗ | ≤ CS nγ/4 " #    j log(nγ/4 ) j γ 1−(jγ/4) j · CS ≤ CS ·n log n 4 nγ/4  γ j+1 = CSj+1 · n1−(j+1)γ/4 logj+1 n 4 as claimed. We are now ready to bound the number of iterations in the second phase. Lemma 4.14. After i ∈ O(1/γ) iterations in the second phase, we have |Vi+ℓ∗ | ∈ O(n1/2 ). Proof. Observe that the terms (γ/4)i and logi n (in Lemma 4.13) are both asymptotically smaller than nε·i , for any constant ε > 0. More concretely, we have O(CSi · (γ/4)i · logi n) ⊆ O(nε·i ) for any ε > 0. Therefore, we may rewrite the bound in Lemma 4.13 as |Vi+ℓ∗ | ∈ O(n1−(γ/4−ε)·i ). Fixing say, ε = γ/8, we get that after i ∈ O(1/[2(γ/4 − ε)]) = O(1/γ) iterations in the second phase, we necessarily have |Vi+ℓ∗ | ∈ O(n1/2 ). We are now ready to show that the entire algorithm terminates in O(log log n + 1/γ) iterations. Namely, since the first phase requires O(log log n) iterations (Lemma 4.12) and the second phase requires O(1/γ) iterations (Lemma 4.14), we get the desired result. Lemma 4.15. The entire algorithm runs in O(log log n) iterations. Proof. By Lemma 4.12, we observe that the first phase runs in O(log log n) iterations. Additionally, by Lemma 4.14, we observe that after O(1/γ) iterations in the second phase, the termination condition is satisfied. Therefore in total, we require O(log log n + 1/γ) ⊆ O(log log n) iterations across the entire algorithm. 24

Round Complexity. We first bound the edge weights of the graphs { Gi } in the first phase. We do this in the following manner: We first derive a crude bound for the edge weights (Lemma 4.16), and thereafter a bound for the values { ki } (Lemma 4.17). Finally, this enables us to obtain a good bound for the edge weights in the first phase, where we show that di ∈ poly(n) (Lemma 4.18). Suppose the initial weights of the graph G = G0 are bounded above by the function g0 (n) = poly(n). We begin with a crude, almost trivial bound for the edge weights. Note that in the following lemma, our induction begins with i = 1 instead of i = 0 for convenience. Lemma 4.16. For all i ∈ { 1, 2, . . . , ℓ∗ }, the weights of the graph Gi are bounded above by the function   i−1 Y gi (n) =  3kj  · g0 (n). j=0

Proof. We prove by induction on i. In the base case i = 1, recall that G1 is a skeleton graph of G′0 . Since the edge weights of G′0 are bounded above by g0 (n), recalling Definition 3.1, we find that the function g1 (n) = 3k0 · g0 (n) is a suitable upper bound for the weights of G1 . The inductive case works similarly: Suppose the claim holds for i = j. Since Gj+1 is a skeleton graph of G′j , we have that the weights of Gj+1 are bounded above by the function gj+1 (n) = 3kj · gj (n). Invoking our induction hypothesis, we therefore get the desired claim. We now provide a bound for the values { ki } in the first phase. Roughly speaking, we work backwards: Rather than starting our induction with k0 = log n, we start our induction instead with kℓ∗ −1 ≤ nγ/4 . This allows us to express our bound for ki in terms of a small polynomial in n, which will be useful later on. Lemma 4.17. Let p = 1.99, and denote Si as the geometric sum of i terms with common ratio and initial term 1/p. For i ∈ { 0, 1, 2 . . . , ℓ∗ − 1 }, we have S∗

ki ≤ CS ℓ −1−i · (nγ/4 )(1/p) 1/(p−1)

As a direct consequence, this implies that ki ≤ CS

ℓ∗ −1−i

.

· (nγ/4 )(1/p)

ℓ∗ −1−i

.

Proof. We prove by induction on i, starting with i = ℓ∗ − 1. For the base case i = ℓ∗ − 1, we get that kℓ∗ −1 ≤ nγ/4 as S0 = 0, which agrees with the definition of { ki }. Proceeding to the inductive case: Suppose the claim holds for i = j. We recall from our definition of kj that kj−1 = (CS kj )1/p . Therefore invoking our induction hypothesis, we have that 1/p

kj−1 = (CS kj )1/p ≤ CS

h S i ℓ∗ −1−j 1/p ℓ∗ −1−(j−1) S∗ ∗ · CS ℓ −1−j (nγ/4 )(1/p) = CS ℓ −1−(j−1) (nγ/4 )(1/p) ,

as CS ≥ 1 by assumption. Since 1/p < 1, we have that as i → ∞, Si converges to 1/(p − 1) by property of the geometric sum. In other words, we have that S∗

ℓ∗ −1−i

ki ≤ CS ℓ −i−1 · (nγ/4 )(1/p) for all i ∈ { 0, 1, 2, . . . , ℓ∗ − 1 }.

25

1/(p−1)

≤ CS

· (nγ/4 )(1/p)

ℓ∗ −1−i

In the following lemma, we show that the edge weights in the first phase are polynomial in n. This makes use of our bound for ki in Lemma 4.17, which we expressed in terms of nγ/4 . The key observation is that multiplying each ki successively results in an additive effect in the exponent of n. In particular, the exponent of n follows a geometric series that converges to a constant value, which shows the desired claim. With this lemma, we conclude our analysis of the first phase. Lemma 4.18. Let p = 1.99. For all i ∈ { 0, 1, 2 . . . , ℓ∗ }, the weights of the graph Gi are bounded above by the function  ∗ 1/(p−1) ℓ g ∗ (n) = 3CS npγ/[4(p−1)] g0 (n) ∈ poly(n). Proof. In order to bound the weights for all the graphs in the first phase, it suffices to bound the function gℓ∗ (n), as defined in Lemma 4.16. Applying our upper bounds on ki in Lemma 4.17, we have that   ! ∗ −1 ∗ −1 ℓY  ℓ∗ ℓY ∗ −1−i ℓ 1/(p−1) gℓ∗ (n) =  3kj  · g0 (n) ≤ 3CS (nγ/4 )(1/p) · g0 (n). j=0

i=0

Notice that the exponent for the term (nγ/4 ) is a geometric sum with the common ratio 1/p and initial term of 1. Since 1/p < 1, this sum converges to p/(p − 1) at infinity. Therefore, we may further bound gℓ∗ (n) with ∗

g (n) ≤ g (n) = ℓ∗



∗ 1/(p−1) ℓ 3CS npγ/[4(p−1)] g0 (n).

Since ℓ∗ ∈ O(log log n) by Lemma 4.12, γ ≤ 1 and the remaining variables (except for n) are treated as constants, we find that g ∗ (n) ∈ poly(n) as desired. We now proceed to the analysis of the edge weights in the second phase. The analysis of this phase is relatively simpler compared to the first: There are only a constant number of iterations in the second phase (Lemma 4.14) and the weights increase by at most a factor of O(n) between iterations. Since we have shown that the first graph in the second phase Gℓ∗ has polynomiallybounded weights (Lemma 4.18), we therefore have that the edge weights throughout the second phase must also be polynomially-bounded. Lemma 4.19. Suppose the weights of the graph Gℓ∗ are bounded above by the function g ∗ (n). Then, for all i ∈ { 0, 1, 2, . . . , ℓ − ℓ∗ }, the weights of the graph Gi+ℓ∗ are bounded above by the function  i gi+ℓ∗ (n) = 3nγ/4 · g ∗ (n). Proof. We prove by induction on i. In the base case of i = 0, we have gℓ∗ (n) = g ∗ (n) as expected. Consider now the inductive case: Suppose the claim holds for i = j. Recalling Definition 3.1, we observe that the function gj+1+ℓ∗ (n) := 3kj+ℓ∗ · gj+ℓ∗ (n) = 3nγ/4 · gj+ℓ∗ (n) is a suitable upper bound for the weights in Gj+1+ℓ∗ . Applying our induction hypothesis, we then have gj+1+ℓ∗ (n) = (3nγ/4 )j+1 · g ∗ (n) as claimed. With this next lemma, we claim the edge weights of all the graphs { Gi } are polynomiallybounded. 26

Lemma 4.20. For all i ∈ { 0, 1, 2, . . . , ℓ }, the edge weights of the graph Gi are bounded above by poly(n). Proof. By Lemma 4.18, we know that the weights of the graphs { G0 , G1 , G2 , . . . , Gℓ∗ } are polynomially-bounded. To bound the edge weights of the remaining graphs { Gℓ∗ +1 , Gℓ∗ +2 , . . . , Gℓ }, it suffices to show that the function gℓ (n) as defined in Lemma 4.19 is bounded above by poly(n), i.e., that the last graph of the second phase has polynomially-bounded weights. By Lemma 4.18, we know that the edge weights of Gℓ∗ are bounded above by the function g ∗ (n) ∈ poly(n). Additionally, by Lemma 4.14, we know that the number of iterations in the second phase is at most O(1/γ). Therefore, we conclude that the function gℓ (n) is bounded by  O(1/γ) gℓ (n) ∈ 3nγ/4 · g ∗ (n) ∈ 3O(1/γ) nO(1) · g ∗ (n) ⊆ poly(n), as desired. We are now ready to show that the weighted diameters of the graphs G′i are always polynomial in n for both the first and second phases. As a result, Step 3 of each iteration, and by extension the entirety of each iteration, requires only O(log log n) rounds. Since we only have O(log log n) iterations, this gives an overall round complexity of O(log2 log n) rounds. Lemma 4.21. Each iteration runs in O(log log n) rounds. As a direct consequence, the entire algorithm runs in O(log2 log n) rounds. Proof. We first bound the weighted diameters di of the graphs G′i . By Lemma 4.20, we know that the edge weights of the graphs { Gi } for all iterations i are bounded above by some function gi (n) ∈ poly(n). Moreover, recall that G′i is a subgraph of Gi by the definition of spanners. Therefore, we must have that di ≤ (n − 1) · gi (n) ∈ poly(n) as any shortest path in G′i has at most n − 1 edges. To assess the round complexity of each iteration, we break it down by steps. • Steps 1, 2, 4 and 5 require O(1) rounds. • Step 3 requires O(log log n + log log di ) ⊆ O(log log n) rounds as di ∈ poly(n) for all iterations. Therefore, we observe that each iteration requires O(log log n) rounds. Since we have O(log log n) iterations by Lemma 4.15, the entire algorithm requires O(log log n·log log n) = O(log2 log n) rounds as claimed. Emulator Properties. We are now ready to bound the hopbound and stretch of the emulator H. To gain an intuitive picture, you can imagine that we are “climbing a tower” of skeleton graphs using edges in H, starting from G = G0 . We start with any pair of vertices u0 , v0 ∈ V0 and the path P0 from u0 to v0 with properties (P1) and (P2) as defined in Definition 3.1. Denote the path P0 as u0 → u1 ⇝ v1 → v0 , and denote the first and last edges of P0 as e1 = { u0 , u1 } and e2 = { v1 , v0 } respectively. We make two observations: • By property (P2), we know the edges e1 and e2 can be found in H. • Also by property (P2), we know that the subpath from u1 to v1 in P0 is contained entirely in G1 . 27

Therefore, using the edges e1 and e2 , we can “climb up” from G0 to G1 . By property (P1) of path P0 , if we find a constant approximation for dG1 (u1 , v1 ), this will directly yield a constant approximation for dG0 (u0 , v0 ). This motivates us to repeat the same process: We now consider the path P1 from u1 to v1 (as defined in Definition 3.1) and using the same procedure, climb from G1 to G2 . We repeat this until we reach the graph Gℓ , where we are finally able to “connect” the endpoints. Since we only have an O(log log n) number of graphs to climb (by Lemma 4.15), we only need O(log log n) edges in H. Additionally, combining these edges yields a (2/γ)O(log log n) -approximate length path from u0 to v0 in H. We now formalise the above intuition in the following lemma. Lemma 4.22. For all i ∈ { 0, 1, 2, . . . , ℓ }, consider any pair of vertices u, v ∈ Vi . There exists a path P from u to v in H such that all of the following hold: • P has at most 1 + 2(ℓ − i) edges, and • the length of P is at most [7C(2/γ)]ℓ−i · dGi (u, v), where C is the same constant defined in Step 1 of the algorithm. Proof. We prove by induction on i, starting from i = ℓ. Base Case (i = ℓ). Recalling the termination stage of the algorithm, we know that the all-pairs distances of Gℓ were added to H as weighted edges. Therefore, the base case holds. Inductive Case. Suppose the claim holds for i = j. Consider any two vertices u, v ∈ Vj−1 . In the case where u ∈ Nkj−1 (v) or v ∈ Nkj−1 (u) (with respect to the graph G′j−1 ), the claim trivially holds. So suppose not: Consider the path P from u to v in Ekj−1 ∪ Ej with the properties (P1) and (P2) as defined in Definition 3.1. We denote the path P as u → u∗ ⇝ v ∗ → v. Additionally, let e1 = { u, u∗ } and e2 = { v ∗ , v } be the first and last edges of path P respectively. By property (P2), we know that e1 , e2 ∈ H. Moreover, the subpath from u∗ to v ∗ in P is contained entirely in the graph Gj . We therefore apply our induction hypothesis on Gj to obtain the path P ∗ ⊆ H from u∗ to v ∗ , which has the following properties: • P ∗ has at most 1 + 2(ℓ − j) edges. • The length of P ∗ is at most [7C(2/γ)]ℓ−j · dGj (u∗ , v ∗ ). We now consider a new path Q from u to v, defined as follows: From u to u∗ using edge e1 , u∗ to v ∗ using path P ∗ , and lastly v ∗ to v using edge e2 . Observe that Q is entirely contained in the edge set H. Moreover, we find that Q has the following properties: • Q has at most 1 + 2(ℓ − j) + 2 = 1 + 2(ℓ − (j − 1)) edges. • Considering P is a 7-approximation of dG′j−1 (u, v) and that G′j−1 is a C(2/γ)-spanner for

28

Gj−1 , we have ω(Q) = ω(e1 ) + ω(P ∗ ) + ω(e2 ) ≤ ω(e1 ) + [7C(2/γ)]ℓ−j · dGj (u∗ , v ∗ ) + ω(e2 ) = dG′j−1 (u, u∗ ) + [7C(2/γ)]ℓ−j · dGj (u∗ , v ∗ ) + dG′j−1 (v ∗ , v) h i ≤ [7C(2/γ)]ℓ−j dG′j−1 (u, u∗ ) + dGj (u∗ , v ∗ ) + dG′j−1 (v ∗ , v) ≤ [7C(2/γ)]ℓ−j · ω(P ) ≤ [7C(2/γ)]ℓ−j · 7 · dG′j−1 (u, v) ≤ [7C(2/γ)]ℓ−j · 7C(2/γ) · dGj−1 (u, v) = [7C(2/γ)]ℓ−(j−1) · dGj−1 (u, v). We now summarise the properties of our emulator H in the following lemma. Lemma 4.23. H is a (2/γ)O(log log n) -stretch O(log log n)-hopbound emulator of the graph G = G0 . Proof. By Lemma 4.15, we have that the final iteration ℓ ≤ T · log log n for some constant T . Therefore, applying our stretch upper bound in Lemma 4.22 with i = 0, we have that for any pair of vertices u, v ∈ V , (1+2T ·log log n)

dH

(u, v) ≤ [7C(2/γ)](T ·log log n) dG (u, v) ∈ (2/γ)O(log log n) dG (u, v).

To show the lower bound, we recall our definition of the skeleton graph in Definition 3.1. Specifically, we observe that for all iterations i, the distances in G are never contracted in the subsequent graphs Gi , i.e., dG (u, v) ≤ dGi (u, v). Consequently, we have that dG (u, v) ≤ dH (u, v) for all pairs of vertices u, v ∈ V . Therefore, we conclude that H is indeed a (2/γ)O(log log n) -stretch O(log log n)-hopbound emulator for G. We now conclude with the proof of Lemma 4.9. Proof of Lemma 4.9. We run the algorithm described in Section 4.3.1. This constructs the edge set H, which by Lemma 4.23 is a (2/γ)O(log log n) -stretch O(log log n)-hopbound emulator for G. By Lemma 4.21, we only require O(log2 log n) rounds. By the algorithm description, we observe that each iteration requires at most Õ(|E| + n1+γ ) total memory, and since there are O(log log n) iterations by Lemma 4.15, we therefore require at most Õ(log log n · (|E| + n1+γ )) ⊆ Õ(|E| + n1+γ ) total memory. In particular, we have sufficient total memory to store the emulator H across the machines. 4.3.3

Wrapping it Up

Now having access to a (2/γ)O(log log n) -stretch O(log log n)-hopbound emulator, we can apply Lemma 3.4 on the emulator to construct (2/γ)O(log log n) -approximate k-nearest neighbourhoods for all vertices. We state this in the following lemma. Lemma 4.24. Let G = (V, E) be a connected, weighted graph with n vertices and let integer k > 0 be a parameter. Given that k 2 ∈ O(nγ ), in the heterogeneous MPC model with Õ(|E|+n1+γ ) total memory, there exists a randomised algorithm that w.h.p. constructs the set { (u, t) : u ∈ V ∧ t ∈ Ñk (u) } 29

where Ñk (u) is a (2/γ)O(log log n) -approximate k-nearest neighbourhood for u. This algorithm runs in O(log2 log n) rounds. Proof. We first invoke Lemma 4.9 to construct a (2/γ)O(log log n) -stretch O(log log n)-hopbound emulator H for the graph G. This requires Õ(|E| + n1+γ ) total memory and runs in O(log2 log n) rounds. Denote the hopbound of the emulator as CH log log n, where CH > 0 is some constant. We now apply Lemma 3.4 on H, setting the parameter r such that 2r = h ≥ CH log log n. (h) This gives us the k-nearest h-hop neighbourhoods Nk (u) for all vertices u ∈ V in the emulator H. By the properties of the emulator H, these suffice as (2/γ)O(log log n) -approximate k-nearest neighbourhoods in the graph G, and we are done. This requires Õ(|H| + nk 2 ) ⊆ Õ(|E| + n1+γ ) total memory and O(r) = O(log log log n) rounds. Overall, we require Õ(|E| + n1+γ ) total memory and O(log2 log n + log log log n) = O(log2 log n) rounds, as claimed. It now remains to complete the proof for Theorem 2, which follows similarly to the proof for Theorem 1. However, we now use Lemma 4.24 for constructing the approximate k-nearest neighbourhoods instead. Proof of Theorem 2. By Lemma 2.6, we may assume that G is a connected graph. We first apply the spanner construction in Lemma 2.4 to construct an O(2/γ)-spanner G′ for G of size Õ(n1+γ/2 ) in O(1) rounds. We then apply Lemma 4.24 to construct a = (2/γ)O(log log n) -approximate k = nγ/4 nearest neighbourhoods Ñk (u) for all vertices u ∈ V in G′ , which requires O(log2 log n) rounds. We now apply Lemma 4.2 with the parameter c = γ, which constructs an O(1/γ)-approximate SSSP oracle for G′ in O(log a + log log n) ⊆ O(log log n) rounds – the inclusion follows as we treat γ as a constant. In total, we require Õ(|E| + n1+γ ) total memory across all steps. Since G′ is an O(2/γ)-spanner for G, an O(1/γ)-approximate SSSP oracle for G′ directly yields an O(1/γ 2 )-approximate SSSP oracle for G, and we are done. In total, we require O(log2 log n + log log n) = O(log2 log n) rounds and Õ(|E| + n1+γ ) total memory, as desired. For the remainder of this work, we further discuss the building blocks as described in Section 3.1.

5

Computing k-Nearest Hopsets

In this section, we aim to prove the following lemma, which constructs a k-nearest hopset for a given weighted graph G in constant rounds. Lemma 3.3 (k-Nearest Hopset). Let G = (V, E) be a connected, weighted graph with n vertices, and let k > 0 be an integer. Suppose that for every vertex u ∈ V , we are given the set {(u, t) : t ∈ Ñk (u)}, where Ñk (u) is an a-approximate k-nearest neighbourhood of u. If k 2 ∈ O(nγ ), then in the sublinear MPC model with Õ(|E| + nk 2 ) total memory, there exists a deterministic algorithm that constructs a k-nearest O(a log d)-hopbound hopset H in O(1) rounds, where d is the weighted diameter of G. Construction. We closely follow the construction of [BCC+ 24, Lemma 2.2]. The central idea behind the construction is straightforward: Each vertex u requests the k shortest incident edges from every vertex t ∈ Ñk (u). This allows u to learn the exact distances to a significant fraction of the vertices in Ñk (u); these exact distances are added as weighted edges to the hopset. Subsequently,

30

one can show that for any vertex v ∈ Nk (u), an appropriate choice of a hopset edge together with one edge from the original graph covers at least 1/a-fraction of the distance from u to v. More concretely, for every vertex t ∈ V , first denote Ik (t) as the k shortest edges incident to t in G, breaking ties, say, by endpoint vertex ID. We define the edge set [ Tk (u) = Ik (t) t∈Ñk (u)

and let Bk (u) be the set of all vertices covered by at least one edge in Tk (u). Lastly, for all v ∈ Bk (u), define δu (v) as the distance from u to v in the subgraph of G induced by the edge set Tk (u). We now define the weighted edge set H as follows: H = { { u, v } : u ∈ V ∧ v ∈ Bk (u) ∧ δu (v) ̸= ∞ } ,

where ωH (u, v) = δu (v).

If multiple candidates exist, choose the edge with the lowest weight. Correctness. The hopset construction is essentially identical to [BCC+ 24, Lemma 2.2], except for a minor difference. In [BCC+ 24], they defined δu (v) as the shortest distance from u to v in the induced subgraph of Tk (u)∪{ { u, w } : { u, w } ∈ E }, i.e., the edges incident to u are also considered in the local shortest path computation. However, it is evident from their proof technique that this difference is not significant. For the sake of completeness, we make this explicit. We define the d-distance ball of a vertex u as Balld (u) := { v : dG (u, v) ≤ d }. It is also convenient to define ℓk (u) := maxv∈Nk (u) dG (u, v), i.e., the minimum d such that Nk (u) ⊆ Balld (u). Notice that for any d < ℓk (u), we have that |Balld (u)| < k. We first invoke two claims from [BCC+ 24]. The first claim suggests that any approximate knearest neighbourhood Ñk (u) contains a ball of a certain distance radius around u. The second claim shows that this distance radius is sufficiently large such that short-cutting exact distances to vertices in this ball gives us the desired hopset. We note that the original statements in [BCC+ 24] √ only had k = n, but it is clear that their proofs do not require any special value of k. Claim 5.1 ([BCC+ 24]). For any u ∈ V and any a-approximate k-nearest neighbourhood Ñk (u) for u, we have Ball(ℓk (u)−1)/a (u) ⊆ Ñk (u). Claim 5.2 ([BCC+ 24]). The edge set H ′ := { { u, v } : u ∈ V ∧ v ∈ Ball(ℓk (u)−1)/a (u) } with edge weights ωH ′ (u, v) := dG (u, v) is a k-nearest O(a log d)-hopbound hopset for G. To connect the preceding two claims, we show in the following claim that the edges Tk (u) are sufficient to determine the exact distances to vertices in Ball(ℓk (u)−1)/a (u). Claim 5.3. Consider any vertices u, v ∈ V such that v ∈ Ball(ℓk (u)−1)/a (u), and let u = w1 → w2 → . . . → wm = v be any shortest path from u to v in G. For each integer 1 ≤ i ≤ m − 1, we have that { wi , wi+1 } ∈ Ik (wi ). Proof. Suppose not, i.e., there exists some vertex wi such that { wi , wi+1 } ∈ / Ik (wi ). Observe that this implies |Ik (wi )| = k. Moreover, for every z ∈ V such that { wi , z } ∈ Ik (wi ), we have dG (u, z) ≤ dG (u, v) – to observe this, notice that ωG (wi , z) ≤ ωG (wi , wi+1 ) ≤ dG (wi , v) and therefore dG (u, z) ≤ dG (u, wi ) + ωG (wi , z) ≤ dG (u, wi ) + dG (wi , v) = dG (u, v). In particular, this implies that dG (u, z) ≤ (ℓk (u) − 1)/a and z ∈ Ball(ℓk (u)−1)/a (u). Altogether, we find that the k vertices { z : { wi , z } ∈ Ik (wi ) } are in Ball(ℓk (u)−1)/a (u) and hence |Ball(ℓk (u)−1)/a (u)| ≥ k. Contradiction. 31

Claim 5.4 ([BCC+ 24]). The edge set H is a k-nearest O(a log d)-hopbound hopset for G. Proof. By Claims 5.1 and 5.3, we find that the edge set Tk (u) is sufficient to learn the exact distances to each vertex v ∈ Ball(ℓk (u)−1)/a (u); in particular, the edges of every shortest path from u to v ∈ Ball(ℓk (u)−1)/a (u) are contained in Tk (u). Claim 5.2 implies that H is indeed a k-nearest O(a log d)-hopbound hopset for G. For the rest of the section, to finish the proof of Lemma 3.3, we show that H can be constructed efficiently in the sublinear MPC model. In the following implementation details, we use two MPC procedures: the duplication lemma and labelling lemma. For the sake of presentation, we defer the description of these lemmas and their proofs to Section A. The high-level idea for the construction is as follows: Every vertex u first requests the set Ik (t) from every vertex t ∈ Ñk (u). After receiving the edge set Tk (u), vertex u locally computes the distances δu (v) and adds the edge { u, v } to H for every vertex v ∈ Bk (u). Implementing this idea in the MPC model does not pose any significant challenges, although care has to be taken in the communication of edges from one vertex to another. We remark that the size of the edge set |Tk (u)| ≤ k 2 by definition, and therefore we require 2 k ∈ O(nγ ) for the distances { δu (v) : v ∈ Bk (u) } to be computed entirely on a single sublinear memory machine. Moreover, we also require the additional total memory of O(nk 2 ) to store the edge sets Tk (u) for all vertices u ∈ V . Representing Information. Before discussing implementation details, we first need to describe how we represent information within the MPC model. We categorize information into two types of information packets: Edges: For each edge { a, b } ∈ E with weight ωG (a, b) belonging to vertex c, we represent it as (E, c, { a, b } , ωG (a, b)). k-Nearest: For each vertex b ∈ Ñk (a), we represent it as (K, b, a). The symbols E and K are used only to differentiate between the two types of information packets. Step 0: Initialisation. At the start of the algorithm, we may assume for every vertex u ∈ V , we only have information of its incident edges and its approximate k-nearest neighbourhood Ñk (u). • For each edge { u, v } ∈ E, there exists a machine that contains (E, u, { u, v } , ωG (u, v)). • For each vertex t ∈ Ñk (u), there exists a machine that contains (K, t, u). Initially, this information is arbitrarily distributed across all the machines. For every edge { u, v } ∈ E, we may assume there exist two packets representing this edge: (E, u, { u, v } , ωG (u, v)) and (E, v, { u, v } , ωG (u, v)). Step 1: Send Requests. To simulate the sending of a request from one vertex to another, it suffices to sort the information packets. Namely, by applying the sorting procedure in Lemma 2.5 using the second item in the tuple as the key, each vertex t ∈ V now has the following information stored on a contiguous set of machines M (t). 32

• (E, t, { t, v } , ωG (t, v)), for every edge { t, v } ∈ E incident to t. • (K, t, u), for every vertex u such that t ∈ Ñk (u). c(t). This step runs in O(1) rounds. Denote the machine in M (t) with the smallest ID as M Intuitively, (K, t, u) corresponds to a request from u asking t for the edge set Ik (t). Step 2: Create Duplicates of Incident Edges. For each vertex t ∈ V , we write Dk (t) = { u : t ∈ Ñk (u) } and dt = |Dk (t)|. Recall that our goal is to let t send the edge set Ik (t) to each vertex in Dk (t). The messages to be sent are prepared as follows: We create dt duplicates of the edge set Ik (t) and thereafter label each duplicate according to the vertex IDs in c(t) learns the value Dk (t). To initiate this procedure, we require that each leader machine M of dt and the edge set Ik (t). We do so in the following way: • Learning the value dt is done by counting the total number of packets (K, t, ·) stored across the machines M (t). We execute this by calling the prefix sum sub-routine in c(t) knows the sum dt . Lemma 2.5 and sorting such that the leader machine M • Learning the edge set Ik (t) is done by sorting the edge packets in M (t) by their edge weights (using Lemma 2.5). We then collect the edges Ik (t) onto the leader machine c(t) with one additional round (which can be done as |Ik (t)| ≤ k and k ∈ O(nγ ) by M assumption). Now, we are ready to duplicate and label the edges. 1. We first apply Lemma A.1 to create dt duplicates of Ik (t) in the form (Ik (t), 1), (Ik (t), 2), . . . , (Ik (t), dt ). 2. We next apply Lemma A.2 to relabel each duplicate with a vertex ID in Dk (t). In other words, denoting Dk (t) = { u1 , u2 , . . . , udt }, we now have the duplicates in the form of (Ik (t), u1 ), (Ik (t), u2 ), . . . , (Ik (t), udt ). 3. Lastly, for each duplicate (Ik (t), uj ), we relabel every edge packet in Ik (t) from (E, t, { t, v } , ωG (t, v)) to (E, uj , { t, v } , ωG (t, v)). P 2 Crucially, since t∈V dt ≤ nk, we only require O(nk ) additional total memory to apply Lemmas A.1 and A.2 which is satisfied by our constraints. Overall, this entire step runs in O(1) rounds. Step 3: Send and Receive Edges. Similar to Step 1, we again sort the edge packets by the second item in the tuple using Lemma 2.5. At this point, we can discard the k-nearest packets. After this, for each vertex u ∈ V , we have the packets (E, u, { t, v } , ωG (t, v)) for the edges { t, v } ∈ Tk (u) stored on a set of contiguous machines M (u) (Note that these are not necessarily the same machines in Step 2). Recalling that |Tk (u)| ≤ k 2 and k 2 ∈ O(nγ ) by assumption, the entire set of edges Tk (u) can c(u) with an additional O(1) rounds (note that we do not need be collected onto the leader M the entire set of incident edges of u, which could have size larger than k 2 ). Overall, this step requires O(1) rounds.

33

c(u) (from Step 3) now locally computes the Step 4: Add Edges to H. Each leader machine M distances δu (v) for all v ∈ Bk (u). Subsequently, for v ∈ Bk (u) (and δu (v) ̸= ∞), the machine c(u) creates a new packet (E, u, { u, v } , δu (v)) to be included into the edge set H. M This concludes the algorithm description. We make a few concluding remarks which are not critical to the algorithm description, but are worth mentioning for clarity: c(u) to just mark which edges • In the last step of the algorithm, it suffices for each machine M are included in H. We do not specify that the edges in H need to be on a set of contiguous machines. • To remove duplicate edges in H, it suffices to perform one final sorting step using Lemma 2.5 to group all edge weights corresponding to each edge { u, v } ∈ H onto a contiguous set of machines, with the weights within each group sorted. Then, each group can locally retain the smallest edge weight using the “finding minimum” procedure in Lemma 2.5, and discard the rest. We summarise the above discussion in the following proof of Lemma 3.3. Proof of Lemma 3.3. We apply the algorithm as described above to construct the edge set H. By the algorithm description, the edge set H constructed by the algorithm is exactly the edge set H specified in Claim 5.4, and is therefore a k-nearest O(a log d)-hopbound hopset for G. Using Õ(|E| + nk 2 ) total memory, each step of the algorithm runs in O(1) rounds. Therefore, the entire algorithm runs in O(1) rounds as well, as desired.

6

Extracting k-Nearest Neighbourhoods

In this section we prove the following lemma, which gives us k-nearest h-hop neighbourhoods according to the input graph. In particular, if we have a c-stretch h-hopbound emulator for a graph G, we can obtain c-approximate k-nearest neighbourhoods for all vertices in G using O(log h) rounds. Alternatively, if we have a k-nearest h-hopbound hopset H for G, applying the lemma on G ∪ H gives exact k-nearest neighbourhoods for all vertices in G. That is, in conjunction with Lemma 3.3, we have a useful tool for extracting exact k-nearest neighbourhoods from approximate k-nearest neighbourhoods in the sublinear MPC model. Lemma 3.4 (Extracting k-Nearest Neighbourhoods). Let G = (V, E) be a connected, weighted graph with n vertices, and let k > 0 and r > 0 be integers, setting h = 2r . Suppose that k 2 ∈ O(nγ ). Then, in the sublinear MPC model with Õ(|E| + nk 2 ) total memory, there exists a deterministic O(r)-round algorithm that constructs the set n  o (h) (h) u, t, dG (u, t) : u ∈ V and t ∈ Nk (u) . Notation. Before describing the construction, it is convenient to define some notation for matrices. We call C the adjacency matrix of a graph H = (VH , EH ) if Cu,v = ωH (u, v) for all vertices u, v ∈ VH . We denote C as the filtered matrix of C, where only the k smallest elements of each row in C are kept, breaking ties by ID (with the remaining elements set to ∞). We specifically denote A to be the adjacency matrix of the input graph G, i.e., Au,v = ωG (u, v) for all vertices u, v ∈ V . 34

In this section, we only consider matrix multiplication under the min-plus semiring. Observe (i) that for all integers i ≥ 1 and for all vertices u, v ∈ V , we have Aiu,v = dG (u, v). In other words, (i)

learning the matrix Ai is equivalent to learning the neighbourhoods Nk (u) for all vertices u ∈ V . Construction. The construction is an application of the well-known graph exponentiation technique: Each vertex u maintains a vertex set which describes its current view of its k-nearest neigh(1) bourhood. Initially, this vertex set is simply Nk (u), the k nearest adjacent vertices to u in G. (2i )

During the ith iteration, the vertex u starts with the k-nearest 2i -hop neighbourhood Nk

(u), and

(2i ) (2i ) gathers the sets Nk (t) for every vertex t ∈ Nk (u). Using this new information, u is able to (2i+1 ) exactly construct the 2i+1 -hop neighbourhood Nk (u). We repeat this process until every u ∈ V (h) knows the h-hop neighbourhood Nk (u). More concretely, we define the sequences of matrices { Bi } for i ∈ { 0, 1, 2, . . . } as follows:

B0 = A, 2 . Bi = Bi−1

For every vertex u ∈ V , the entries of row u in Bi+1 correspond to the vertices and values that u learns at the end of the ith iteration. In other words, we want to show that Bi = A2i for all integers i ≥ 0. Correctness. We adopt a useful lemma from Bui et al. [BCC+ 24], which claims that for any adjacency matrix C representing a graph with positive integer weights, the k smallest entries in each row of (C)i are the k smallest entries in the corresponding row of C i . Lemma 6.1 ([BCC+ 24]). Let C be the adjacency matrix of a graph with positive integer weights. Then we have (C)i = C i for all integers i ≥ 1. We now proceed to show that Bi = A2i . There is a slight difference between Lemma 6.1 and the construction of the matrices { Bi }: For the former, the filtering occurs only at the end of all i iterations; for the latter, the filtering occurs between each iteration. However, by applying Lemma 6.1 between each iteration, we can show the desired claim. Lemma 6.2. For all integers i ≥ 0, we have Bi = A2i . Proof. We prove this by induction. In the base case i = 0, we have B0 = A = A20 as claimed. Proceeding to the inductive case: Suppose the claim holds for i = j. Invoking our induction hypothesis, we have that  2 Bj+1 = Bj2 = A2j . j

Observe that the matrix A2 represents the adjacency matrix of the graph G′ = (V, E ′ ) with edge j (2j ) weights ωG′ (u, v) = dG (u, v). Therefore, we can apply Lemma 6.1 on the matrix A2 with i = 2 to obtain  2 Bj+1 = A2j = (A2j )2 = (A2j+1 ), as desired. 35

6.1

Algorithm Description

We describe the algorithm in iterations: For each iteration i ∈ { 0, 1, 2, . . . }, we start with the matrix Bi , and by communicating minimal but sufficient information between vertices, we show that we can construct the matrix Bi+1 in a constant number of rounds. For ease of notation, for all i ∈ { 0, 1, 2, . . . } and for all vertices u ∈ V , we define n  o (2i ) (2i ) Bi (u) = u, t, dG (u, t) : t ∈ Nk (u) . In other words, Bi (u) represents the entries of the row u of Bi (by Lemma 6.2). To perform the matrix multiplication, observe that to determine the values Bi+1 (u) for any vertex u ∈ V , it suffices to have the following information: • The values Bi (u), and (2i )

• The values Bi (t) for all vertices t ∈ Nk

(u).

By extension, recalling that |Bi (v)| ≤ k for all vertices v ∈ V , we require O(k 2 ) memory per machine in order to construct the values Bi+1 (u) entirely locally. We note that the algorithm description for each iteration is nearly identical to the algorithm for Lemma 3.3. Therefore, for the sake of brevity, we describe only the essential details. Initialisation. To determine the values B0 (u) for every vertex u ∈ V , it suffices to sort the edges such that the k shortest edges incident on u (breaking ties by ID) are stored on a single machine. Using Lemma 2.5, this requires O(1) rounds. A Single Iteration. Our procedure for each iteration proceeds as follows: In iteration i ∈ { 0, 1, 2, . . . }, every vertex u ∈ V initially has the values Bi (u). Step 1. Sending Requests. For every vertex u ∈ V , it sends a request for the values Bi (t) for (2i ) each vertex t ∈ Nk (u). Using Lemma 2.5, this step requires O(1) rounds. (2i )

Step 2. Duplicating Information. For every vertex t ∈ V , denote Di (t) = { u : t ∈ Nk (u) } and dt = |Di (t)|. Recall that our goal is to let t send the values Bi (t) to every vertex in Di (t). This proceeds as follows: 1. We duplicate dt copies of the values Bi (t). 2. We label each duplicate with a vertex ID in Di (t). In other words, denoting Di (t) = { u1 , u2 , . . . , udt }, we have constructed the values (Bi (t), u1 ), (Bi (t), u2 ), . . . , (Bi (t), udt ). Using P Lemma A.1 and Lemma A.2, this 2step requires O(1) rounds. Moreover, recalling that t∈V dt ≤ nk, this step requires O(nk ) additional total memory. Step 3. Performing Matrix Multiplication. For every vertex u ∈ V , we sort the values across c(u): the machines such that we have the following information stored on a single machine M • The values Bi (u), and 36

(2i )

• The values Bi (t) for all vertices t ∈ Nk

(u).

c(u) is able to construct the values Bi+1 (u) as specified Finally, using its local information, M in the earlier construction. Using Lemma 2.5, this step requires O(1) rounds. All remaining information is then discarded. Claim 6.3. Running T consecutive iterations of the above algorithm in the sublinear MPC model requires O(T ) rounds and Õ(|E| + nk 2 ) total memory (independent of T ). Proof. We first argue about the round complexity. For each iteration, every step requires only O(1) rounds. Since there is a constant (three) number of steps, each iteration only requires O(1) rounds, and running T consecutive iterations requires O(T ) rounds. We next argue about the total memory constraints. Observe that each iteration requires only O(nk 2 ) additional memory: Step 1 requires O(nk) additional memory, while Steps 2 and 3 require O(nk 2 ) additional memory. Naively, we might assume that we therefore require O(T ·nk 2 ) additional total memory overall. However, recall that after Step 3 in each iteration, we discard all remaining information except for the values of the matrix Bi+1 . In other words, there is no accumulation of memory usage between iterations, and the total memory required remains as Õ(|E|+nk 2 ), regardless of the number of iterations. The Final Proof. We summarise our discussion for this section with the proof of Lemma 3.4. Proof. We run the above algorithm for r iterations, which requires O(r) rounds and Õ(|E| + nk 2 ) total memory by Claim 6.3. By the end of the algorithm, we have constructed the entries of the matrix Br = Ah . Now applying Lemma 6.2, we observe that this is equivalent to the values (h) (h) { (u, t, dG (u, t)) : u ∈ V ∧ t ∈ Nk (u) }, and we are done.

7

Skeleton Graphs

In this section, we prove the following lemma, which provides a fast construction for the skeleton graph as defined in Definition 3.1. Lemma 3.2 (Skeleton Graph Construction). Let G = (V, E) be a connected, weighted graph with n vertices, and let k > 1 be an integer. Suppose the k-nearest edge set Ek for G is given. If k 2 ∈ O(nγ ), then in the sublinear MPC model with Õ(|E|k 2 ) total memory, there exists a randomised algorithm that w.h.p. constructs a skeleton graph GS = (VS , ES ) in O(1) rounds. Our skeleton graph is based on the construction proposed by [BCC+ 24], which has exactly the properties described in Definition 3.1. However, the main (and only) issue with this construction is that the number of edges in the skeleton graph is poorly bounded. Therefore, we suggest a modified construction that maintains the same properties while bounding the number of edges by O(|E|k 2 ). In doing so, we require adding additional vertices to the skeleton graph; however, we show that the number of additional vertices is at most n/k, and therefore the number of vertices is still bounded above by Õ(n/k).

37

Original Construction. We first discuss the construction proposed by [BCC+ 24]. We follow a clustering approach: The cluster centers are the vertex set C ⊆ V , chosen such that |C| ∈ O((n log k)/k) and C ∩ Nk (u) ̸= ∅ for all u ∈ V (i.e., C is a hitting set for the k-nearest neighbourhoods). The vertex set C is constructed by first adding each vertex w ∈ V to C independently with probability p ∈ Θ((log k)/k) and subsequently adding any remaining vertices w′ with C ∩ Nk (w′ ) = ∅. For all vertices u ∈ V , we add u to the cluster with the nearest center. More concretely, we choose a c(u) ∈ C such that the distance dG (u, c(u)) is the smallest among all vertices in C ∩ Nk (u) (breaking ties arbitrarily). We now define the graph G∗S = (VS∗ , ES∗ ) as follows: • VS∗ = C, and • For all vertices u, v ∈ V , we add the edge { c(u), c(v) } ∈ ES∗ if there exists a vertex t ∈ V such that all of the following hold: – t ∈ Nk (u) (i.e., t is in the k-nearest neighbourhood of u), and – { t, v } ∈ E (i.e., t is adjacent to v in G) or t = v. We define the edge weight ωG∗S (c(u), c(v)) := dG (c(u), u) + dG (u, t) + ωG (t, v) + dG (v, c(v)). If there are multiple candidate edge weights, choose the minimum weight. We now give a proof sketch of the correctness of G∗S . Namely, for any two vertices that are not in the k-nearest of each other, there exists a path in Ek ∪ ES∗ that satisfies the two properties stated in Definition 3.1. Claim 7.1 ([BCC+ 24]). G∗S is a skeleton graph for G as defined in Definition 3.1. Proof Sketch. To show that G∗S is a skeleton graph for G, we need to verify the following properties: • |VS∗ | ∈ O((n log k)/k). • dG∗S (u, v) ≥ dG (u, v) for all u, v ∈ VS∗ . • If ωG (u, v) ≤ g(n) for all { u, v } ∈ E for some function g, then ωG∗S (x, y) ≤ 3k · g(n) for all { x, y } ∈ ES∗ . • If G is connected, then so is G∗S . • If u ∈ / Nk (v) and v ∈ / Nk (u), then there exists a path P in Ek ∪ ES∗ with the properties (P1) and (P2). In this proof sketch, we focus on showing the last property; the remaining properties are relatively easier to verify. Consider any two vertices u, v ∈ V such that u ∈ / Nk (v) and v ∈ / Nk (u). We first consider the shortest path from u to v in G, which we denote as u = u0 ⇝ t0 → u1 ⇝ t1 → u2 ⇝ t2 → . . . → uℓ ⇝ tℓ = v chosen such that ti ∈ Nk (ui ) while ui+1 ∈ / Nk (ui ). By definition, observe that there must exist a path Q in ES∗ of the form c(u0 ) → c(u1 ) → c(u2 ) → . . . → c(uℓ ) → c(tℓ ). In particular, we observe that for i ≤ ℓ − 2, ωG∗S (c(ui ), c(ui+1 )) ≤ dG (c(ui ), ui ) + dG (ui , ti ) + ωG (ti , ui+1 ) + dG (ui+1 , c(ui+1 )) ≤ dG (ui , ui+1 ) + dG (ui , ti ) + ωG (ti , ui+1 ) + dG (ui+1 , ui+2 ) = 2 · dG (ui , ui+1 ) + dG (ui+1 , ui+2 ). 38

To bound the edge weights c(uℓ−1 ) → c(uℓ ) and c(uℓ ) → c(tℓ ), we observe that dG (uℓ , c(uℓ )) ≤ dG (uℓ , c(tℓ )) ≤ dG (uℓ , tℓ ) + dG (tℓ , c(tℓ )) ≤ dG (uℓ , tℓ ) + dG (u, v). Therefore, we conclude that the length of path Q is at most ℓ−1 X

ωG∗S (c(ui ), c(ui+1 )) + ωG∗S (c(uℓ ), c(tℓ ))

i=0

 ≤ 2 · dG (u0 , u1 ) + 3 

ℓ−1 X

 dG (uj , uj+1 ) + dG (uℓ , tℓ ) + dG (u, v) .

j=1

We now construct the final path P from u to v in Ek ∪ ES∗ : u → c(u) using an edge in Ek , c(u) ⇝ c(v) using path Q (contained entirely in ES∗ ), and c(v) → v using an edge in Ek . By construction, we observe that P obeys property (P2) of Definition 3.1. Additionally, noting that dG (u, c(u)) ≤ dG (u0 , u1 ) and dG (v, c(v)) ≤ dG (u, v), we observe the following: • The length of the path u → c(u) ⇝ c(v) is at most 6 · dG (u, v). • The length of the path c(v) → v is at most dG (u, v). Therefore, we conclude that the length of P is at most 7 · dG (u, v). Moreover, using the fact that dG∗S (u, v) ≥ dG (u, v) for all u, v ∈ VS∗ , we have that the length of P is indeed a 7-approximation of the distance dG (u, v), and thus obeys property (P1) of Definition 3.1. We now discuss our modified construction, which seeks to provide a better upper bound for the size of the skeleton graph while preserving the essential properties as stated in Definition 3.1. Modified Construction. For every vertex t ∈ V , we call t a bad vertex if there exist more than k 2 distinct vertices u ∈ V such that t ∈ Nk (u) (i.e., | { u : t ∈ Nk (u) } | > k 2 ); otherwise, we call t a good vertex. Denote B ⊆ V as the set of bad vertices in V . We also define the vertex set C and the vertices c(u) for all u ∈ V identically to the original construction. Before defining the modified skeleton graph, we first define two weighted edge sets EC and EB . Edge Set EC . Defined over the vertices C. For all vertices u, v ∈ V , we add the edge { c(u), c(v) } to EC if there exists a vertex t ∈ V such that all of the following hold: • t ∈ Nk (u) (i.e., t is in the k-nearest neighbourhood of u), • { t, v } ∈ E (i.e., t is adjacent to v in G) or t = v, and • t∈ / B (i.e., t is a good vertex). We define the edge weight ωEC (c(u), c(v)) := dG (c(u), u) + dG (u, t) + ωG (t, v) + dG (v, c(v)). If there are multiple candidate edge weights, choose the minimum weight. Note that the definition of EC is almost identical to the earlier definition of ES∗ , with the additional requirement that t ∈ / B. Edge Set EB . Defined over the vertices C ∪ B. For all bad vertices t ∈ B, we add the edge { s, t } to EB if either one of the following conditions holds: 39

• There exists a vertex u ∈ V such that s = c(u) and t ∈ Nk (u). In this case, we set the edge weight ωEB (s, t) := dG (s, u) + dG (u, t). • There exists a vertex v ∈ V such that s = c(v) and either { t, v } ∈ E or t = v. In this case, we set the edge weight ωEB (s, t) := dG (s, v) + ωG (v, t). If both conditions hold simultaneously or if there are multiple candidate edge weights, we always choose the minimum weight. We are now ready to define the graph GS = (VS , ES ) as follows: We define VS = C ∪ B and ES = EC ∪ EB (such that for any parallel edges, choose the edge with the smaller edge weight). This concludes the construction, and we claim that GS is a skeleton graph for G with the additional property that |ES | ∈ O(|E|k 2 ).

7.1

Correctness

We separate the proof of correctness into multiple smaller claims. We first argue on the size of the vertex set VS . Namely, we show that the number of bad vertices is upper bounded by n/k. Claim 7.2. |B| ≤ n/k. Consequently, we have |VS | ∈ O((n log k)/k). Proof. By definition, we have |C| ∈ O((n log k)/k). Thus to show that |VS | ∈ O((n log k)/k), it suffices to obtain a good bound for |B|. Consider the following “token distribution” procedure: For every vertex u ∈ V , u gives the vertex t ∈ V a token if t ∈ Nk (u). Observe that the set B is equivalent to the set of vertices with more than k 2 tokens. Additionally, we observe that there are at most nk tokens across all vertices. Therefore by the pigeonhole principle, we can only have at most nk/k 2 = n/k bad vertices. In other words, |B| ≤ n/k as claimed. We next argue on the size of the edge set ES . In particular, we will show that both EC and EB have at most O(|E|k 2 ) edges, and therefore ES has O(|E|k 2 ) edges as well. Claim 7.3. |ES | ∈ O(|E|k 2 ). Proof. A useful observation here is that in any simple undirected graph, the number of non-isolated vertices (i.e., vertices with at least one adjacent edge) is at most 2|E|; in particular, |B| ≤ 2|E|. Bounding |EB |. For every bad vertex t ∈ B, define the integers at = | { v : { v, t } ∈ E or v = t } | and bt = | { u : t ∈ Nk (u) } | (i.e., at is the number of vertices adjacent to t in G (and itself) and bt is the number of vertices that t is in the k-nearest of). P P We find that t∈B at ≤ 2|E| + |B| and t∈B bt ≤ 2|E|k – to observe the latter, sum the k-nearest neighbourhoods of each non-isolated vertex in V . Additionally, we observe from the definition of EB that for every bad vertex t ∈ B, we add at most (at + bt ) edges. Therefore, the size of |EB | is bounded by X |EB | ≤ (at + bt ) ≤ 2|E| + |B| + 2|E|k ∈ O(|E|k 2 ). t∈B

Bounding |EC |. Fix any two non-isolated vertices t, v ∈ V such that t is a good vertex, and either { t, v } ∈ E or t = v. By definition of a good vertex, there are at most k 2 vertices u such that 40

t ∈ Nk (u). Therefore, it follows from the definition of EC that we only construct at most k 2 edges { c(u), c(v) } with edge weight dG (c(u), u) + dG (u, t) + ωG (t, v) + dG (v, c(v)). Since there are at most O(|E|) possible choices for the vertices t and v, we can therefore conclude that there are at most O(|E|k 2 ) edges in EC . We now argue on the value of the edge weights of the edge set ES . Claim 7.4. Suppose that the edge weights ωG are bounded above by the function f (n). Then the edge weights ωGS are bounded above by the function g(n) = 3k · f (n). Proof. Before bounding the edge weights, we first make a preliminary but important observation: For any pair of vertices u, v ∈ V such that v ∈ Nk (u), we must have that dG (u, v) ≤ (k − 1)f (n). To see this, note that the shortest path from u to v in G necessarily has at most (k − 1) edges; otherwise the first k vertices along this path, including u and excluding v, form a better k-nearest neighbourhood for u. We now recall the definitions of the edge weights for EC and EB . • For any edge { sa , sb } ∈ EC , recall that the edge weight ωEC (sa , sb ) = dG (sa , u) + dG (u, t) + ωG (t, v) + dG (v, sb ), such that t, sa ∈ Nk (u) and sb ∈ Nk (v). By the earlier observation, we have that dG (sa , u) + dG (u, t) + dG (v, sb ) ≤ (3k − 3)f (n). Including the weight ωG (t, v), we find that ωEC (sa , sb ) ≤ (3k − 2) · f (n) ≤ 3k · f (n). • For any edge { s, t } in EB where t ∈ B, recall that there exists some vertex x ∈ V such that c(x) = s, and the edge weight ωEB (s, t) is either one of the following: – ωEB (s, t) = dG (s, x) + dG (x, t) such that t ∈ Nk (x); or – ωEB (s, t) = dG (s, x) + ωG (x, t) such that { x, t } ∈ E (or t = x). In the former case, the weight is bounded by (2k − 2) · f (n) ≤ 2k · f (n), while in the latter case, the weight is bounded by k · f (n). Therefore, we find that ωEB (s, t) ≤ max[2k, k] · f (n) = 2k · f (n). Overall, we find that for all edges { x, y } ∈ ES , we must have that ωGS (x, y) ≤ max[3k, 2k] · f (n) = 3k · f (n). The following claim is a lower bound on the distances in GS . Namely, for any pair of vertices in G, we show that their distances do not shrink in GS . Claim 7.5. For any pair of vertices u, v ∈ VS , we have dG (u, v) ≤ dGS (u, v). Proof. We recall the definitions of the edge weights for EC and EB . • Recalling the definition of EC , observe that for any edge { x, y } ∈ EC , the edge weight ωEC (x, y) is equivalent to the length of the path x ⇝ u ⇝ t → v ⇝ y in G (for some vertices u, v, t as per the definition of EC ). Namely, the length of this path is necessarily at least dG (x, y). 41

• Similarly, recalling the definition of EB , observe that for any edge { s, t } ∈ EB and fixing t to be the bad vertex, the edge weight ωEB (s, t) is equivalent to the length of the path s ⇝ u ⇝ t or s ⇝ v → t (for some vertices u, v as per the definition of EB ). Namely, the length of this path is necessarily at least dG (s, t). Therefore, for any edge { x, y } ∈ ES , we necessarily have that ωES (x, y) ≥ dG (x, y). By extension, for any vertices u, v ∈ VS , the length of any path from u to v contained in ES is at least dG (u, v). From this observation, the claim directly follows. We now show the most important claim: Between any pair of vertices in G that are not in the k-nearest neighbourhood of each other, there exists a path in Ek ∪ ES with the properties (P1) and (P2) described in Definition 3.1. Before proving this claim, it helps to prove the following result which gives us a way to transform a path in the original construction G∗S to a path in the modified construction GS of at most the same path distance. Claim 7.6. For any edge { x, y } ∈ ES∗ in the original construction G∗S , the shortest path from x to y in the modified construction GS is at most the edge weight in G∗S , i.e., dGS (x, y) ≤ ωG∗S (x, y). Proof. Recall the original construction G∗S : For any edge { x, y } ∈ ES∗ , the edge weight is given by ωG∗S (x, y) = dG (x, u) + dG (u, t) + ωG (t, v) + dG (v, y) for some vertices t, u, v ∈ V such that c(u) = x and c(v) = y. Now consider these same vertices but in the modified construction GS . There are two possible cases: Case 1: t is a good vertex. Recalling the construction for EC , we must have that the edge { x, y } is also added into EC . Since we always take the minimum weight of parallel edges, we have that the edge weight ωEC (x, y) ≤ ωG∗S (x, y). Case 2: t is a bad vertex. Recalling the construction for EB , we must have that the edges { x, t } and { t, y } are added into EB . Similarly, since we always take the minimum weight of parallel edges, we have that the weights ωEB (x, t) ≤ dG (x, u) + dG (u, t) and ωEB (t, y) ≤ ωG (t, v) + dG (v, y). Namely, this implies that ωEB (x, t) + ωEB (t, y) ≤ ωG∗S (x, y). We now adapt the earlier proof of Claim 7.1 and apply Claim 7.6 to prove the following claim. Claim 7.7. For any pair of vertices u, v ∈ V such that u ∈ / Nk (v) and v ∈ / Nk (u), there exists a path P in ES ∪ Ek that satisfies the properties (P1) and (P2) given in Definition 3.1. Proof. First recall the proof of Claim 7.1: For the vertices u, v as specified in the hypothesis, there exist edges e1 = { u, c(u) }, e2 = { c(v), v } in Ek and a path Q from c(u) to c(v) in G∗S such that the path from u to v formed by e1 , e2 and Q has distance at most 7 · dG (u, v). By applying Claim 7.6, we construct the path Q′ from c(u) to c(v) in GS such that ω(Q′ ) ≤ ω(Q). We now define the path P in Ek ∪ ES as follows: u → c(u) using the edge e1 , c(u) ⇝ c(v) using Q′ , and c(v) → v using the edge e2 . We now show that P obeys properties (P1) and (P2) as defined in Definition 3.1. Proof of (P1). We have that the length of P is at most 7 · dG (u, v) by the proof of Claim 7.1. By Claim 7.5, we also have that the length of P is at least dG (u, v). Therefore, the length of P is indeed a 7-approximation of the distance dG (u, v).

42

Proof of (P2). By construction, the first and last edges u → c(u) and c(v) → v are contained in Ek , while the remaining edges in Q′ are contained entirely in ES . Lastly, connectivity is now straightforward to show. Claim 7.8. If G is connected, then GS is also connected. Proof. We first show that the vertices in C are in the same connected component in GS . Suppose not, i.e., there exist vertices x, y ∈ C ⊆ V such that x and y are not in the same connected component in GS . In particular, observe that x = c(x) and y = c(y) necessarily. There are two possible cases: Case 1: x ∈ / Nk (y) and y ∈ / Nk (x). Since G is connected, we find that x and y are connected by a path, i.e., dG (x, y) ̸= ∞. By the proof of Claim 7.7, we find that there is necessarily a path from c(x) to c(y) in GS . Case 2: x ∈ Nk (y) or y ∈ Nk (x). Suppose that x ∈ Nk (y); the other case is similar. Notice that this necessarily satisfies the condition for an edge to be constructed between c(x) and c(y). Namely, if x is a good vertex, then { c(x), c(y) } ∈ EC ; else, { x, c(y) } ∈ EB . In either case, we get a contradiction. Considering now any vertex t ∈ VS \ C, note that t is necessarily a bad vertex. In other words, we have that the edge { t, c(t) } ∈ EB by definition. This suffices to show the claim. To summarise the above results, we present this final claim on correctness. Claim 7.9. The graph GS = (VS , ES ) is a skeleton graph for G as defined in Definition 3.1. Additionally, we have |ES | ∈ O(|E|k 2 ). Proof. By Claims 7.2, 7.4, 7.5, 7.7 and 7.8, it follows directly that GS is a skeleton graph for G according to Definition 3.1. Additionally by Claim 7.3, we have |ES | ∈ O(|E|k 2 ) as desired.

7.2

Algorithm Description

The most critical part of the algorithm description is constructing the edge sets EC and EB (as defined in the modified construction). The high-level idea is for every vertex u ∈ V to communicate the following values: • (c(u), dG (u, c(u)) + dG (u, t)) to every vertex t ∈ Nk (u). • (c(u), dG (u, c(u)) + ωG (u, t)) to every vertex t adjacent to u in G. We then delegate the construction of EC to the good vertices, and the construction of EB to the bad vertices. More concretely, every t ∈ / B constructs the edges { c(u), c(v) } for every u, v ∈ V such that t ∈ Nk (u) and { t, v } ∈ E (or t = v), which follows the familiar duplication–labelling procedure (as described previously in the algorithms for Lemma 3.3 and Lemma 3.4). For every vertex t ∈ B, it constructs the edges { c(u), t } for every u such that t ∈ Nk (u), and the edges { c(v), t } for every incident edge { v, t } ∈ E (or t = v). Overall, we show that this requires O(1) rounds with Õ(|E|k 2 ) total memory. Similar to the previous algorithm descriptions, we use the term packets to describe discrete units of information. 43

Step 0: Initialisation. We may assume that for every edge { u, v } ∈ E, there exist two copies of this edge across the machines in the form (Eadj , u, { u, v } , ωG (u, v)) and (Eadj , v, { u, v } , ωG (u, v)). Likewise for every edge { u, w } ∈ Ek , there exist two copies of this edge in the form (Ek−near , u, { u, w } , dG (u, w)) and (Ek−near , w, { u, w } , dG (u, w)). As a preliminary step, we first sort the edges using Lemma 2.5 such that for every vertex u ∈ V , we have the packets { (Eadj , u, { u, v } , ωG (u, v)) : { u, v } ∈ E } and { (Ek−near , u, { u, w } , dG (u, w)) : w ∈ Nk (u) } c(u). With another O(1) rounds, stored on a contiguous set of machines M (u) with leader M c(u) to know the set Nk (u) (recall that k ∈ O(nγ ) by assumption). we allow every leader M Step 1: Constructing the Hitting Set C. The objective in this step is to construct the packets (u, c(u)) for all vertices u ∈ V . We first describe how to construct the hitting set C, which we execute via a random sampling process. The high-level idea is as follows: 1. We start with C = ∅. Each vertex selects itself into C with probability (ln k)/k. 2. For every vertex u ∈ V such that Nk (u) ∩ C = ∅, we add u to C. By construction, C must be a hitting set for the neighbourhoods { Nk (u) : u ∈ V }. It can be shown that by repeating this procedure Θ(log n) times, we will have at least one execution where |C| ∈ Θ((n log k)/k) w.h.p., see [BCC+ 24, Lemma 6.1, arXiv2405.02695v2] or [DFK+ 21, Lemma 4.1]. We now translate this idea into the language of the MPC model. c(u) locally selects u into C with probability (ln k)/k. 1. For every vertex u ∈ V , the leader M Denoting ( 1 if u is added in C iu = 0 otherwise, we relabel every k-nearest edge packet into the form (Ek−near , v, { u, v } , dG (u, v), iu , iv ) which can be done in O(1) rounds via the MPC tools in Lemma 2.5. c(u) locally determines whether Nk (u) ∩ C = ∅; if this is true, it adds u 2. Every leader M to C. 3. The edge packets are re-labelled with the updated values for iu (for each vertex u ∈ V ) c(u) chooses c(u) as the vertex in C ∩ Nk (u) in O(1) rounds. Subsequently, each leader M that is closest to u. We execute the above procedure Θ(log n) times in parallel. We then choose an execution where |C| ∈ O((n log k)/k) – such an execution occurs w.h.p. – and construct the packets (u, c(u)) corresponding to that particular execution, for all vertices u ∈ V . Overall, this step requires O(1) rounds in total. Step 2: Communicating Preliminary Information. Before constructing the edge sets EC and EB , we first require the communication of some preliminary information. Namely, the objective of this step is to construct the values { (c(u), dG (c(u), u) + dG (u, t)) : t ∈ Nk (u) } and 44

{ (c(u), dG (c(u), u) + ωG (u, t)) : { u, t } ∈ E } for all vertices u ∈ V , and to communicate these values to the respective vertices. We do so in the following way: Following from Step 0, for every vertex u ∈ V , there exists a contiguous segment of machines M (u) that contains the edges incident to u in E ∪ Ek . In c(u) knows the k-nearest neighbourhood Nk (u) and the value particular, the leader machine M (u, c(u), dG (u, c(u))). c(u) broadcasts the value (u, c(u), dG (u, c(u))) to the machines in M (u) (using 1. M Lemma 2.5). 2. For every vertex t ∈ Nk (u), we construct the request packet (Rk−near , t, c(u), dG (u, c(u)) + dG (u, t)), which is done locally on the machines M (u). 3. For every edge { u, t } ∈ E (and for u = t), we construct the request packet (Radj , t, c(u), dG (u, c(u)) + ωG (u, t)), which is also done locally on the machines M (u). By applying a sorting procedure (Lemma 2.5), every vertex t ∈ V now has the packets • (Rk−near , t, c(u), dG (u, c(u)) + dG (u, t)) for every vertex u ∈ V such that t ∈ Nk (u), and • (Radj , t, c(v), dG (v, c(v)) + ωG (v, t)) for every vertex v such that { v, t } ∈ E (or v = t). c(t). This stored on a (possibly different) contiguous segment of machines M (t) with leader M entire step runs in O(1) rounds. Step 3: Identifying Bad Vertices B. Recalling the definition of a bad vertex, it suffices for each vertex t ∈ V to count the number of packets of the form (Rk−near , t, . . .), which we execute by performing the prefix sum and sorting sub-routines in Lemma 2.5. At the end of this c(t) knows the number of packets (Rk−near , t, . . .). More concretely, procedure, the leader M defining ( 1 if | { (Rk−near , t, . . .) } | > k 2 bt = 0 otherwise, c(t) determines the value (t, bt ) and distributes this value to the other machines in M (t) M (using Lemma 2.5). Overall, this entire step runs in O(1) rounds. Step 4: Building Edges in EC . For every vertex t ∈ / B, our objective is the following: For every pair of request packets (Rk−near , t, sa , wa ) and (Radj , t, sb , wb ), create a new edge { sa , sb } with the edge weight (wa + wb ). For ease of notation, denote Kt = { (c(u), dG (u, c(u)) + dG (u, t)) : t ∈ Nk (u) } , At = { (c(v), dG (v, c(v)) + ωG (v, t)) : { t, v } ∈ E ∨ t = v } , with at = |At |. Our plan is to create at duplicates of the set Kt , and “label” each duplicate with a value from At . Therefore, we perform the following: 45

1. We first apply Lemma A.1 (Kt , 1), (Kt , 2), . . . , (Kt , at ).

to

create

at

duplicates

of

Kt

in

the

form

2. We next apply Lemma A.2 to relabel each duplicate with a value in At . In other words, denoting At = { (s1 , w1 ), (s2 , w2 ), . . . , (sat , wat ) }, we now have the duplicates in the form of (Kt , (s1 , w1 )), (Kt , (s2 , w2 )), . . . , (Kt , (sat , wat )). 3. Lastly, for each duplicate (Kt , (sj , wj )), we re-construct each packet in Kt from (Rk−near , t, s, w) into the edge ({ s, sj } , w + wj ). P Since t ∈ / B, we have that |Kt | ≤ k 2 . Additionally, we also observe that t∈B / at ∈ O(|E|). 2 γ Lastly recalling that k ∈ O(n ) by assumption, we find that the above procedure can be executed in O(1) rounds with Õ(|E|k 2 ) additional memory. This completes the construction of the edge set EC . Step 5: Building Edges in EB . For every vertex t ∈ B, we perform a simple procedure across the machines in M (t) (from Step 3) to construct edges of EB : • For every request packet (Rk−near , t, sa , wa ) received, construct the value ({ t, sa } , wa ). • For every request packet (Radj , t, sb , wb ) received, construct the value ({ t, sb } , wb ). This can be done entirely locally, and completes the construction of the edge set EB . Claim 7.10. There exists a randomised algorithm to construct the graph GS (as defined in the earlier modified construction) w.h.p. in the sublinear MPC model in O(1) rounds with Õ(|E|k 2 ) total memory. Proof. We apply the algorithm as described above to construct the edge sets EC (in Step 4) and EB (in Step 5), which completes the construction of GS . By the description of the algorithm, we observe each step only requires O(1) rounds, and therefore the entire algorithm runs in O(1) rounds as well. Moreover, only Step 4 requires Õ(|E|k 2 ) additional memory, with the remaining steps only needing Õ(|E| + nk) total memory (with the extra O(nk) memory needed to store the edge set Ek ). Therefore, it suffices to have Õ(|E|k 2 ) total memory overall. The Final Proof. We summarise this section on the skeleton graph with the proof for Lemma 3.2. Proof of Lemma 3.2. By Claim 7.10, we construct the graph GS = (VS , ES ) for G as defined in the modified construction in O(1) rounds and Õ(|E|k 2 ) total memory. By Claim 7.9, we find that GS is indeed a skeleton graph for G, with the added property that |ES | ∈ O(|E|k 2 ) as claimed.

References [ABB+ 19]

Sepehr Assadi, Mohammad Hossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1616–1635. Society for Industrial and Applied Mathematics, 2019.

46

[ABJ+ 25]

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

[ADD+ 93]

Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81–100, 1993.

[AG18]

Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: dual primal algorithms for maximum matching under resource constraints. ACM Transactions on Parallel Computing (TOPC), 4(4):1–40, 2018.

[AGM12]

Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 459–467. SIAM, 2012.

[ANO+ 14]

Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC), pages 574–583, New York, New York. Association for Computing Machinery, 2014. isbn: 9781450327107.

[ASS+ 18]

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

[ASW19]

Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well-connected components in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 461–470, New York, NY, USA. Association for Computing Machinery, 2019. isbn: 9781450362177.

[ASZ20]

Alexandr Andoni, Clifford Stein, and Peilin Zhong. Parallel approximate undirected shortest paths via low hop emulators. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 322–335, Chicago, IL, USA. Association for Computing Machinery, 2020. isbn: 9781450369794.

[BBD+ 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 Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 481–490, New York, NY, USA. Association for Computing Machinery, 2019. isbn: 9781450362177.

[BCC+ 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), pages 391– 400, 2024.

[BDE+ 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), pages 1615–1636. IEEE, 2019.

47

[BDG+ 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 (SPAA), pages 118–128, New York, NY, USA. Association for Computing Machinery, 2021. isbn: 9781450380706.

[BDH18]

Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Semimapreduce meets congested clique. arXiv preprint arXiv:1802.10297, 2018.

[BEF+ 21]

MohammadHossein Bateni, Hossein Esfandiari, Manuela Fischer, and Vahab Mirrokni. Extreme k-center clustering. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 35 of number 5, pages 3941–3949, 2021.

[BEG+ 21]

Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: quantum and mapreduce. Journal of the ACM (JACM), 68(3):1–41, 2021.

[BEL+ 22]

Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, and Slobodan Mitrović. Massively Parallel Algorithms for Small Subgraph Counting. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 245 of Leibniz International Proceedings in Informatics (LIPIcs), 39:1–39:28, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. isbn: 978-3-95977-249-5.

[BHH23]

Soheil Behnezhad, Mohammadtaghi Hajiaghayi, and David G Harris. Exponentially faster massively parallel maximal matching. Journal of the ACM, 70(5):1–18, 2023.

[BKS17]

Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. J. ACM, 64(6):40:1–40:58, 2017.

[BW18]

Aditya Bhaskara and Maheshakya Wijewardena. Distributed clustering via LSH based data partitioning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 570–579, 2018.

[CC11]

Shumo Chu and James Cheng. Triangle listing in massive networks and its applications. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 672–680, New York, NY, USA. Association for Computing Machinery, 2011. isbn: 9781450308137.

[CC22]

Sam Coy and Artur Czumaj. Deterministic massively parallel connectivity. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 162–175, New York, NY, USA. Association for Computing Machinery, 2022. isbn: 9781450392648.

[CCM23]

Sam Coy, Artur Czumaj, and Gopinath Mishra. On parallel k-center clustering. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 65–75, New York, NY, USA. Association for Computing Machinery, 2023. isbn: 9781450395458.

48

[CDK+ 21]

Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. Fast approximate shortest paths in the congested clique. Distributed Computing, 34(6):463– 487, 2021.

[CDM+ 26]

Kyungjin Cho, Michal Dory, Yannic Maus, and Tijn de Vos. Deterministic distance approximation in mpc via improved hitting sets. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 366–379, Royal Holloway, University of London, London, United Kingdom. Association for Computing Machinery, 2026. isbn: 9798400727610. doi: 10 . 1145 / 3816782 . 3819203. url: https://doi.org/10.1145/3816782.3819203.

[CDP20]

Artur Czumaj, Peter Davies, and Merav Parter. Simple, deterministic, constant-round coloring in the congested clique. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC), pages 309–318, New York, NY, USA. Association for Computing Machinery, 2020. isbn: 9781450375825.

[CFG+ 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 Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 471–480. ACM, 2019.

[CGJ+ 24]

Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), 50:1–50:20, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. isbn: 978-3-95977322-5.

[CŁM+ 18]

Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 471–484, New York, NY, USA. Association for Computing Machinery, 2018. isbn: 9781450355599.

[CLN+ 21]

Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svensson. Parallel and efficient hierarchical k-median clustering. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 20333–20345. Curran Associates, Inc., 2021.

[CMZ22]

Vincent Cohen-Addad, Vahab Mirrokni, and Peilin Zhong. Massively parallel k-means clustering for perturbation resilient instances. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning (ICML), volume 162, pages 4180– 4201, 2022.

[CZ24]

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

49

[DDŁ+ 24]

Laxman Dhulipala, Michael Dinitz, Jakub Łącki, and Slobodan Mitrović. Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling. In Dan Alistarh, editor, Proceedings of the 38th International Symposium on Distributed Computing (DISC), volume 319 of Leibniz International Proceedings in Informatics (LIPIcs), 19:1– 19:23, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. isbn: 978-3-95977-352-2.

[DFK+ 21]

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), pages 223–233, New York, NY, USA. Association for Computing Machinery, 2021. isbn: 9781450385480.

[DG04]

Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation (OSDI), volume 4 of number 1, pages 137–150. USA, 2004.

[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 (SPAA), pages 415–426, New York, NY, USA. Association for Computing Machinery, 2024. isbn: 9798400704161.

[DN20]

Michael Dinitz and Yasamin Nazari. Massively Parallel Approximate Distance Sketches. In Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller, editors, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), volume 153 of Leibniz International Proceedings in Informatics (LIPIcs), 35:1–35:17, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. isbn: 978-3-95977-133-7.

[DP22]

Michal Dory and Merav Parter. Exponentially faster shortest paths in the congested clique. Journal of the ACM (JACM), 69(4):1–42, 2022.

[EGN22]

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost Shortest Paths with NearAdditive Error in Weighted Graphs. In Artur Czumaj and Qin Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 227 of Leibniz International Proceedings in Informatics (LIPIcs), 23:1–23:22, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. isbn: 978-3-95977-236-5.

[EN18]

Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):1–29, 2018.

[Erd65]

Paul Erdős. On some extremal problems in graph theory. Israel Journal of Mathematics, 3(2):113–116, 1965.

[FHO22]

Orr Fischer, Adi Horowitz, and Rotem Oshman. Massively parallel computation in a heterogeneous regime. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), pages 345–355, 2022.

[GGJ20]

Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC algorithms for MIS, matching, and coloring on trees and beyond. In Hagit Attiya, editor, Proceedings of the 34th International Symposium on Distributed Computing (DISC), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), 34:1–34:18, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. isbn: 978-3-95977-168-9. 50

[GGK+ 18]

Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld. Improved massively parallel computation algorithms for MIS, matching, and vertex cover. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 129–138, 2018.

[GK25]

Shay Golan and Matan Kraus. String Problems in the Congested Clique Model. In Paola Bonizzoni and Veli Mäkinen, editors, 36th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 331 of Leibniz International Proceedings in Informatics (LIPIcs), 6:1–6:23, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. isbn: 978-3-95977-369-0.

[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), Baltimore, MD, USA. IEEE, November 2019.

[GSZ11]

Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In Proceedings of the 22nd International Conference on Algorithms and Computation (ISAAC), pages 374–383, Yokohama, Japan. Springer-Verlag, 2011. isbn: 9783642255908.

[GU19]

Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1636–1653. SIAM, 2019.

[GWZ25]

Junhao Gan, Anthony Wirth, and Zhuo Zhang. O(1)-round MPC algorithms for multi-dimensional grid graph connectivity, euclidean MST and DBSCAN. In Sudeepa Roy and Ahmet Kara, editors, Proceedings of the 28th International Conference on Database Theory (ICDT), volume 328 of Leibniz International Proceedings in Informatics (LIPIcs), 7:1–7:20, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. isbn: 978-3-95977-364-5.

[HLL18]

Nicholas J. A. Harvey, Christopher Liaw, and Paul Liu. Greedy and local ratio algorithms in the mapreduce model. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 43–52, New York, NY, USA. Association for Computing Machinery, 2018. isbn: 9781450357999.

[HSS19]

MohammadTaghi Hajiaghayi, Saeed Seddighin, and Xiaorui Sun. Massively parallel approximation algorithms for edit distance and longest common subsequence. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1654–1672. SIAM, 2019.

[HT23]

Jacob Holm and Jakub Tětek. Massively parallel computation on embedded planar graphs. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4373–4408. SIAM, 2023.

[IMS17]

Sungjin Im, Benjamin Moseley, and Xiaorui Sun. Efficient massively parallel methods for dynamic programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 798–811, 2017. 51

[JMN+ 24]

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

[JPP+ 25]

Hongyan Ji, Shreyas Pai, Sriram Pemmaraju, and Joshua Sobel. Faster set cover in the MPC model. In Proceedings of the 26th International Conference on Distributed Computing and Networking (ICDCN), pages 144–151, New York, NY, USA. Association for Computing Machinery, 2025. isbn: 9798400710629.

[KLM+ 14]

Raimondas Kiveris, Silvio Lattanzi, Vahab S. Mirrokni, Vibhor Rastogi, and Sergei Vassilvitskii. Connected components in mapreduce and beyond. In Ed Lazowska, Doug Terry, Remzi H. Arpaci-Dusseau, and Johannes Gehrke, editors, Proceedings of the ACM Symposium on Cloud Computing (SoCC), 18:1–18:13. ACM, 2014.

[Koo24]

Jaehyun Koo. An optimal MPC algorithm for subunit-monge matrix multiplication, with applications to lis. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 145–154, 2024.

[KSV10]

Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 938–948. SIAM, 2010.

[LMS+ 11]

Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in mapreduce. In Proceedings of the twentythird annual ACM symposium on Parallelism in algorithms and architectures (SPAA), pages 85–94, 2011.

[Now21]

Krzysztof Nowicki. A deterministic algorithm for the mst problem in constant rounds of congested clique. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1154–1165, New York, NY, USA. Association for Computing Machinery, 2021. isbn: 9781450380539.

[NS22]

Danupon Nanongkai and Michele Scquizzato. Equivalence classes and conditional hardness in massively parallel computations. Distributed computing, 35(2):165–183, 2022.

[PS89]

David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99–116, 1989.

[PT12]

Rasmus Pagh and Charalampos E Tsourakakis. Colorful triangle counting and a mapreduce implementation. Information Processing Letters, 112(7):277–281, 2012.

[RMC+ 13]

Vibhor Rastogi, Ashwin Machanavajjhala, Laukik Chitnis, and Anish Das Sarma. Finding connected components in map-reduce in logarithmic rounds. In Christian S. Jensen, Christopher M. Jermaine, and Xiaofang Zhou, editors, Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE), pages 50–61. IEEE Computer Society, 2013.

[RVW18]

Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and circuits (on lower bounds for modern parallel computation). J. ACM, 65(6):41:1–41:24, 2018.

52

[SV11]

Siddharth Suri and Sergei Vassilvitskii. Counting triangles and the curse of the last reducer. In Proceedings of the 20th International Conference on World Wide Web (WWW), pages 607–614, New York, NY, USA. Association for Computing Machinery, 2011. isbn: 9781450306324.

[TZ05]

Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, January 2005.

[UY90]

Jeffrey D. Ullman and Mihalis Yannakakis. High-probability parallel transitive closure algorithms. In Proceedings of the second annual ACM symposium on Parallel algorithms and architectures (SPAA), pages 200–209, 1990.

[Whi12]

Tom White. Hadoop: The Definitive Guide. O’Reilly Media, Inc., 2012. isbn: 1449311520, 9781449311520.

[ZCF+ 10]

Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: cluster computing with working sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud), 2010.

A

MPC Tools

We describe two tools, the duplication lemma and the labelling lemma, that together enable efficient communication of information between vertices. As a motivating example, suppose each vertex holds k edges that need to be delivered to d other vertices. To facilitate this, we first create d duplicates of each of the k edges and then label each copy with its intended recipient. The labelled messages can then be routed through a sorting procedure. We show that this entire process can be implemented in a constant number of rounds. Lemma A.1 (Duplication). Suppose we have n sets S1 , S2 , . . . , Sn of items such that each set Si occupies at most O(k) space for some integer k > 0. For every set Si , the task is to create di ≥ 1 duplicates of the set in the form (Si , 1), (Si , 2), . . . , (Si , di ). P Given that k ∈ O(nγ ), in the sublinear MPC model with O (nk + ni=1 kdi ) total memory, there exists a deterministic algorithm to accomplish this task for all sets Si . This algorithm runs in O(1) rounds. Proof. For all i ∈ { 1, 2, . . . , n }, we may assume that Si and di are appropriately labelled such that c(i) that completely stores the tuple (Si , di ). there exists a single machine M To facilitate the duplication procedure, our goal is to first create “gaps” of memory between the machines; we then fill in the gaps by duplicating the sets. For simplicity, we may assume that each machine has exactly enough local memory to store a single tuple of the form (S, d), where S is a set of k items and d is an integer; the procedure can be generalised for the case of larger local memory. 1. Define the integers p0 , p1 , p2 , . . . , pn as follows: p0 = 0, pi = di + pi−1 . Using the prefix sum sub-routine in Lemma 2.5, these integers { pi } can be determined in c(i) knows the value pi−1 . O(1) rounds. We then sort the values such that each machine M 53

c(i) sends the tuple (Si , di ) to the machine with ID (pi−1 + 1). By our total 2. The machine M memory constraints (and our simplifying assumption on the local memory), we have sufficiently many machines to perform this communication. Denote M (i) as the contiguous set of machines with IDs (pi−1 + 1), (pi−1 + 2), . . . , (pi−1 + di ), and c(i) as the machine in M (i) with the smallest ID. After the communication procedure in Step 2, M c(i) knows the value (Si , di ) while the remaining machines in M (i) are empty. Subsequently, M c(i) M broadcasts the value (Si , pi−1 ) to the machines in M (i) in O(1) rounds (Lemma 2.5). This enables us to create the duplicates (Si , 1), (Si , 2), . . . , (Si , di ) locally across the machines in M (i), and we are done. Overall, this requires O(1) rounds as claimed. Lemma A.2 (Labelling). Suppose we have n sets S1 , S2 , . . . , Sn of items such that each set Si occupies at most O(k) space for some integer k > 0. For every set Si , there also exist di ≥ 1 duplicates of Si in the form (Si , 1), (Si , 2), . . . , (Si , di ). Our task is to label each duplicate (Si , j) with a label ui,j , where each label ui,j occupies O(1) space. P Given that k ∈ O(nγ ), in the sublinear MPC model with O (nk + ni=1 kdi ) total memory, there exists a deterministic algorithm to accomplish this task for all sets Si . This algorithm runs in O(1) rounds. Proof. We assume that the labels ui,j and the sets (Si , j) are appropriately labelled such that by performing a sorting procedure (Lemma 2.5), there exists a single machine M (i, j) that completely stores the tuple (Si , j, ui,j ). Subsequently, by means of local computation, we can then relabel (Si , j) into (Si , ui,j ), and we are done.

B

Reporting the Path

In this section, our task is the following: Given a weighted undirected graph G = (V, E), construct a distance oracle that receives a pair of vertices (u, v) as query and returns in constant rounds a path P in G from u to v such that ω(P ) is a constant approximation of dG (u, v). We call this a path-reporting distance oracle. We show that this can be accomplished by modifications to our distance oracle algorithms. Namely, our aim is to show the following lemma, which can be seen as a modification of Lemma 4.2. We remark that when applying this lemma, the connectivity assumption can be relaxed using Lemma 2.6 as before (noting that the technique of Lemma 2.6 almost immediately applies to path-reporting oracles as well). Lemma B.1. Let G = (V, E) be a connected, weighted graph with n vertices, and let c > 0 be a constant such that |E| ∈ Õ(n1+c/2 ). Suppose that for every vertex u ∈ V , we are given the set {(u, t) : t ∈ Ñk (u)}, where Ñk (u) is an a-approximate k-nearest neighbourhood of u with k = nc/4 . Given that c ≤ γ, in the heterogeneous MPC model with Õ(n1+c ) total memory, there exists a randomised algorithm that w.h.p. constructs an O(1/c)-approximate path-reporting distance oracle in O(log a + log log n) rounds. Every subsequent query can then be answered in O(1) rounds. The algorithms in this section are presented primarily as modifications to algorithms discussed previously in the main body of this work, and will be nearly identical in proof to those stated in the main body. Therefore for the sake of clarity and presentation, we only sketch these modifications while providing sufficient exposition to motivate them. 54

We begin by recalling the distance oracle construction of Lemma 4.2, which consists of the following two components; here, k is some small polynomial of n determined by the input parameters. • The k-nearest edge set Ek of G. • A constant-stretch spanner F = (VS , EF ) of the skeleton graph GS = (VS , ES ). A distance query (u, v) is answered as follows. If u ∈ Nk (v) or v ∈ Nk (u), then return the edge weight ωEk (u, v). Otherwise, we return δ(u, v) := min (ωEk (u, x) + dF (x, y) + ωEk (y, v)). x,y∈VS

We had previously shown that this can be computed in O(1) rounds and yields a constant approximation of dG (u, v). Our aim is to output a path in the original graph that has length at most δ(u, v). Specifically, there are two components to this task: 1. For each edge { u, v } ∈ Ek , we should have knowledge of, or be able to compute, some shortest path P from u to v. 2. Likewise for each edge { x, y } ∈ EF ⊆ ES , we should have knowledge of, or be able to compute, a path P from x to y such that ω(P ) ≤ ωES (x, y). We discuss each component separately before combining them to form the proof of Lemma B.1. Recovering paths in Ek . The most immediate attempt would be to modify the building block algorithms Lemma 3.3 and Lemma 3.4 such that each time we shortcut a path (i.e., construct a new edge from a path in the original graph), we also maintain the full path that was shortcut. While this works, we will consider a slightly more space-efficient method that uses a property of k-nearest neighbourhoods. Specifically, let (u, t) be any vertex pair with t ∈ Nk (u), and let P be any shortest path from u to t. Observe that for any vertex v along P , we necessarily have that v ∈ Nk (u) as well, i.e., all the vertices in P are in the k-nearest neighbourhood of u. Therefore for each edge { u, t } ∈ Ek , instead of storing the entire shortest path from u to t, we just store the last edge along this path. Concretely, alongside the k-nearest edge set Ek , we also desire some set Lk ⊆ V 3 that satisfies the following properties: • (Size-bounded ) |Lk | ≤ nk. • (Soundness) (u, z, t) ∈ Lk only if t ∈ Nk (u) and either (1) the edge { t, z } is on some shortest path from u to t or (2) t = z = u. • (Completeness) For all pairs u, t ∈ V with t ∈ Nk (u), there exists some vertex z ∈ V such that (u, z, t) ∈ Lk . Note that for a fixed graph G and integer k, there may be multiple candidate choices for Lk . We first show for any pair of vertices u, t ∈ V such that t ∈ Nk (u), the set Lk is sufficient to recover some shortest path from u to t.

55

Lemma B.2. Let G = (V, E) be a connected, weighted graph with n vertices, and let integer k > 0 be a parameter. Consider any set Lk with the properties specified above. For any pair of vertices u, t ∈ V such that t ∈ Nk (u), there exists a path u = v1 − v2 − v3 − . . . − vm = t in G with m ≤ k such that (1) the length of this path is dG (u, t) and (2) for all integers 1 ≤ i ≤ m − 1 we have (u, vi , vi+1 ) ∈ Lk . Proof. We first note that any shortest path from u to t necessarily has at most k distinct vertices (including u and t); otherwise, the first k vertices along the path, counting from u, have strictly shorter distances to u than that of t, hence contradicting t ∈ Nk (u) (recall that we consider only positive edge weights). Consequently, for any shortest path from u to t, all vertices along the path are necessarily in Nk (u) as well. We will prove the claim by induction on dG (u, t). In the base case, we have dG (u, t) = 0 and t = u necessarily; the claim immediately follows by the properties of Lk . In the inductive case, suppose the claim holds for all distances at most ℓ and that dG (u, t) = ℓ+1. By the properties of Lk , observe that there exists some vertex z ∈ Nk (u) such that (u, z, t) ∈ Lk . In particular, notice that dG (u, z) < dG (u, t) – this follows from the observation that the edge { z, t } is on some shortest path from u to t, and hence dG (u, t) = dG (u, z) + ωG (z, t). Therefore, applying the induction hypothesis on (u, z), there exists a path u = v1 − v2 − . . . − vm = z of length dG (u, z) such that (u, vi , vi+1 ) ∈ Lk for all integers 1 ≤ i ≤ m − 1. The claim now follows by directly appending the edge { z, t } to the end of this path and noticing that the new path indeed has length exactly dG (u, t); by an earlier observation, we find that the new path has at most k distinct vertices as well. We now show that given approximate k-nearest neighbourhoods for all vertices, we can efficiently construct a set Lk satisfying the above properties alongside constructing the k-nearest set Ek . In particular, it suffices for us to introduce small modifications to the algorithm of Lemma 4.1. Lemma B.3. Let G = (V, E) be a connected, weighted graph with n vertices, and let integer k > 0 be a parameter. Suppose that for every vertex u ∈ V , we are given the set {(u, t) : t ∈ Ñk (u)}, where Ñk (u) is an a-approximate k-nearest neighbourhood of u. Given that k 2 ∈ O(nγ ), in the sublinear MPC model with Õ(|E|+nk 2 ) total memory, there exists a deterministic algorithm for constructing the k-nearest edge set Ek and some set Lk (satisfying the above properties) for G in O(log log d + log a) rounds, where d is the weighted diameter of G. Proof Sketch. Recall that the original algorithm of Lemma 4.1 was simply a direct combination of two previous algorithms: Lemma 3.3 and Lemma 3.4, the algorithms for constructing a k-nearest hopset and extracting exact k-nearest neighbourhoods respectively. Separately, we show how to modify these algorithms to yield the desired output. Modifying Lemma 3.3. Recall that each hopset edge represents some path in the original graph G. We modify the output of the algorithm such that for each edge e in the hopset H, we also include the first and last edges of the path represented by e. Modifying Lemma 3.4. We modify the algorithm such that in each iteration i of the graph exponentiation, we update both Ek and Lk corresponding to the new “local” view of the knearest neighbourhoods for each vertex. Crucially for Lk , we want to maintain paths in the original graph G instead of the graph G ∪ H – this is enabled by the above modification to Lemma 3.3. After sufficient iterations, the algorithm outputs both Ek and Lk corresponding to the true k-nearest neighbourhoods. 56

Recovering paths in GS . Again, the most obvious attempt seems to be modifying the algorithm of Lemma 3.2 such that each time we shortcut a path in G to form an edge in GS , we also maintain the original path in G. However, we will utilise our specific implementation of the skeleton graph algorithm to suggest a more space-efficient procedure. Consider a skeleton graph GS = (VS , ES ) constructed using Lemma 3.2 from a graph G = (V, E) and parameter k. We recall the algorithm description for Lemma 3.2. Namely, each edge { x, y } ∈ ES (oriented appropriately) satisfies one of the following cases. Case 1. There exists a vertex u ∈ V such that ωES (x, y) = dG (x, u) + dG (u, y) satisfying that x, y ∈ Nk (u). Case 2. There exists a vertex v ∈ V such that ωES (x, y) = ωG (x, v) + dG (v, y) satisfying that y ∈ Nk (v), and { x, v } ∈ E or x = v. Case 3. There exist vertices u, t, v ∈ V such that all of the following hold: • x ∈ Nk (u) and y ∈ Nk (v). • t ∈ Nk (u), and either { t, v } ∈ E or t = v. • ωES (x, y) = dG (x, u) + dG (u, t) + ω(t, v) + dG (v, y). Specifically, the edges in the edge set EB fall under Cases 1 and 2 while the edges in the edge set EC fall under Case 3 (recalling the definition of EB and EC from Section 7). This motivates us to modify the algorithm for Lemma 3.2 in the following way: When we construct any edge { x, y } ∈ ES , we maintain which of the three cases this edge falls under as well as the vertices in G that were used to construct this edge. Concretely, alongside the skeleton graph GS = (VS , ES ), we also desire some set LS ⊆ ES × 3 (V ⊔ V 5 ) × { 1, 2, 3 } satisfying the following properties. • (Size-bounded ) |LS | = |ES |. • (Soundness) For any ({ x, y } , τ, i) ∈ LS , we have the following; assume that { x, y } is oriented appropriately such that it satisfies at least one of the above cases. – If { x, y } satisfies Case 1, then i = 1 and τ = (x, u, y) for some vertex u ∈ V such that ωES (x, y) = dG (x, u) + dG (u, y) and x, y ∈ Nk (u). – If { x, y } satisfies Case 2, then i = 2 and τ = (x, v, y) for some vertex v ∈ V such that ωES (x, y) = ωG (x, v) + dG (v, y), y ∈ Nk (v), and either { x, v } ∈ E or x = v. – If { x, y } satisfies Case 3, then i = 3 and τ = (x, u, t, v, y) ∈ V 5 , where u, t, v ∈ V are vertices that satisfy the definition of Case 3. If { x, y } satisfies multiple cases, then τ and i may be assigned any value that matches at least one of these specifications. • (Completeness) For any { x, y } ∈ ES , we have that ({ x, y } , τ, i) ∈ LS for some τ ∈ V 3 ⊔ V 5 and i ∈ { 1, 2, 3 }. As before, we remark that for a fixed skeleton graph GS , there may be multiple candidate choices for LS . It is not difficult to see that given any path P of the form x = v1 − v2 − v3 − . . . − vm = y 57

in GS , one can use LS to “sketch” a walk in the original graph G of length at most ω(P ); we refer to the proof sketch of Lemma B.1 for the details. In the following lemma, we show that the skeleton graph algorithm of Lemma 3.2 can be slightly modified to also output LS alongside GS . Lemma B.4. Let G = (V, E) be a connected, weighted graph with n vertices, and let k > 1 be an integer. Suppose the k-nearest edge set Ek for G is given. If k 2 ∈ O(nγ ), then in the sublinear MPC model with Õ(|E|k 2 ) total memory, there exists a randomised algorithm that w.h.p. constructs a skeleton graph GS = (VS , ES ) and some set LS (satisfying the above properties) in O(1) rounds. Proof Sketch. We make a simple modification to the algorithm description of Lemma 3.2. Namely in Step 2, for each vertex u ∈ V we modify the request packets to also include the vertex ID of u before communicating these packets to the respective vertices. This provides the vertices t ∈ V in Steps 4 and 5 with sufficient information to compute LS alongside the edges ES . Notice that the total space needed to store LS is at most O(|ES |) ⊆ O(|E|k 2 ), and therefore we have sufficient total memory. The path-reporting distance oracle. We now combine Lemma B.3 and Lemma B.4 in a nearly identical fashion to how we combined Lemma 4.1 and Lemma 3.2 to form the algorithm of Lemma 4.2. Proof Sketch of Lemma B.1. We apply the same preprocessing algorithm technique as the proof of Lemma 4.2, but replace Lemma 4.1 with Lemma B.3 and Lemma 3.2 with Lemma B.4. At the end of this procedure, we have constructed the following: • The k-nearest edge set Ek . • The constant-stretch spanner F = (VS , EF ) of the skeleton graph GS = (VS , ES ), stored on the single near-linear machine M ∗ . • Sets Lk and LS with the properties as specified previously. We may also assume that for each vertex u ∈ V , the edge set { { u, t } : t ∈ Nk (u) } and the set { (u, z, t) ∈ Lk : t, z ∈ V } are stored locally on a single machine M (u). We now perform two last additional preprocessing steps: 1. We filter out LS to only contain information about the edges in F . Specifically, we construct the set LF := (EF × (V 3 ⊔ V 5 ) × { 1, 2, 3 }) ∩ LS ; we proceed to collect LF , which is now near-linear-sized, onto the machine M ∗ . This can be done in O(1) rounds. 2. For each vertex u ∈ V , the machine M (u) locally computes some shortest path from u to each vertex t ∈ Nk (u) (Lemma B.2). Notice that this requires at most O(k 2 ) = O(nc/2 ) ⊆ O(nγ ) space per vertex u, and thus we have sufficient local memory. This requires no communication rounds. We now describe the procedure for answering path-reporting queries. For each query (u, v), the case where u ∈ Nk (v) or v ∈ Nk (u) is handled by simply returning the path constructed by the local machine M (v) or M (u) respectively. For the remainder of the proof sketch, we focus on the case when u ∈ / Nk (v) and v ∈ / Nk (u). 58

Following the same answering-query procedure of Lemma 4.2, we first determine the vertices x, y ∈ VS that minimise the distance estimate δ(u, v). The vertices (u, v, x, y) are then communicated to the near-linear machine M ∗ . Using F and LF , M ∗ now locally computes a sequence of vertex pairs (u, w2 ) = (w1 , w2 ), (w2 , w3 ), . . . , (wℓ−1 , wℓ ) = (wℓ−1 , v) ∈ V 2 and a sequence b1 , b2 , . . . , bℓ−1 ∈ { 1, 2 } with the following properties: • (No repeat vertices) wi ̸= wj for any i ̸= j. • (Size-bounded ) ℓ ∈ O(|VS |) ⊆ O((n log k)/k). • (Pairs are k-nearest apart or share an edge) For each pair (wi , wi+1 ), we have that (1) if bi = 1 then either wi ∈ Nk (wi+1 ) or wi+1 ∈ Nk (wi ); (2) if bi = 2 then { wi , wi+1 } ∈ E. • (Good approximation) For each integer 1 ≤ i ≤ ℓ − 1, we denote ( ωEk (wi , wi+1 ) if bi = 1 ∆i := ωG (wi , wi+1 ) if bi = 2, and let ∆ :=

Pℓ−1

i=1 ∆i . We have that ∆ is at most δ(u, v).

It can be quickly verified that such a sequence of vertex pairs indeed exists and can be computed entirely using F and LF . Using the paths computed in the last preprocessing step, we use O(1) rounds to construct a walk between u and v in G of length at most ∆ and with at most O(k · ℓ) ⊆ O(n log k) ⊆ Õ(n) edges; notice that the lack of repeat vertices in the above sequence allows this walk construction to be executed without any added complications. With one last O(1) rounds, the entire walk can be collected onto the near-linear machine M ∗ . Local computation on M ∗ simplifies this walk into a path between u and v of length at most ∆ by removing cycles.

59

Related documents

• Improved Massively Parallel Shortest Path Computation#1341671
• Towards Dynamic Top-$k$ Simple Shortest Paths#1357259
• Approximation and Hardness Results for the Parallel-Block Construction Problem / Arivarasan Karmegam, Alexandru Popa, Lucianna Kiffer, Antonio Fernández Anta#1188461
• Faster high-accuracy multicommodity flow in dense graphs#1215758
• Terminology for Benchmarking Link-State IGP Data-Plane Route Convergence#231839