Metraipolis › archive › dc_89faf024d5c1
A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem — arXiv:2608.16615
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.16615
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T00:13:31.872Z
- SHA-256 of the archived text
e61aa118e570ae26807ee1801e26c24e4aba096937e73cd816051eb81653607b- Stable URL of this page
https://metraipolis.com/documento/dc_89faf024d5c1
How to cite
A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem — arXiv:2608.16615 — arXiv (en), https://arxiv.org/abs/2608.16615 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_89faf024d5c1 (Metraipolis archive dc_89faf024d5c1, sha256 e61aa118e570ae26807ee1801e26c24e4aba096937e73cd816051eb81653607b)
BibTeX
@misc{dc89faf024d5c1,
title = {A Simple Algorithm for the Directed Multiple Source Replacement Paths Problem — arXiv:2608.16615},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.16615},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_89faf024d5c1; sha256 e61aa118e570ae26807ee1801e26c24e4aba096937e73cd816051eb81653607b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.16615. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-18 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.16615 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T23:35:27.645Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).