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.
Blogger's Review: This paper presents a significant improvement in the time complexity of the multi-source reachability problem, especially in dense graphs, showcasing the powerful application of matrix multiplication in graph theory. This research provides new insights worth further exploration.