Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds

Abstract

We study computing {\em all-pairs shortest paths} (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from every other node using communication. The problem admits $(1+o(1))$-approximation $\tilde O(n)$-time algorithms ~\cite{LenzenP-podc15,Nanongkai-STOC14}, which are matched with $\tilde Ω(n)$-time lower bounds~\cite{Nanongkai-STOC14,LenzenP_stoc13,FrischknechtHW12}\footnote{$\tilde Θ$, $\tilde O$ and $\tilde Ω$ hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios.}. No $ω(n)$ lower bound or $o(m)$ upper bound were known for exact computation. In this paper, we present an $\tilde O(n^{5/4})$-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive $O(m)$-time algorithm when the network is not so sparse. Our result also holds for the case where edge weights are {\em asymmetric} (a.k.a. the directed case where communication is bidirectional). Our techniques also yield an $\tilde O(n^{3/4}k^{1/2}+n)$-time algorithm for the {\em $k$-source shortest paths} problem where we want every node to know distances from $k$ sources; this improves Elkin's recent bound~\cite{Elkin-STOC17} when $k=\tilde ω(n^{1/4})$.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.