Massively parallel algorithms for approximate shortest paths

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}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>poly</mml:mtext> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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 )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation algorithm for Single-Source Shortest Paths (SSSP) that takes $$\textrm{poly}(\log {\log {n}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>poly</mml:mtext> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> rounds in the near-linear MPC model, where the memory per machine is $$\tilde{O}(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> and the total memory is $$\tilde{O}(mn^{\rho })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>ρ</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , where $$\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ρ</mml:mi> </mml:math> 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}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>poly</mml:mtext> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> rounds and allows to query a $$(1+\epsilon )(2k-1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> <mml:mo>)</mml:mo> <mml:mo>(</mml:mo> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -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})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>+</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ρ</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , where $$\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ρ</mml:mi> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> memory, where the rest of machines can have sublinear memory of size $$O(n^{\gamma })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>γ</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for a small constant $$\gamma &lt; 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>γ</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn>