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

Preprint · Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

- Archive id: arxiv:1504.07056
- Published: 2015-04-27
- DOI: https://doi.org/10.1145/2897518.2897638
- arXiv: https://arxiv.org/abs/1504.07056
- Source URL: https://arxiv.org/abs/1504.07056
- PDF: https://arxiv.org/pdf/1504.07056
- Provenance: arxiv

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

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.