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

We present a deterministic (1+ o (1))-approximation O ( n 1/2+ o (1) + D 1+ o (1) )-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+ o (1))-approximation Õ( n 1/2 D 1/4 + D )-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n 1/8 , and (ii) the O (є −1 logє −1 )-approximation factor of Lenzen and Patt-Shamir’s Õ( n 1/2+є + D )-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω( n 1/2 /log n + D ) [Das Sarma et al. STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+ o (1))-approximation O ( 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 et al. [PODC 2012].

Authors

• Monika Henzinger
• Sebastian Forster
• Danupon Nanongkai

Keywords

• Distributed computing
• derandomization
• shortest paths