Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time

Understand

In the {\em 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 {\em time complexity}).

• The problem admits $(1+o(1))$-approximation $\tilde\Theta(n)$-time algorithm and a nearly-tight $\tilde \Omega(n)$ lower bound [Nanongkai, STOC'14; Lenzen and Patt-Shamir PODC'15]\footnote{$\tilde \Theta$, $\tilde O$ and $\tilde \Omega$ hide polylogarithmic factors.
• Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios~\cite{LenzenP_podc13,HolzerW12,PelegRT12,Nanongkai-STOC14}.}.
• For the exact case, Elkin [STOC'17] presented an $O(n^{5/3} \log^{2/3} n)$ time bound, which was later improved to $\tilde O(n^{5/4})$ [Huang, Nanongkai, Saranurak FOCS'17].