Abstract We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take $$\textrm{poly}(\log {\log {n}})$$ poly ( log log n ) rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with n vertices and m edges. Our first contribution is a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation algorithm for Single-Source Shortest Paths (SSSP) that takes $$\textrm{poly}(\log {\log {n}})$$ poly ( log log n ) rounds in the near-linear MPC model, where the memory per machine is $$\tilde{O}(n)$$ O ~ ( n ) and the total memory is $$\tilde{O}(mn^{\rho })$$ O ~ ( m n ρ ) , where $$\rho $$ ρ is a small constant. Our second contribution is a distance oracle that allows to approximate the distance between any pair of vertices. The distance oracle is constructed in $$\textrm{poly}(\log {\log {n}})$$ poly ( log log n ) rounds and allows to query a $$(1+\epsilon )(2k-1)$$ ( 1 + ϵ ) ( 2 k - 1 ) -approximate distance between any pair of vertices u and v in O(1) additional rounds. The algorithm is for the near-linear memory MPC model with total memory of size $$\tilde{O}((m+n^{1+\rho })n^{1/k})$$ O ~ ( ( m + n 1 + ρ ) n 1 / k ) , where $$\rho $$ ρ is a small constant. While our algorithms are for the near-linear MPC model, in fact they only use one machine with $$\tilde{O}(n)$$ O ~ ( n ) memory, where the rest of machines can have sublinear memory of size $$O(n^{\gamma })$$ O ( n γ ) for a small constant $$\gamma < 1$$ γ < 1

We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take poly(łogłogn ) rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with n vertices and m edges.

Near-additive (aka (1+ε,β)β-) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related problems in distributed, streaming and dynamic settings.

We study a (1+ε)-approximate single-source shortest paths (henceforth, (1+ε)-SSSP) in n-vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A randomized algorithm with polylogarithmic time and slightly super-linear work Õ(|E|• n^ρ), for an arbitrarily small ρ>0, was given by Cohen (10) more than 25 years ago. Exciting progress on this problem was achieved in recent years (4, 17, 19, 35), culminating in randomized polylogarithmic time and Õ(|E|) work. However, the question of whether there exists a deterministic counterpart of Cohen's algorithm remained wide open.

Given a pair of parameters α ≥ 1,β ≥ 0, a subgraph G'=(V,H) of an n-vertex unweighted undirected graph G=(V,E) is called an (α,β)-spanner if for every pair u,ν ∈ V of vertices, we have dG' (u,ν)≤ α dG (u,α)+β. If β=0 the spanner is called a multiplicative α-spanner, and if α = 1+ε, for an arbitrarily small ε>0, the spanner is said to be near-additive.