A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem

Abstract

In the replacement paths (RP) problem, we are given a graph $G = (V, E)$ with $n = |V|$ and $m = |E|$, together with two vertices $s, t \in V$, and are asked to compute the shortest-path distance from $s$ to $t$ in $G \setminus e$ for every failed edge $e \in E$. The multiple source replacement paths (MSRP) problem is its natural generalization: given a set $S \subseteq V$ of $\sigma$ sources, compute the replacement path distances for all pairs in $S \times V$. In this paper, we present a randomized combinatorial algorithm that solves MSRP on unweighted directed graphs in $\tilde{O}(m\sqrt{\sigma n} + \sigma n^2)$ time, with all the output distances correct with high probability. This improves the best known bound $\tilde{O}(m\min\{\sigma\sqrt{n}, n\} + \sigma n^2)$ for directed graphs, which is obtained either by running the single source RP algorithm of Chechik and Magen [ICALP'20] from each source separately or by constructing and querying the all-pairs distance sensitivity oracle of Bernstein and Karger [STOC'09]. Our running time is essentially tight among combinatorial algorithms because Gupta, Jain, and Modi [PODC'20] proved a lower bound of $m{(\sigma n)}^{1/2-o(1)}$ for such algorithms, which holds even on undirected graphs, and the additive term $\sigma n^2$ is proportional to the time needed to write down the $\Theta(\sigma n^2)$ output distances. The algorithm is also remarkably simple.