Multi-Source Reachability in Near-Optimal Time
This work provides a faster deterministic solution for multi-source reachability, a fundamental problem in graph algorithms, benefiting applications in network analysis and database queries.
The paper presents a near-optimal deterministic algorithm for multi-source reachability in directed graphs, achieving $ ilde{O}(n^{ω(σ)})$ time for $n^σ$ sources, which for dense graphs allows reachability from up to $n^{0.32}$ sources in near-linear time, breaking the super-quadratic barrier and improving over the previous $n^{1+2/3ω(σ)}$-time randomized algorithm.
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].