# Undirected $(1+\varepsilon)$-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms

Preprint · Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li

- Archive id: arxiv:2204.05874
- Published: 2022-04-12
- arXiv: https://arxiv.org/abs/2204.05874
- Source URL: https://arxiv.org/abs/2204.05874
- PDF: https://arxiv.org/pdf/2204.05874
- Provenance: arxiv

## Abstract

This paper presents near-optimal deterministic parallel and distributed algorithms for computing $(1+\\varepsilon)$-approximate single-source shortest paths in any undirected weighted graph. On a high level, we deterministically reduce this and other shortest-path problems to $\\tilde{O}(1)$ Minor-Aggregations. A Minor-Aggregation computes an aggregate (e.g., max or sum) of node-values for every connected component of some subgraph. Our reduction immediately implies: Optimal deterministic parallel (PRAM) algorithms with $\\tilde{O}(1)$ depth and near-linear work. Universally-optimal deterministic distributed (CONGEST) algorithms, whenever deterministic Minor-Aggregate algorithms exist. For example, an optimal $\\tilde{O}(HopDiameter(G))$-round deterministic CONGEST algorithm for excluded-minor networks. Several novel tools developed for the above results are interesting in their own right: A local iterative approach for reducing shortest path computations "up to distance $D$" to computing low-diameter decompositions "up to distance $\\frac{D}{2}$". Compared to the recursive vertex-reduction approach of \[Li20\], our approach is simpler, suitable for distributed algorithms, and eliminates many derandomization barriers. A simple graph-based $\\tilde{O}(1)$-competitive $\\ell\_1$-oblivious routing based on low-diameter decompositions that can be evaluated in near-linear work. The previous such routing \[ZGY+20\] was $n^{o(1)}$-competitive and required $n^{o(1)}$ more work. A deterministic algorithm to round any fractional single-source transshipment flow into an integral tree solution. The first distributed algorithms for computing Eulerian orientations.

_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.