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

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 $\tilde{O}(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({\epsilon }^{-1}\log {\epsilon }^{-1})$-approximation factor of Lenzen and Patt-Shamir's $\tilde{O}(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}/\log n+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].

Accepted to SIAM Journal on Computing. A preliminary version of this paper was presented at the 48th ACM Symposium on Theory of Computing (STOC 2016). Abstract shortened to respect the arXiv limit of 1920 characters

References in corpus (5)

• Algebraic Methods in the Congested Clique
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Distributed Approximation Algorithms for Weighted Shortest Paths
• Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification
• Almost-Tight Distributed Minimum Cut Algorithms

Cited by in corpus (14)

• Distributed Edge Connectivity in Sublinear Time
• Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
• Estimation of Graphlet Statistics
• Near-Additive Spanners and Near-Exact Hopsets, A Unified View
• Minor Sparsifiers and the Distributed Laplacian Paradigm
• Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
• Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in $\tilde{O}(n^{3/2})$ Rounds
• Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work
• Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
• Two Player Hidden Pointer Chasing and Multi-Pass Lower Bounds in Turnstile Streams