A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem
2026-08-17 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem where you want to find shortest routes in a graph even if one road (edge) is blocked, for many starting points at once. They present a new randomized algorithm for unweighted directed graphs that finds all these alternative distances faster than previous methods. Their algorithm is nearly the fastest possible for any combinatorial approach and outputs all replacement distances with high accuracy. They also emphasize that their method is simple compared to earlier ones.
replacement paths problemmultiple source replacement paths (MSRP)shortest pathunweighted directed graphsrandomized algorithmcombinatorial algorithmdistance sensitivity oracletime complexitygraph algorithms
Authors
Kaito Harada, Taisuke Izumi
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 $σ$ 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{σn} + σn^2)$ time, with all the output distances correct with high probability. This improves the best known bound $\tilde{O}(m\min\{σ\sqrt{n}, n\} + σ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{(σn)}^{1/2-o(1)}$ for such algorithms, which holds even on undirected graphs, and the additive term $σn^2$ is proportional to the time needed to write down the $Θ(σn^2)$ output distances. The algorithm is also remarkably simple.