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