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