# A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Henzinger MH, Krinninger S, Nanongkai D. 2021. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 50(3), STOC16-98-STOC16-137.

Download (ext.)

https://arxiv.org/abs/1504.07056
[Preprint]

*Journal Article*|

*Published*|

*English*

**Scopus indexed**

Author

Henzinger, Monika

^{ISTA}^{}; Krinninger, Sebastian; Nanongkai, DanuponAbstract

We present a deterministic (1+π(1))-approximation (π1/2+π(1)+π·1+π(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \sf CONGEST model); here π is the number of nodes in the network, π· is its (hop) diameter, and edge weights are positive integers from 1 to poly(π). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+π(1))-approximation πΜ (πβπ·1/4+π·)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as π1/8, and (ii) the π(πβ1logπβ1)-approximation factor of Lenzen and Patt-Shamir's πΜ (π1/2+π+π·)-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use πΜ (β
) to hide polylogarithmic factors in π.) Our running time matches the known time lower bound of Ξ©(π/logπβΎβΎβΎβΎβΎβΎβΎβ+π·) [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+π(1))-approximation (π1/2+π(1)+π·1+π(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 (ππ(1),π(1))-hop set of size π1+π(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+π(1))-approximation ππ(1)-time algorithm on congested cliques, and (ii) a (1+π(1))-approximation ππ(1)-pass π1+π(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].

Publishing Year

Date Published

2021-05-01

Journal Title

SIAM Journal on Computing

Volume

50

Issue

3

Page

STOC16-98-STOC16-137

ISSN

eISSN

IST-REx-ID

### Cite this

Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths.

*SIAM Journal on Computing*. 2021;50(3):STOC16-98-STOC16-137. doi:10.1137/16m1097808Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2021). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths.

*SIAM Journal on Computing*. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/16m1097808Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. βA Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.β

*SIAM Journal on Computing*. Society for Industrial & Applied Mathematics, 2021. https://doi.org/10.1137/16m1097808.M. H. Henzinger, S. Krinninger, and D. Nanongkai, βA deterministic almost-tight distributed algorithm for approximating single-source shortest paths,β

*SIAM Journal on Computing*, vol. 50, no. 3. Society for Industrial & Applied Mathematics, pp. STOC16-98-STOC16-137, 2021.Henzinger, Monika H., et al. βA Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.β

*SIAM Journal on Computing*, vol. 50, no. 3, Society for Industrial & Applied Mathematics, 2021, pp. STOC16-98-STOC16-137, doi:10.1137/16m1097808.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Link(s) to Main File(s)**

Access Level

Open Access

### Export

Marked PublicationsOpen Data ISTA Research Explorer

### Sources

arXiv 1504.07056