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.

15 pages, 1 figure