# A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem

Preprint · Kaito Harada, Taisuke Izumi

- Archive id: arxiv:2608.16615
- Published: 2026-08-17
- arXiv: https://arxiv.org/abs/2608.16615
- Source URL: https://arxiv.org/abs/2608.16615
- PDF: https://arxiv.org/pdf/2608.16615
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.