In graph theory, computing distances and reachabilities from a small set of vertices to the entire graph is a crucial primitive in both theory and practice. In undirected unweighted graphs, while computing single-source shortest path (SSSP) requires $O(n^2)$ time in dense graphs, all-pairs shortest paths (APSP) can be computed in $\tilde{O}(n^{\omega}) = O(n^{2.372})$ time, providing significant savings over running $n$ SSSP instances separately.
However, when one needs to compute multiple-source shortest paths (MSSP) from a set of $n^\sigma$ vertices, the previously best-known running time was $\tilde{O}(\min\{n^{\omega}, n^{2 + \sigma}\})$: either compute APSP or run SSSP from each source. On the other hand, MSSP is only as hard as computing Boolean matrix multiplication (BMM) between an $n^\sigma \times n$ matrix and an $n \times n$ matrix, leaving a significant gap.
Our first main result is an almost optimal algorithm for MSSP on undirected unweighted graphs running in $\tilde{O}(n^{\omega(\sigma, 1, 1)})$ time, which provides a smooth interpolation between SSSP and APSP algorithms. The main technical tool behind our result is a novel graph decomposition, which may be of independent interest.
Next, we study the multiple-source reachability problem, where we need to determine whether a given set of $n^\sigma$ vertices can reach each of the vertices in a given directed graph. Multiple-source reachability can also be solved in $\tilde{O}(\min\{n^{\omega}, n^{2 + \sigma}\})$ time, with the same lower bound from rectangular BMM. We provide an optimal algorithm that runs in $\tilde{O}(n^{\omega(\sigma, 1, 1)})$ time, again matching the running time for BMM.
Our algorithm for multiple-source reachability can be generalized to MSSP on DAGs. As an application, we present an $O(n^{2.084})$ time algorithm for computing a $\tilde{O}(n)$-size shortcut set that reduces diameter to $O(n^{1/3})$.
Blogger's Review: This research introduces an almost optimal algorithm for the multiple-source shortest paths and reachability problems, utilizing a novel graph decomposition technique, showcasing a close integration between theory and practical applications. Compared to traditional methods, the new algorithm offers significant advantages in handling large-scale data, paving the way for further research and exploration.