Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication

Michael Elkin, Chhaya Trehan

Given an $n$-vertex $m$-edge digraph $G=(V,E)$ and a set $S\subseteq V$, $|S|=n^{\sigma }$ (for some $0<\sigma \le 1$) of designated sources, the $S\times V$-direachability problem is to…