pith. sign in

arxiv: 2606.25612 · v1 · pith:RIHUNSW2new · submitted 2026-06-24 · 💻 cs.DS

Multi-Source Reachability in Near-Optimal Time

Shimon Kogan , Merav Parter This is my paper

Pith reviewed 2026-06-25 20:10 UTC · model grok-4.3

classification 💻 cs.DS
keywords multi-source reachabilitydirected graphsrectangular matrix multiplicationdeterministic algorithmsgraph algorithmstransitive closure
0
0 comments X

The pith

A deterministic algorithm computes reachable sets from n^σ sources in Õ(n^{ω(σ)}) time.

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

The paper establishes a deterministic algorithm for the multi-source reachability problem on directed graphs. Given a graph with n vertices and a source set of size n^σ, the algorithm returns all vertices reachable from any source in the set. The running time matches the cost of rectangular matrix multiplication with the corresponding dimensions. A sympathetic reader would care because reachability is a core primitive in graph processing and this bound improves on the prior best randomized solution while removing randomness.

Core claim

The authors give a deterministic reduction from multi-source reachability to rectangular matrix multiplication. For a source set S of size n^σ the procedure runs in Õ(n^{ω(σ)}) time, where ω(σ) is the exponent for multiplying an n^σ-by-n matrix by an n-by-n matrix. When the graph is dense this yields near-linear time for every σ up to roughly 0.32, surpassing the previous n^{1+2/3ω(σ)}-time randomized bound.

What carries the argument

Reduction of multi-source reachability to one rectangular matrix multiplication whose exponent is ω(σ).

If this is right

  • Reachability from up to n^{0.32} sources becomes solvable in near-linear time on dense directed graphs.
  • The deterministic bound removes the need for randomization in the previous n^{1 + 2/3 ω(σ)} solution.
  • Any future improvement to rectangular matrix multiplication immediately improves the reachability time.

Where Pith is reading between the lines

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

  • The same reduction technique may apply to other problems whose current best algorithms rely on fast rectangular multiplication.
  • In practice the method could accelerate network reachability queries when the number of sources is a moderate power of n.
  • Extending the approach to dynamic or weighted graphs would be a natural next algorithmic target.

Load-bearing premise

The known upper bound on the rectangular matrix multiplication exponent ω(σ) is treated as given and the reduction is assumed to preserve that exact exponent.

What would settle it

An explicit dense graph family with |S| = n^{0.3} on which any correct algorithm requires Ω(n^{1.1}) time would falsify the near-optimality claim.

read the original abstract

The multi-source reachability problem asks to compute the reachable sets from a given subset of source vertices. For $n$-vertex digraphs $G=(V,E)$ and a subset of sources $S \subseteq V$ with $|S|=n^{\sigma}$ for some $\sigma \in [0,1]$, we present a near-optimal deterministic algorithm that solves this problem in $\tilde{O}(n^{\omega(\sigma)})$ time, where $\omega(\sigma)$ is the rectangular matrix multiplication exponent for multiplying an $n^{\sigma}\times n$ matrix by an $n \times n$ matrix. For dense graphs, this yields reachability from up to $n^{0.32}$ sources in near-linear time, breaking the super-quadratic time barrier and improving over the state-of-the-art $n^{1+2/3\omega(\sigma)}$-time randomized algorithm of Elkin and Trehan [arXiv:2401.05628, 2024].

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 / 1 minor

Summary. The manuscript claims a deterministic algorithm for multi-source reachability on n-vertex digraphs with |S|=n^σ sources that runs in ilde{O}(n^{\omega(\sigma)}) time, obtained by reducing the problem to a single rectangular matrix multiplication over the appropriate semiring and invoking the known rectangular matrix-multiplication exponent \omega(\sigma) from prior literature; this improves the prior randomized bound of n^{1 + 2/3 \omega(\sigma)}.

Significance. If the claimed reduction holds, the result is significant: it supplies a deterministic near-optimal solution that breaks the super-quadratic barrier for dense graphs when |S| ≤ n^{0.32} and yields near-linear time. The direct reduction to one rectangular matrix multiplication (rather than a sequence whose cost would exceed the single-multiplication bound) together with the parameter-free expression in terms of the externally defined \omega(\sigma) is a clear strength.

minor comments (1)
  1. [Abstract] Abstract: a single sentence sketching the reduction (e.g., “by a direct reduction to one rectangular matrix multiplication over the (min,+) semiring”) would make the high-level contribution clearer to readers who do not consult the full text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the accurate summary of our contribution, and the recommendation to accept. We are pleased that the significance of the deterministic near-optimal bound and the direct reduction to a single rectangular matrix multiplication are recognized.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's claimed running time is expressed directly as Õ(n^{ω(σ)}) by reducing multi-source reachability to a single rectangular matrix multiplication instance whose exponent ω(σ) is imported unchanged from prior external literature. No equations or steps in the provided abstract define ω(σ) internally, fit parameters to the target result, or rely on self-citations for the uniqueness or correctness of the reduction. The construction is therefore self-contained against external algebraic benchmarks and does not reduce to its own inputs by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the rectangular matrix multiplication exponent ω(σ) being available from prior literature; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)
  • standard math Rectangular matrix multiplication of an n^σ × n matrix by an n × n matrix can be performed in n^{ω(σ)} time
    The algorithm's running time is defined in terms of this exponent taken from prior work.

pith-pipeline@v0.9.1-grok · 5698 in / 1290 out tokens · 30705 ms · 2026-06-25T20:10:29.648616+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

259 extracted references · 85 canonical work pages

  1. [1]

    Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers , booktitle =

    Shimon Kogan and Merav Parter , editor =. Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.CH9 , timestamp =

    work page doi:10.1137/1.9781611977554.ch9 2023

  2. [2]

    Journal of Algorithms , volume =

    Edith Cohen , title =. Journal of Algorithms , volume =. 1996 , month = sep, doi =

    1996

  3. [3]

    Faster join-projects and sparse matrix multiplications , booktitle =

    Rasmus Resen Amossen and Rasmus Pagh , editor =. Faster join-projects and sparse matrix multiplications , booktitle =

  4. [4]

    Communications of the ACM , volume=

    Programming parallel algorithms , author=. Communications of the ACM , volume=. 1996 , publisher=

    1996

  5. [5]

    Fineman , editor =

    Nairen Cao and Jeremy T. Fineman , editor =. Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth , booktitle =

  6. [6]

    The Time Complexity of Fully Sparse Matrix Multiplication , booktitle =

    Amir Abboud and Karl Bringmann and Nick Fischer and Marvin K. The Time Complexity of Fully Sparse Matrix Multiplication , booktitle =

  7. [7]

    Woodruff and Qin Zhang , editor =

    Dirk Van Gucht and Ryan Williams and David P. Woodruff and Qin Zhang , editor =. The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication , booktitle =

  8. [8]

    Michele Borassi , title =. Inf. Process. Lett. , volume =. 2016 , url =. doi:10.1016/J.IPL.2016.05.002 , timestamp =

    work page doi:10.1016/j.ipl.2016.05.002 2016

  9. [9]

    Blelloch and Bruce M

    Guy E. Blelloch and Bruce M. Maggs , editor =. Parallel Algorithms , booktitle =. 1999 , url =. doi:10.1201/9781420049503-C48 , timestamp =

    work page doi:10.1201/9781420049503-c48 1999

  10. [10]

    Into the Square: On the Complexity of Some Quadratic-time Solvable Problems , booktitle =

    Michele Borassi and Pierluigi Crescenzi and Michel Habib , editor =. Into the Square: On the Complexity of Some Quadratic-time Solvable Problems , booktitle =

  11. [11]

    Edith Cohen , title =. J. Comput. Syst. Sci. , volume =. 1997 , url =. doi:10.1006/JCSS.1997.1534 , timestamp =

    work page doi:10.1006/jcss.1997.1534 1997

  12. [12]

    Proceedings of the 37th

    Adam Karczmarz and Bartlomiej Lewandowski , title =. Proceedings of the 37th

  13. [13]

    Journal of the ACM (JACM) , volume=

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

    1997

  14. [14]

    22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981 , pages =

    Don Coppersmith and Shmuel Winograd , title =. 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981 , pages =. 1981 , url =. doi:10.1109/SFCS.1981.27 , timestamp =

    work page doi:10.1109/sfcs.1981.27 1981

  15. [15]

    Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures , pages=

    Improved work span tradeoff for single source reachability and approximate shortest paths , author=. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures , pages=

  16. [16]

    Proceedings of the 37th

    Jan van den Brand and Hossein Gholizadeh and Yonggang Jiang and Tijn de Vos , title =. Proceedings of the 37th

  17. [17]

    Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth , booktitle =

    Arpit Agarwal and Sanjeev Khanna and Huan Li and Prathamesh Patil and Chen Wang and Nathan White and Peilin Zhong , editor =. Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth , booktitle =

  18. [18]

    Pan , title =

    Xiaohan Huang and Victor Y. Pan , title =. J. Complex. , volume =. 1998 , url =. doi:10.1006/JCOM.1998.0476 , timestamp =

    work page doi:10.1006/jcom.1998.0476 1998

  19. [19]

    Raimund Seidel , title =. J. Comput. Syst. Sci. , volume =. 1995 , url =. doi:10.1006/JCSS.1995.1078 , timestamp =

    work page doi:10.1006/jcss.1995.1078 1995

  20. [20]

    CoRR , volume =

    Michael Elkin and Chhaya Trehan , title =. CoRR , volume =. 2024 , url =. doi:10.48550/ARXIV.2401.05628 , eprinttype =. 2401.05628 , timestamp =

    work page doi:10.48550/arxiv.2401.05628 2024

  21. [21]

    Closing the Gap Between Directed Hopsets and Shortcut Sets , booktitle =

    Aaron Bernstein and Nicole Wein , editor =. Closing the Gap Between Directed Hopsets and Shortcut Sets , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.CH7 , timestamp =

    work page doi:10.1137/1.9781611977554.ch7 2023

  22. [22]

    Minimum Path Cover in Parameterized Linear Time , journal =

    Manuel C. Minimum Path Cover in Parameterized Linear Time , journal =. 2022 , url =. doi:10.48550/ARXIV.2211.09659 , eprinttype =. 2211.09659 , timestamp =

    work page doi:10.48550/arxiv.2211.09659 2022

  23. [23]

    2024 , url =

    Amir Abboud and Greg Bodwin , title =. 2024 , url =. doi:10.1137/21M1442176 , timestamp =

    work page doi:10.1137/21m1442176 2024

  24. [24]

    Uri Zwick , title =. J. 2002 , url =. doi:10.1145/567112.567114 , timestamp =

    work page doi:10.1145/567112.567114 2002

  25. [25]

    33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992 , pages =

    Noga Alon and Zvi Galil and Oded Margalit and Moni Naor , title =. 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992 , pages =. 1992 , url =. doi:10.1109/SFCS.1992.267748 , timestamp =

    work page doi:10.1109/sfcs.1992.267748 1992

  26. [26]

    Optimal Short Cycle Decomposition in Almost Linear Time , booktitle =

    Merav Parter and Eylon Yogev , editor =. Optimal Short Cycle Decomposition in Almost Linear Time , booktitle =. 2019 , url =. doi:10.4230/LIPICS.ICALP.2019.89 , timestamp =

    work page doi:10.4230/lipics.icalp.2019.89 2019

  27. [27]

    Liu and Richard Peng and Maximilian Probst Gutenberg and Sushant Sachdeva , title =

    Li Chen and Rasmus Kyng and Yang P. Liu and Richard Peng and Maximilian Probst Gutenberg and Sushant Sachdeva , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00064 , timestamp =

    work page doi:10.1109/focs54457.2022.00064 2022

  28. [28]

    Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time , booktitle =

    Manuel C. Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time , booktitle =. 2022 , url =. doi:10.1137/1.9781611977073.18 , timestamp =

    work page doi:10.1137/1.9781611977073.18 2022

  29. [29]

    Minimum Chain Cover in Almost Linear Time , booktitle =

    Manuel C. Minimum Chain Cover in Almost Linear Time , booktitle =. 2023 , url =. doi:10.4230/LIPICS.ICALP.2023.31 , timestamp =

    work page doi:10.4230/lipics.icalp.2023.31 2023

  30. [30]

    Decreasing the diameter of bounded degree graphs , journal =

    Noga Alon and Andr. Decreasing the diameter of bounded degree graphs , journal =. 2000 , url =. doi:10.1002/1097-0118(200011)35:3\<161::AID-JGT1\>3.0.CO;2-Y , timestamp =

    work page doi:10.1002/1097-0118(200011)35:3 2000

  31. [31]

    arXiv preprint arXiv:2211.06920 , year=

    Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets , author=. arXiv preprint arXiv:2211.06920 , year=

    arXiv

  32. [32]

    Greg Bodwin and Gary Hoppenworth , title =. 64th

  33. [33]

    Shimon Kogan and Merav Parter , title =. 63rd

  34. [34]

    CoRR , volume =

    Greg Bodwin , title =. CoRR , volume =. 2023 , url =. doi:10.48550/ARXIV.2305.18647 , eprinttype =

    work page doi:10.48550/arxiv.2305.18647 2023

  35. [35]

    Sparse Distance Preservers and Additive Spanners , journal =

    B. Sparse Distance Preservers and Additive Spanners , journal =. 2005 , url =. doi:10.1137/S0895480103431046 , timestamp =

    work page doi:10.1137/s0895480103431046 2005

  36. [36]

    A Unified Framework for Light Spanners , booktitle =

    Hung Le and Shay Solomon , editor =. A Unified Framework for Light Spanners , booktitle =

  37. [37]

    Don Coppersmith and Michael Elkin , title =

  38. [38]

    Michael Elkin and Ofer Neiman and Shay Solomon , title =

  39. [39]

    Beating Matrix Multiplication for n

    Shimon Kogan and Merav Parter , editor =. Beating Matrix Multiplication for n. 49th International Colloquium on Automata, Languages, and Programming,. 2022 , url =. doi:10.4230/LIPICS.ICALP.2022.82 , timestamp =

    work page doi:10.4230/lipics.icalp.2022.82 2022

  40. [40]

    Greg Bodwin , title =

  41. [41]

    Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths , booktitle =

    Michael Elkin and Ofer Neiman , editor =. Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths , booktitle =

  42. [42]

    Efficient Algorithms for Constructing Very Sparse Spanners and Emulators , booktitle =

    Michael Elkin and Ofer Neiman , editor =. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators , booktitle =

  43. [43]

    Uri Ben. New (. Proceedings of the 2020

    2020

  44. [44]

    A Unified Framework for Hopsets , booktitle =

    Ofer Neiman and Idan Shabat , editor =. A Unified Framework for Hopsets , booktitle =

  45. [45]

    Baratz and David Peleg , editor =

    Baruch Awerbuch and Alan E. Baratz and David Peleg , editor =. Cost-Sensitive Analysis of Communication Protocols , booktitle =. 1990 , url =. doi:10.1145/93385.93417 , timestamp =

    work page doi:10.1145/93385.93417 1990

  46. [46]

    Michael Elkin and Seth Pettie , title =

  47. [47]

    Michael Elkin and Idan Shabat , title =. 64th

  48. [48]

    Sparse distance preservers and additive spanners , booktitle =

    B. Sparse distance preservers and additive spanners , booktitle =

  49. [49]

    Michael Elkin and Arnold Filtser and Ofer Neiman , title =. Theor. Comput. Sci. , volume =

  50. [50]

    Seth Pettie , title =

  51. [51]

    On Sparse Spanners of Weighted Graphs , journal =

    Ingo Alth. On Sparse Spanners of Weighted Graphs , journal =

  52. [52]

    Near-Optimal Light Spanners , journal =

    Shiri Chechik and Christian Wulff. Near-Optimal Light Spanners , journal =. 2018 , url =. doi:10.1145/3199607 , timestamp =

    work page doi:10.1145/3199607 2018

  53. [53]

    Linear Size Distance Preservers , booktitle =

    Greg Bodwin , editor =. Linear Size Distance Preservers , booktitle =

  54. [54]

    Combinatorics (Keszthely, 1976), Coll

    Triple systems with no six points carrying three triangles , author=. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai , volume=

    1976

  55. [55]

    Proceedings of the National Academy of Sciences , volume=

    On sets of integers which contain no three terms in arithmetical progression , author=. Proceedings of the National Academy of Sciences , volume=. 1946 , publisher=

    1946

  56. [56]

    Annals of Mathematics , pages=

    A new proof of the graph removal lemma , author=. Annals of Mathematics , pages=. 2011 , publisher=

    2011

  57. [57]

    Aho and M

    Alfred V. Aho and M. R. Garey and Jeffrey D. Ullman , title =. 1972 , url =. doi:10.1137/0201008 , timestamp =

    work page doi:10.1137/0201008 1972

  58. [58]

    Spencer , title =

    Hanmao Shi and Thomas H. Spencer , title =. J. Algorithms , volume =

  59. [59]

    Klein and Sairam Subramanian , title =

    Philip N. Klein and Sairam Subramanian , title =. J. Algorithms , volume =

  60. [60]

    A Faster Distributed Single-Source Shortest Paths Algorithm , booktitle =

    Sebastian Forster and Danupon Nanongkai , editor =. A Faster Distributed Single-Source Shortest Paths Algorithm , booktitle =

  61. [61]

    Amir Abboud and Greg Bodwin and Seth Pettie , title =

  62. [62]

    Annals of Mathematics , pages =

    Jacob Fox , title =. Annals of Mathematics , pages =

  63. [63]

    An Improved Construction of Progression-Free Sets , booktitle =

    Michael Elkin , editor =. An Improved Construction of Progression-Free Sets , booktitle =

  64. [64]

    Better Distance Preservers and Additive Spanners , booktitle =

    Greg Bodwin and Virginia Vassilevska Williams , editor =. Better Distance Preservers and Additive Spanners , booktitle =

  65. [65]

    New Additive Emulators , booktitle =

    Shimon Kogan and Merav Parter , editor =. New Additive Emulators , booktitle =

  66. [66]

    CoRR , volume =

    Michael Elkin and Ofer Neiman , title =. CoRR , volume =. 2020 , url =

    2020

  67. [67]

    Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in

    Michael Elkin and Ofer Neiman , editor =. Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in. The 31st

  68. [68]

    Thorup-Zwick emulators are universally optimal hopsets , journal =

    Shang. Thorup-Zwick emulators are universally optimal hopsets , journal =

  69. [69]

    Proceedings of the Seventeenth Annual

    Mikkel Thorup and Uri Zwick , title =. Proceedings of the Seventeenth Annual

  70. [70]

    Edith Cohen , title =. J

  71. [71]

    Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles , booktitle =

    Mikkel Thorup , editor =. Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles , booktitle =. 2004 , url =. doi:10.1007/978-3-540-27810-8\_33 , timestamp =

    work page doi:10.1007/978-3-540-27810-8 2004

  72. [72]

    Floyd , title =

    Robert W. Floyd , title =. Commun. 1962 , url =. doi:10.1145/367766.368168 , timestamp =

    work page doi:10.1145/367766.368168 1962

  73. [73]

    Johnson , title =

    Donald B. Johnson , title =. J. 1977 , url =. doi:10.1145/321992.321993 , timestamp =

    work page doi:10.1145/321992.321993 1977

  74. [74]

    Italiano and Aleksander Lukasiewicz and Nikos Parotsidis and Przemyslaw Uznanski , editor =

    Fabrizio Grandoni and Giuseppe F. Italiano and Aleksander Lukasiewicz and Nikos Parotsidis and Przemyslaw Uznanski , editor =. All-Pairs. Proceedings of the 2021. 2021 , url =. doi:10.1137/1.9781611976465.18 , timestamp =

    work page doi:10.1137/1.9781611976465.18 2021

  75. [75]

    Graphs Comb

    Noga Alon , title =. Graphs Comb. , volume =. 1990 , url =. doi:10.1007/BF01787474 , timestamp =

    work page doi:10.1007/bf01787474 1990

  76. [76]

    Finding Sparser Directed Spanners , booktitle =

    Piotr Berman and Sofya Raskhodnikova and Ge Ruan , editor =. Finding Sparser Directed Spanners , booktitle =

  77. [77]

    Woodruff , title =

    Arnab Bhattacharyya and Elena Grigorescu and Kyomin Jung and Sofya Raskhodnikova and David P. Woodruff , title =. 2012 , url =. doi:10.1137/110826655 , timestamp =

    work page doi:10.1137/110826655 2012

  78. [78]

    Woodruff , editor =

    Arnab Bhattacharyya and Elena Grigorescu and Kyomin Jung and Sofya Raskhodnikova and David P. Woodruff , editor =. Transitive-closure spanners , booktitle =

  79. [79]

    Transitive-Closure Spanners:

    Sofya Raskhodnikova , editor =. Transitive-Closure Spanners:. Property Testing - Current Research and Surveys , series =. 2010 , url =. doi:10.1007/978-3-642-16367-8\_10 , timestamp =

    work page doi:10.1007/978-3-642-16367-8 2010

  80. [80]

    Fineman , title =

    Jeremy T. Fineman , title =

Showing first 80 references.