pith. machine review for the scientific record. sign in

arxiv: 2605.03892 · v1 · submitted 2026-05-05 · 💻 cs.DS

Recognition: unknown

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth

Vikrant Ashvinkumar , Aaron Bernstein , Maximilian Probst Gutenberg , Thatchaphol Saranurak
Authors on Pith no claims yet

Pith reviewed 2026-05-07 13:48 UTC · model grok-4.3

classification 💻 cs.DS
keywords parallel algorithmsreachabilityshortest pathsdirected graphswork-depth tradeoffdense graphsgraph algorithms
0
0 comments X

The pith

Parallel algorithms compute single-source reachability and shortest paths in directed graphs with near-linear work and depth below the square root of the number of vertices whenever the graph is sufficiently dense.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes parallel algorithms for single-source reachability and shortest paths on directed graphs that use near-linear work in the number of edges while achieving depth strictly less than the square root of the number of vertices. This improvement holds as soon as the number of edges meets or exceeds n raised to the power of 1 plus a vanishing fraction. A reader would care because prior near-linear-work methods were stuck at square-root depth in every density regime, limiting how well many processors could be used on dense networks such as social graphs or citation networks. For the densest case of roughly quadratic edges, the new reachability depth drops to roughly n to the 0.136 and shortest-path depth to n to the 0.25 plus lower-order terms.

Core claim

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 require Ω(√n) depth in all density regimes.

What carries the argument

The new parallel algorithms that combine existing techniques to exploit graph density and thereby reduce depth below the square-root barrier while keeping total work near-linear.

If this is right

  • Reachability on dense digraphs can be solved in depth n^{0.136} using near-linear work.
  • Shortest paths on dense digraphs can be solved in depth n^{0.25+o(1)} using near-linear work.
  • The algorithms apply to any directed graph meeting the density threshold m ≥ n^{1+o(1)}, not only the quadratic case.
  • These bounds improve on all prior near-linear-work parallel methods, which required at least square-root depth regardless of density.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the techniques extend to other problems such as all-pairs shortest paths or transitive closure, they could reduce parallel depth for additional graph queries on dense inputs.
  • The density threshold suggests that new ideas are still needed to break the square-root barrier on truly sparse graphs.
  • Practical implementations on shared-memory machines could be tested by measuring wall-clock time on dense real-world digraphs with millions of edges.
  • The work-depth tradeoff shown here may guide future algorithm design for other parallel models beyond the one implicitly used.

Load-bearing premise

The graph must contain at least n to a power slightly larger than 1 edges, and the underlying parallel computation model must support the auxiliary subroutines used in the construction.

What would settle it

A lower-bound proof establishing that every near-linear-work parallel algorithm for reachability on directed graphs with m = n^{1.1} edges requires depth at least c √n for some constant c would falsify the central claim.

Figures

Figures reproduced from arXiv: 2605.03892 by Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Vikrant Ashvinkumar.

Figure 1
Figure 1. Figure 1: Comparison of spans of Oe(m) work parallel algorithms for reachability and SSSP on digraphs. Each plotted curve corresponds to such a parallel algorithm. The x-axis is the density of the input digraph, and the y-axis is the span of the algorithm. †: The bound for parallel SSSP also holds for combinatorial parallel reachability (i.e. ω = 3). Parallel Reachability and Shortcut Sets. Our main result is on par… view at source ↗
Figure 2
Figure 2. Figure 2: An example where a single (ancestor) pivot chosen. view at source ↗
read the original abstract

We present parallel algorithms for computing single-source reachability and shortest paths on directed $n$-vertex $m$-edge graphs using near-linear $\tilde{O}(m)$ work and $o(\sqrt{n})$ depth whenever $m\ge n^{1+o(1)}$. At the extreme of $m=\Omega(n^{2})$, 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 require $\Omega(\sqrt{n})$ depth in all density regimes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript presents parallel algorithms for single-source reachability and shortest paths on directed n-vertex m-edge graphs. These achieve near-linear Õ(m) work and o(√n) depth whenever m ≥ n^{1+o(1)}. At the extreme of m = Ω(n²), the reachability algorithm has depth n^{0.136} and the shortest-path algorithm has depth n^{0.25+o(1)}. The algorithms operate in the standard CRCW PRAM model and combine a low-depth sampling-based decomposition (for the sparse regime) with a sparsified dense-matrix subroutine adapted from fast matrix multiplication (invoked only when m ≥ n^{1+ε}). All auxiliary lemmas are proved in the paper, and the depth recurrences are solved to obtain the stated bounds while preserving Õ(m) work. This improves on prior near-linear-work algorithms that require Ω(√n) depth in all density regimes.

Significance. If the central claims hold, the result is significant: it breaks the √n depth barrier for dense digraphs while retaining near-linear work, a long-standing open question in parallel graph algorithms. The manuscript supplies complete proofs of all auxiliary lemmas without external unverified oracles, uses a standard CRCW PRAM model with O(1)-time word operations, and derives the concrete exponents via explicit recurrences. These strengths make the contribution technically solid and potentially impactful for high-performance parallel implementations.

minor comments (3)
  1. [Abstract and §1] The abstract and introduction could explicitly state the parallel model (CRCW PRAM) and the density threshold m ≥ n^{1+ε} at which the dense subroutine is invoked, to make the regime separation immediately clear to readers.
  2. [§4 (dense subroutine)] In the derivation of the dense-case depth bounds, add a short paragraph or table summarizing the recurrence solution steps that produce the specific exponents 0.136 and 0.25+o(1); this would improve readability without altering the technical content.
  3. [§3.2] Ensure that all references to prior matrix-multiplication exponents (e.g., the O(n^{2.37}) base) are accompanied by the precise citation and the exact sparsification factor used to keep total work Õ(m).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and detailed summary of our work, the assessment of its significance in breaking the long-standing √n depth barrier for near-linear-work parallel reachability and shortest paths on directed graphs, and the recommendation for minor revision. The report correctly captures the key technical contributions, including the combination of sampling-based decomposition and sparsified dense-matrix methods, the CRCW PRAM model, and the explicit depth exponents derived from the recurrences.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper constructs parallel algorithms for single-source reachability and shortest paths via a combination of sampling-based decomposition in the sparse regime and a sparsified dense-matrix subroutine (adapted from matrix multiplication) invoked only for m ≥ n^{1+ε}. Depth recurrences are solved explicitly to obtain the stated n^{0.136} and n^{0.25+o(1)} bounds while preserving Õ(m) work. All lemmas, primitives, and the CRCW PRAM model assumptions are proved or stated within the manuscript itself; no load-bearing step reduces by definition, fitted parameter, or unverified self-citation chain to the target result. The result is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard assumptions of parallel computation models and graph theory; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (1)
  • domain assumption Standard parallel computation model (likely CRCW PRAM or similar) in which the stated work and depth are measured.
    All parallel algorithm papers implicitly rely on a model of computation; the abstract does not name it but the depth and work bounds presuppose one.

pith-pipeline@v0.9.0 · 5418 in / 1419 out tokens · 58803 ms · 2026-05-07T13:48:35.836128+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Nearly work-efficient parallel algorithm for digraph reachability , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  2. [2]

    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Parallel reachability in almost linear work and square root depth , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

    2019

  3. [3]

    Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Efficient construction of directed hopsets and parallel approximate shortest paths , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  4. [4]

    Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , pages=

    Brief announcement: An improved distributed approximate single source shortest paths algorithm , author=. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , pages=

    2021

  5. [5]

    Journal of Algorithms , volume=

    A randomized parallel algorithm for single-source shortest paths , author=. Journal of Algorithms , volume=. 1997 , publisher=

    1997

  6. [6]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  7. [7]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Parallel exact shortest paths in almost linear work and square root depth , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  8. [8]

    SIAM Journal on Computing (Society for Industrial and Applied Mathematics);(United States) , volume=

    High-probability parallel transitive-closure algorithms , author=. SIAM Journal on Computing (Society for Industrial and Applied Mathematics);(United States) , volume=

  9. [9]

    Journal of the ACM (JACM) , volume=

    Time-work tradeoffs for parallel algorithms , author=. Journal of the ACM (JACM) , volume=. 1997 , publisher=

    1997

  10. [10]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    More asymmetry yields faster matrix multiplication , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

  11. [11]

    Folklore sampling is optimal for exact hopsets: Confirming the

    Bodwin, Greg and Hoppenworth, Gary , booktitle=. Folklore sampling is optimal for exact hopsets: Confirming the. 2023 , organization=

    2023

  12. [12]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    New diameter-reducing shortcuts and directed hopsets: Breaking the barrier , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  13. [13]

    Beating Matrix Multiplication for n^

    Kogan, Shimon and Parter, Merav , booktitle=. Beating Matrix Multiplication for n^. 2022 , organization=

    2022

  14. [14]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Faster and unified algorithms for diameter reducing shortcuts and minimum chain covers , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  15. [15]

    31st Annual European Symposium on Algorithms (ESA 2023) , pages=

    Towards bypassing lower bounds for graph shortcuts , author=. 31st Annual European Symposium on Algorithms (ESA 2023) , pages=. 2023 , organization=

    2023

  16. [16]

    arXiv preprint arXiv:2503.13274 , year=

    Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances , author=. arXiv preprint arXiv:2503.13274 , year=

    work page arXiv

  17. [17]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Closing the gap between directed hopsets and shortcut sets , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  18. [18]

    Parallel algorithms , author=

  19. [19]

    Greedy Algorithms for Shortcut Sets and Hopsets

    Greedy Algorithms for Shortcut Sets and Hopsets , author=. arXiv preprint arXiv:2511.20111 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  20. [20]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year=

    New Separations and Reductions for Directed Preservers and Hopsets , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year=

    2025

  21. [21]

    2026 SIAM Symposium on Simplicity in Algorithms (SOSA) , pages=

    Reducing Shortcut and Hopset Constructions to Shallow Graphs , author=. 2026 SIAM Symposium on Simplicity in Algorithms (SOSA) , pages=. 2026 , organization=

    2026

  22. [22]

    Finding strongly connected components in parallel using

    Schudy, Warren , booktitle=. Finding strongly connected components in parallel using