{"id":"arxiv:2608.16615","kind":"preprint","title":"A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem","authors":["Kaito Harada","Taisuke Izumi"],"author_count":2,"year":2026,"published":"2026-08-17","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2608.16615","nct_id":null,"source_url":"https://arxiv.org/abs/2608.16615","archive_url":"https://space-kitty.com/papers/arxiv:2608.16615","updated":"2026-10-10","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2608.16615","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}