Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
share
In the distributed all-pairs shortest paths problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity). The problem admits (1+o(1))-approximation Θ̃(n)-time algorithm and a nearly-tight Ω̃(n) lower bound [Nanongkai, STOC'14; Lenzen and Patt-Shamir PODC'15][Θ̃, Õ and Ω̃ hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios LenzenP_podc13,HolzerW12,PelegRT12,Nanongkai-STOC14.]. For the exact case, Elkin [STOC'17] presented an O(n^5/3^2/3 n) time bound, which was later improved to Õ(n^5/4) [Huang, Nanongkai, Saranurak FOCS'17]. It was shown that any super-linear lower bound (in n) requires a new technique [Censor-Hillel, Khoury, Paz, DISC'17], but otherwise it remained widely open whether there exists a Õ(n)-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) Õ(n)-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous Õ(n^5/4) bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous Õ(n^5/4) bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in 1, 2, ... poly(n)). ...
READ FULL TEXT