Search Results

Given a graph G = (V,E) (n = |V|, m = |E|) and two vertices s,t ∈ V, the f-fault replacement path (fFRP) problem computes for every set F of at most f edges, the distance from s to t when edges in F fail. A recent result shows that 2FRP in directed graphs can be solved in Õ(n³) time [Vassilevska Williams, Woldeghebriel, Xu 2022]. In this paper, we show a 3FRP algorithm in deterministic Õ(n³) time for undirected weighted graphs, which almost matches the size of the output. This implies that fFRP in undirected graphs can be solved in nearly optimal Õ(n^f) time for all f ≥ 3. To construct our 3FRP algorithm, we introduce an incremental distance sensitivity oracle (DSO) for undirected graphs with Õ(n²) worst-case update time, while preprocessing time, space, and query time are still Õ(n³), Õ(n²) and Õ(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 [Peng and Rubinstein 2023], 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 Õ(n³) 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 Õ(n³) time complexity for 2-fault SSRP is also nearly optimal. Now we know that in undirected graphs 1FRP can be solved in Õ(m) time [Nardelli, Proietti, Widmayer 2001], and 2FRP and 3FRP in undirected graphs can be solved in Õ(n³) time. In this paper, we also show that a truly subcubic algorithm for 2FRP in undirected weighted graphs does not exist under APSP hypothesis.