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

DOI10.1145/2897518.2897638MaRDI QIDQ5361854zbMATH OpenOpenAlexFDO

Authors Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.07056

zbMATH Keywords

distributed computingshortest pathsderandomization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Distributed algorithms (68W15)

Abstract: 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 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 $ildeO(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(epsilo{n}^{-1}logepsilo{n}^{-1})$-approximation factor of Lenzen and Patt-Shamir's $ildeO(n^{1/2+epsilon}+D)$-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of $Omega(n^{1/2}/logn+D)$ [Elkin STOC 2004] up to subpolynomial factors, 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 $(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 [OPODIS 2015]. 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 from problems that are not directly related to shortest paths, e.g., ruling sets [Goldberg et al. STOC 1987], source detection [Lenzen and Peleg PODC 2013], and partial distance estimation [Lenzen and Patt-Shamir PODC 2015].

Recommendations

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Distributed approximation algorithms for weighted shortest paths
• Improved distributed algorithms for exact shortest paths

Cited in

(28)

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A \(2\cdot | E |\)-bit distributed algorithm for the directed Euler trail problem
• Fast Distributed Approximation for Max-Cut
• Distributed approximation algorithms for weighted shortest paths
• A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
• Derandomizing local distributed algorithms under bandwidth restrictions
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Hopsets with constant hopbound, and applications to approximate shortest paths
• Faster distributed shortest path approximations via shortcuts
• Thorup-Zwick emulators are universally optimal hopsets
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Distributed distance computation and routing with small messages
• The sparsest additive spanner via multiple weighted BFS trees
• Distance computations in the hybrid network model via oracle simulations
• Distributed distance approximation
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Single-source shortest paths in the CONGEST model with improved bounds
• On efficient distributed construction of near optimal routing schemes
• Reachability and shortest paths in the broadcast CONGEST model
• A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
• Distributed model checking on graphs of bounded treedepth
• Distributed planar reachability in nearly optimal time
• Fast approximate shortest paths in the congested clique
• Distributed Lower Bounds for Ruling Sets
• Approximation of distances and shortest paths in the broadcast congest clique
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Distributed MST and broadcast with fewer messages, and faster gossiping

This page was built for publication: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361854)