Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.18312 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912134836781056 |
|---|---|
| author | Chi, Shucheng Duan, Ran Wang, Benyu Xie, Tianle |
| author_facet | Chi, Shucheng Duan, Ran Wang, Benyu Xie, Tianle |
| contents | Given a graph $G=(V,E)$ and two vertices $s,t\in V$, the $f$-fault replacement path ($f$FRP) problem computes for every set of edges $F$ where $|F|\leq f$, the distance from $s$ to $t$ when edges in $F$ fail. A recent result shows that 2FRP in directed graphs can be solved in $\tilde{O}(n^3)$ time [arXiv:2209.07016]. In this paper, we show a 3FRP algorithm in deterministic $\tilde{O}(n^3)$ time for undirected weighted graphs, which almost matches the size of the output. This implies that $f$FRP in undirected graphs can be solved in almost optimal $\tilde{O}(n^f)$ time for all $f\geq 3$. To construct our 3FRP algorithm, we introduce an incremental distance sensitivity oracle (DSO) with $\tilde{O}(n^2)$ worst-case update time, while preprocessing time, space, and query time are still $\tilde{O}(n^3)$, $\tilde{O}(n^2)$ and $\tilde{O}(1)$, respectively, which match the static DSO [Bernstein and Karger 2009]. Here in a DSO, we can preprocess a graph so that the distance between any pair of vertices given any failed edge can be answered efficiently. From the recent result in [arXiv:2211.05178], we can obtain an offline dynamic DSO from the incremental worst-case DSO, which makes the construction of our 3FRP algorithm more convenient. By the offline dynamic DSO, we can also construct a 2-fault single-source replacement path (2-fault SSRP) algorithm in $\tilde{O}(n^3)$ time, that is, from a given vertex $s$, we want to find the distance to any vertex $t$ when any pair of edges fail. Thus the $\tilde{O}(n^3)$ time complexity for 2-fault SSRP is also almost optimal. Now we know that in undirected graphs 1FRP can be solved in $\tilde{O}(m)$ time [Nardelli, Proietti, Widmayer 2001], and 2FRP and 3FRP in undirected graphs can be solved in $\tilde{O}(n^3)$ time. In this paper, we also show that a truly subcubic algorithm for 2FRP in undirected graphs does not exist under APSP-hardness conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18312 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Undirected 3-Fault Replacement Path in Nearly Cubic Time Chi, Shucheng Duan, Ran Wang, Benyu Xie, Tianle Data Structures and Algorithms Given a graph $G=(V,E)$ and two vertices $s,t\in V$, the $f$-fault replacement path ($f$FRP) problem computes for every set of edges $F$ where $|F|\leq f$, the distance from $s$ to $t$ when edges in $F$ fail. A recent result shows that 2FRP in directed graphs can be solved in $\tilde{O}(n^3)$ time [arXiv:2209.07016]. In this paper, we show a 3FRP algorithm in deterministic $\tilde{O}(n^3)$ time for undirected weighted graphs, which almost matches the size of the output. This implies that $f$FRP in undirected graphs can be solved in almost optimal $\tilde{O}(n^f)$ time for all $f\geq 3$. To construct our 3FRP algorithm, we introduce an incremental distance sensitivity oracle (DSO) with $\tilde{O}(n^2)$ worst-case update time, while preprocessing time, space, and query time are still $\tilde{O}(n^3)$, $\tilde{O}(n^2)$ and $\tilde{O}(1)$, respectively, which match the static DSO [Bernstein and Karger 2009]. Here in a DSO, we can preprocess a graph so that the distance between any pair of vertices given any failed edge can be answered efficiently. From the recent result in [arXiv:2211.05178], we can obtain an offline dynamic DSO from the incremental worst-case DSO, which makes the construction of our 3FRP algorithm more convenient. By the offline dynamic DSO, we can also construct a 2-fault single-source replacement path (2-fault SSRP) algorithm in $\tilde{O}(n^3)$ time, that is, from a given vertex $s$, we want to find the distance to any vertex $t$ when any pair of edges fail. Thus the $\tilde{O}(n^3)$ time complexity for 2-fault SSRP is also almost optimal. Now we know that in undirected graphs 1FRP can be solved in $\tilde{O}(m)$ time [Nardelli, Proietti, Widmayer 2001], and 2FRP and 3FRP in undirected graphs can be solved in $\tilde{O}(n^3)$ time. In this paper, we also show that a truly subcubic algorithm for 2FRP in undirected graphs does not exist under APSP-hardness conjecture. |
| title | Undirected 3-Fault Replacement Path in Nearly Cubic Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.18312 |