Optimal Distributed Replacement Paths
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909754137247744 |
|---|---|
| author | Chang, Yi-Jun Chen, Yanyu Dey, Dipan Mishra, Gopinath Nguyen, Hung Thuan Sanchez, Bryce |
| author_facet | Chang, Yi-Jun Chen, Yanyu Dey, Dipan Mishra, Gopinath Nguyen, Hung Thuan Sanchez, Bryce |
| contents | We study the replacement paths problem in the $\mathsf{CONGEST}$ model of distributed computing. Given an $s$-$t$ shortest path $P$, the goal is to compute, for every edge $e$ in $P$, the shortest-path distance from $s$ to $t$ avoiding $e$. For unweighted directed graphs, we establish the tight randomized round complexity bound for this problem as $\widetildeΘ(n^{2/3} + D)$ by showing matching upper and lower bounds. Our upper bound extends to $(1+ε)$-approximation for weighted directed graphs. Our lower bound applies even to the second simple shortest path problem, which asks only for the smallest replacement path length. These results improve upon the very recent work of Manoharan and Ramachandran (SIROCCO 2024), who showed a lower bound of $\widetildeΩ(n^{1/2} + D)$ and an upper bound of $\widetilde{O}(n^{2/3} + \sqrt{n h_{st}} + D)$, where $h_{st}$ is the number of hops in the given $s$-$t$ shortest path $P$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15378 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Distributed Replacement Paths Chang, Yi-Jun Chen, Yanyu Dey, Dipan Mishra, Gopinath Nguyen, Hung Thuan Sanchez, Bryce Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We study the replacement paths problem in the $\mathsf{CONGEST}$ model of distributed computing. Given an $s$-$t$ shortest path $P$, the goal is to compute, for every edge $e$ in $P$, the shortest-path distance from $s$ to $t$ avoiding $e$. For unweighted directed graphs, we establish the tight randomized round complexity bound for this problem as $\widetildeΘ(n^{2/3} + D)$ by showing matching upper and lower bounds. Our upper bound extends to $(1+ε)$-approximation for weighted directed graphs. Our lower bound applies even to the second simple shortest path problem, which asks only for the smallest replacement path length. These results improve upon the very recent work of Manoharan and Ramachandran (SIROCCO 2024), who showed a lower bound of $\widetildeΩ(n^{1/2} + D)$ and an upper bound of $\widetilde{O}(n^{2/3} + \sqrt{n h_{st}} + D)$, where $h_{st}$ is the number of hops in the given $s$-$t$ shortest path $P$. |
| title | Optimal Distributed Replacement Paths |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2502.15378 |