Undirected (1+ 𝜀 )-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms

DOI10.1145/3519935.3520074MaRDI QIDQ6083499zbMATH OpenWikidataFDO

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

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmsparallel algorithmsshortest path

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 $ildeO(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 $ildeO(1)$ depth and near-linear work. Universally-optimal deterministic distributed (CONGEST) algorithms, whenever deterministic Minor-Aggregate algorithms exist. For example, an optimal $ildeO(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 $fracD2$". 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 $ildeO(1)$-competitive $el{l}_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.

Cited in

(6)

• Optimal electrical oblivious routing on expanders
• Hardness and algorithms for several new optimization problems on the weighted massively parallel computation model
• A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP
• Universally optimal information dissemination and shortest paths in the HYBRID distributed model
• Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights
• A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs

This page was built for publication: Undirected (1+ 𝜀 )-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms

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