pith. sign in

arxiv: 2507.13470 · v3 · submitted 2025-07-17 · 💻 cs.DS · cs.DC

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication

Michael Elkin , Chhaya Trehan This is my paper

Pith reviewed 2026-05-19 04:14 UTC · model grok-4.3

classification 💻 cs.DS cs.DC
keywords multi-source reachabilitydirected graphsrectangular matrix multiplicationshortcutshopsetsapproximate distancestreewidthgraph separators
0
0 comments X

The pith

New algorithm computes reachability from n^sigma sources in digraphs in time n to the 1 plus (2/3) times omega of sigma.

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

The paper presents a centralized algorithm for the S times V reachability problem on n-vertex digraphs with n^sigma sources. It achieves running time hat O of n to the 1 plus (2/3) omega(sigma) by combining existing shortcut constructions with rectangular matrix multiplication. This bound improves the prior min of 2 plus sigma and omega for sigma values from roughly 0.333 to 0.53. The work also improves parallel algorithms on graphs with small recursive separators, generalizes them to bounded-treewidth graphs, and extends the results to approximate distance computation.

Core claim

Leveraging shortcut constructions by Kogan and Parter, the authors develop a centralized algorithm with running time hat O of n to the 1 plus (2/3) omega of sigma, improving upon min of 2 plus sigma and omega for tilde sigma less than or equal to sigma less than or equal to 0.53. They improve Cohen's parallel algorithm for graphs admitting balanced recursive separators, generalize to graphs of treewidth at most n to the rho, and extend all results to (1 plus epsilon)-approximate distance computation.

What carries the argument

Shortcut constructions combined with rectangular matrix multiplication to compute reachability sets from a polynomial number of sources.

If this is right

  • Faster centralized computation of reachability when the source set size is between n to the 0.333 and n to the 0.53.
  • Lower parallel work for S times V reachability on graphs with balanced recursive separators.
  • New centralized and parallel algorithms for reachability on bounded-treewidth graphs.
  • Extension of the improvements to (1 plus epsilon)-approximate distances in the same graph families.

Where Pith is reading between the lines

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

  • The same shortcut-plus-matrix-multiplication template may yield speedups for other problems that reduce to multi-source reachability.
  • Further refinements to rectangular matrix multiplication exponents could widen the range of sigma where the new bound wins.
  • The parallel improvements suggest similar gains might be possible for dynamic or distributed versions of the problem.

Load-bearing premise

The shortcut constructions can be combined with rectangular matrix multiplication without incurring additional asymptotic overhead.

What would settle it

A calculation or graph family where the new exponent 1 plus (2/3) omega of sigma is not strictly smaller than min of 2 plus sigma and omega for some sigma between 0.333 and 0.53.

Figures

Figures reproduced from arXiv: 2507.13470 by Chhaya Trehan, Michael Elkin.

Figure 1
Figure 1. Figure 1: The segment connecting the points (0.321334, ω(0.321334)) and (1, ω(1)) lies above the plot of ω(σ). Its slope is however smaller than the slope of the segment connecting the points (σ, ω(σ)) and (1, ω(1)) for any ˜σ < σ < 1. The latter segment is illustrated by a red line. Hence, the assertion of the lemma holds for ˜σ < σ < 1. For σ = 1, we have 1 2 + ω(σ) − 3 2 σ = 3ω − 2ω(σ) − 1 = ω − 1. Hence equality… view at source ↗
Figure 2
Figure 2. Figure 2: Different sets and incidences between them in the proof of Lemma 9. [PITH_FULL_IMAGE:figures/full_fig_p061_2.png] view at source ↗
read the original abstract

Given an $n$-vertex $m$-edge digraph $G = (V,E)$ and a subset $S \subseteq V$ of $|S| = n^{\sigma}$ (for some $0 \le \sigma \le 1$) designated sources, the $S \times V$ reachability problem is to compute the sets $\mathcal V_s$ of vertices reachable from $s$, for every $s \in S$. Naive centralized algorithms run BFS/DFS from each source in $O(m \cdot n^{\sigma})$ time or compute $G$'s transitive closure in $\hat O(n^{\omega})$ time, where $\omega \le 2.371552\ldots$ is the matrix multiplication exponent. Thus, the best known bound is $\hat O(n^{\min \{ 2 + \sigma, \omega\}})$. Leveraging shortcut constructions by Kogan and Parter [SODA 2022, ICALP 2022], we develop a centralized algorithm with running time $\hat O(n^{1 + \frac{2}{3} \omega(\sigma)})$, where $\omega(\sigma)$ is the rectangular matrix multiplication exponent. Using current estimates on $\omega(\sigma)$, our exponent improves upon $\min \{2 + \sigma, \omega \}$ for $\tilde \sigma \leq \sigma \leq 0.53$, where $1/3 < \tilde \sigma < 0.3336$ is a universal constant. In a classical result, Cohen [Journal of Algorithms, 1996] devised parallel algorithms for $S \times V$ reachability on graphs admitting balanced recursive separators of size $n^{\rho}$ for $\rho < 1$, requiring polylogarithmic time and work $n^{\max \{\omega \rho, 2\rho + \sigma \} + o(1)}$. We significantly improve, extend, and generalize Cohen's result. First, our parallel algorithm for graphs with small recursive separators has lower work complexity than Cohen's in boraod paramater ranges. Second, we generalize our algorithm to graphs of treewidth at most $n^{\rho}$ ($\rho < 1$) and provide a centralized algorithm that outperforms existing bounds for $S \times V$ reachability on such graphs. We also do this for some other graph familes with small separators. Finally, we extend these results to $(1 + \epsilon)$-approximate distance computation.

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

2 major / 2 minor

Summary. The paper claims a centralized algorithm for S×V reachability in n-vertex digraphs with |S|=n^σ sources that runs in Õ(n^{1+(2/3)ω(σ)}) time by combining Kogan-Parter shortcut constructions (SODA/ICALP 2022) with rectangular matrix multiplication, improving on the prior min{2+σ,ω} bound for σ in [σ̃,0.53] where σ̃≈0.333. It also improves Cohen's 1996 parallel algorithm for graphs with balanced recursive separators, generalizes the approach to bounded-treewidth graphs and other separator families, supplies a centralized variant for those families, and extends all results to (1+ε)-approximate distances.

Significance. If the central combination holds without hidden asymptotic overhead, the result would tighten the best-known exponent for multi-source reachability in a non-trivial parameter range and would strengthen the parallel and approximate-distance literature by reducing work complexity relative to Cohen while broadening the graph families covered. The explicit reuse of existing shortcut constructions and the provision of both centralized and parallel bounds are concrete strengths.

major comments (2)
  1. [§3] §3 (main centralized algorithm): the reduction of S×V reachability to a collection of rectangular matrix multiplications must explicitly bound the total cost of all auxiliary graphs and source-set invocations produced by the Kogan-Parter shortcuts. If any auxiliary structure has size n^{f(σ)} with f(σ)>(2/3)ω(σ)−1, or if an extra matrix-multiplication call is incurred per shortcut layer whose exponent is not absorbed, the claimed 1+(2/3)ω(σ) bound would be violated. The current write-up does not contain this accounting.
  2. [§4] §4 (parallel algorithm for recursive separators): the claimed work improvement over Cohen's max{ωρ,2ρ+σ} must be derived from the same shortcut+rectangular-MM combination; the paper should state the precise new work exponent as a function of ρ and σ and verify it is strictly smaller than Cohen's in the stated broad parameter ranges.
minor comments (2)
  1. [Abstract] Abstract: 'boraod paramater ranges' is a typo for 'broad parameter ranges'.
  2. [Preliminaries] Notation: ω(σ) is introduced without an explicit reference to the rectangular matrix-multiplication literature; add a sentence or citation in the preliminaries.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The observations highlight opportunities to strengthen the presentation of cost analyses and explicit exponent derivations. We address each major comment below and will incorporate clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (main centralized algorithm): the reduction of S×V reachability to a collection of rectangular matrix multiplications must explicitly bound the total cost of all auxiliary graphs and source-set invocations produced by the Kogan-Parter shortcuts. If any auxiliary structure has size n^{f(σ)} with f(σ)>(2/3)ω(σ)−1, or if an extra matrix-multiplication call is incurred per shortcut layer whose exponent is not absorbed, the claimed 1+(2/3)ω(σ) bound would be violated. The current write-up does not contain this accounting.

    Authors: We appreciate the referee highlighting the need for explicit accounting. The Kogan-Parter construction produces O(log n) layers with auxiliary graphs whose aggregate size across all source-set invocations is bounded by n^{1+o(1)} per layer; when combined with the rectangular matrix multiplication cost for each invocation, the total is absorbed into the Õ(n^{1+(2/3)ω(σ)}) bound because the dominant term remains the rectangular multiplication exponent. No unabsorbed extra matrix-multiplication calls occur beyond those already accounted for in the recurrence. To address the concern directly, the revised manuscript will add a dedicated paragraph (or subsection) in §3 that sums the costs over all auxiliary structures and invocations, confirming that no auxiliary size exceeds the threshold that would violate the claimed exponent. revision: yes

  2. Referee: [§4] §4 (parallel algorithm for recursive separators): the claimed work improvement over Cohen's max{ωρ,2ρ+σ} must be derived from the same shortcut+rectangular-MM combination; the paper should state the precise new work exponent as a function of ρ and σ and verify it is strictly smaller than Cohen's in the stated broad parameter ranges.

    Authors: We agree that an explicit derivation strengthens the claim. The new parallel work bound is obtained by substituting the centralized shortcut+rectangular-MM procedure into the recursive separator framework, replacing Cohen's direct matrix-multiplication steps with the improved subproblem solver. In the revision we will state the precise work exponent as a function of ρ and σ (specifically, the maximum of the separator-induced term and the adapted 1+(2/3)ω(σ) term scaled by the recursion depth), and we will include a short case analysis verifying that this exponent is strictly smaller than max{ωρ, 2ρ+σ} throughout the broad parameter ranges ρ<1 and σ∈[σ̃,0.53] where the centralized improvement holds. This derivation follows directly from the same combination used in the centralized case. revision: yes

Circularity Check

0 steps flagged

No circularity detected; central bound derived from external citations and known matrix-multiplication exponents

full rationale

The paper derives its O(n^{1 + (2/3)ω(σ)}) bound by explicitly leveraging the shortcut constructions of Kogan and Parter (SODA 2022, ICALP 2022) together with rectangular matrix multiplication, without any self-referential equations, fitted parameters renamed as predictions, or load-bearing self-citations. The abstract and description present the improvement over min{2+σ, ω} as a direct consequence of combining these independent prior results with standard rectangular-MM techniques; no step reduces the claimed exponent to the paper's own inputs by construction. The generalization of Cohen's 1996 result is likewise an extension rather than a tautology. This is a standard non-circular algorithmic improvement.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard background results in matrix multiplication and prior algorithmic constructions without introducing new free parameters or invented entities.

axioms (1)
  • standard math Known upper bounds and properties of the rectangular matrix multiplication exponent omega(sigma)
    The improvement is stated in terms of current estimates on omega(sigma).

pith-pipeline@v0.9.0 · 6000 in / 1264 out tokens · 59206 ms · 2026-05-19T04:14:11.007429+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    doi:10.1145/3350755.3400222

    ACM, 2020. doi:10.1145/3350755.3400222. [CFR22] Nairen Cao, Jeremy T. Fineman, and Katina Russell. Parallel shortest paths with negative edge weights. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures , SPAA ’22, page 177–190, New York, NY, USA,

    work page doi:10.1145/3350755.3400222 2020

  2. [2]

    doi:10.1145/3490148.3538583

    Association for Computing Machinery. doi:10.1145/3490148.3538583. [Cha10] Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM Journal on Computing , 39(5):2075–2089, 2010. doi:10.1137/08071990X. [Coh96] Edith Cohen. Efficient parallel shortest-paths in digraphs with a separator decompo- sition. Journal of Algorithms, 21(...

    work page doi:10.1145/3490148.3538583 2075

  3. [3]

    [MTTV97] Gary L

    doi:10.1145/100216.100255. [MTTV97] Gary L. Miller, Shang-Hua Teng, William P. Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44(1):1–29,

    work page doi:10.1145/100216.100255

  4. [4]

    [MTV91] G.L

    doi:10.1145/256292.256294. [MTV91] G.L. Miller, S.-H. Teng, and S.A. Vavasis. A unified geometric approach to graph separators. In [1991] Proceedings 32nd Annual Symposium of Foundations of Com- puter Science, pages 538–547, 1991. doi:10.1109/SFCS.1991.185417. 55 [Mun71] J. Ian Munro. Efficient determination of the transitive closure of a directed graph. ...

    work page doi:10.1145/256292.256294 1991

  5. [5]

    doi:10.1145/3564246.3585235

    Association for Computing Machinery. doi:10.1145/3564246.3585235. [RS11] Liam Roditty and Asaf Shapira. All-pairs shortest paths with a sublinear additive error. ACM Trans. Algorithms , 7(4):45:1–45:12, 2011. doi:10.1145/2000807. 2000813. [RW09] Bruce A. Reed and David R. Wood. A linear-time algorithm to find a separator in a graph excluding a minor. ACM ...

    work page doi:10.1145/3564246.3585235 2011

  6. [6]

    [WN11] Christian Wulff-Nilsen

    doi:10.1016/0012-365X(82)90083-8. [WN11] Christian Wulff-Nilsen. Separator theorems for minor-free and shallow minor-free graphs with applications. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages 37–46, 2011. doi:10.1109/FOCS.2011.15. [WX20] Haitao Wang and Jie Xue. Near-optimal algorithms for shortest paths in weighted unit-...

    work page doi:10.1016/0012-365x(82)90083-8 2011

  7. [7]

    Suppose that a graph G = (V, E), |V | = n, admits a kρ-recursive separator with ratio α. (See Section 4.1 for relevant definitions.) Then G admits a separator C′ of size |C′| = Oρ,α(csep · nρ) with ratio 1/2, i.e., both parts A′ and B′ of V \ C′ satisfy |A′|, |B′| ≤ n/2

    work page

  8. [8]

    Then G admits a separator C′ of size |C′| = Oρ,λ(csep · log n · nρ), (68) with ratio 1/2

    Suppose that G = (V, E) admits a recursive separator with a flat bound of csep · nρ on its size. Then G admits a separator C′ of size |C′| = Oρ,λ(csep · log n · nρ), (68) with ratio 1/2. Proof. In case 1 we assume that for any subset U ⊂ V of vertices, there is a separator C∗ of size at most csep · |U |ρ such that U \ C decomposes into parts A∗ and B∗ of ...

    work page

  9. [9]

    For every i, Ai, Bi, Ci, Di is a partition of V

    work page

  10. [10]

    (In particular, if Di = ϕ, then Ci is a separator, and Ai, Bi are the two parts.)

    There are no edges between Ai and Bi, Ai and Di and Bi and Di. (In particular, if Di = ϕ, then Ci is a separator, and Ai, Bi are the two parts.)

    work page

  11. [11]

    |Ai| ≤ | Bi| ≤ | Ai| + |Ci| + |Di|

    work page

  12. [12]

    To define this sequence, we start with defining A0 = B0 = C0 = ϕ, D0 = V

    For every i such that both (Ai, Bi, Ci, Di) and (Ai+1, Bi+1, Ci+1, Di+1) are defined,we have |Di+1| ≤ λ · |Di|, i.e., eventually the sets Di vanish. To define this sequence, we start with defining A0 = B0 = C0 = ϕ, D0 = V . The proper- ties 1-4 hold (partly vacuously). Assume now that Ai, Bi, Ci, Di are defined for some i. Build 60 a balanced separator fo...

    work page