# Multi-Source Reachability in Near-Optimal Time

Preprint · Shimon Kogan, Merav Parter

- Archive id: arxiv:2606.25612
- Published: 2026-06-24
- arXiv: https://arxiv.org/abs/2606.25612
- Source URL: https://arxiv.org/abs/2606.25612
- PDF: https://arxiv.org/pdf/2606.25612
- Provenance: arxiv

## 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^σ$ for some $σ\\in \[0,1\]$, we present a near-optimal deterministic algorithm that solves this problem in $\\tilde{O}(n^{ω(σ)})$ time, where $ω(σ)$ is the rectangular matrix multiplication exponent for multiplying an $n^σ\\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ω(σ)}$-time randomized algorithm of Elkin and Trehan \[arXiv:2401.05628, 2024\].

_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.