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

Preprint · Michael Elkin, Chhaya Trehan

- Archive id: arxiv:2507.13470
- Published: 2025-07-17
- arXiv: https://arxiv.org/abs/2507.13470
- Source URL: https://arxiv.org/abs/2507.13470
- PDF: https://arxiv.org/pdf/2507.13470
- Provenance: arxiv

## Abstract

Given an $n$-vertex $m$-edge digraph $G = (V,E)$ and a subset $S \\subseteq V$ of $\|S\| = n^σ$ (for some $0 \\le σ\\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^σ)$ time or compute $G$'s transitive closure in $\\hat O(n^ω)$ time, where $ω\\le 2.371552\\ldots$ is the matrix multiplication exponent. Thus, the best known bound is $\\hat O(n^{\\min \\{ 2 + σ, ω\\}})$. 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} ω(σ)})$, where $ω(σ)$ is the rectangular matrix multiplication exponent. Using current estimates on $ω(σ)$, our exponent improves upon $\\min \\{2 + σ, ω\\}$ for $\\tilde σ\\leq σ\\leq 0.53$, where $1/3 \< \\tilde σ\< 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^ρ$ for $ρ\< 1$, requiring polylogarithmic time and work $n^{\\max \\{ωρ, 2ρ+ σ\\} + 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^ρ$ ($ρ\< 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 + ε)$-approximate distance computation.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.