A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \sf CONGEST model); here $n$ is the number of nodes in the network, $D$ is its (hop) diameter, and edge weights are positive integers from 1 to $\operatorname{poly}(n)$. This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized $(1+o(1))$-approximation $\tilde{O}(\sqrt{n}D^{1/4}+D)$-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as $n^{1/8}$, and (ii) the $O(\epsilon^{-1}\log\epsilon^{-1})$-approximation factor of Lenzen and Patt-Shamir's $\tilde{O}(n^{1/2+\epsilon}+D)$-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use $\tilde{O}(\cdot)$ to hide polylogarithmic factors in $n$.) Our running time matches the known time lower bound of $\Omega(\sqrt{n/\log n}+D)$ [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40--57]. It also implies a $(2+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an $(n^{o(1)},o(1))$-hop set of size $n^{1+o(1)}$. We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a $(1+o(1))$-approximation $n^{o(1)}$-time algorithm on congested cliques, and (ii) a $(1+o(1))$-approximation $n^{o(1)}$-pass $n^{1+o(1)}$-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14].