2026-09-08T01:21:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26404 2026-09-05T19:42:21Z ddc:004 open_access

Parallel Reachability and Shortest Paths on Non-Sparse Digraphs: Near-Linear Work and Sub-Square-Root Depth Ashvinkumar, Vikrant Bernstein, Aaron Gutenberg, Maximilian Probst Saranurak, Thatchaphol shortcut set parallel reachability hopset parallel SSSP We present parallel algorithms for computing single-source reachability and shortest paths on directed n-vertex m-edge graphs using near-linear Õ(m) work and o(√n) depth whenever m ≥ n^{1+o(1)}. At the extreme of m = Ω(n²), our reachability and shortest path algorithms have depth only n^0.136 and n^{0.25+o(1)}, respectively. The state-of-the-art parallel algorithms with near-linear work for both problems [Jambulapati et al., 2019; Cao et al., 2020; Rozhoň et al., 2023; Cao and Fineman, 2023; Brand et al., 2025] require Ω(√n) depth in all density regimes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vikrant Ashvinkumar and Aaron Bernstein and Maximilian Probst Gutenberg and Thatchaphol Saranurak 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.15 urn:nbn:de:0030-drops-264045 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.15 eng https://creativecommons.org/licenses/by/4.0/legalcode