Multi-Source Reachability in Near-Optimal Time

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: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.