Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees

Let G be an n-node and m-edge positively real-weighted undirected graph. For any given integer f≥ 1 , we study the problem of designing a sparse f-edge-fault-tolerant (f-EFT) σ-approximate single-source shortest-path tree (σ-ASPT), namely a subgraph of G having as few edges as possible and which, following the failure of a set F of at most f edges in G, contains paths from a fixed source that are stretched by a factor of at most σ. To this respect, we provide an algorithm that efficiently computes an f-EFT (2 | F| + 1) -ASPT of size O(fn). Our structure improves on a previous related construction designed for unweighted graphs, having the same size but guaranteeing a larger stretch factor of 3 (f+ 1) , plus an additive term of (f+ 1) log n. Then, we show how to convert our structure into an efficient f-EFT single-source distance oracle, that can be built in O(fmα(m,n)+fnlog3n) time, has size O(fnlog 2n) , and in O(| F| 2log 2n) time is able to report a (2 | F| + 1) -approximate distance from the source to any node in G- F. Moreover, our oracle can return a corresponding approximate path in the same amount of time plus the path’s size. The oracle is obtained by tackling another fundamental problem, namely that of updating a minimum spanning forest (MSF) of G following a batch of k simultaneous modification (i.e., edge insertions, deletions and weight changes). For this problem, we build in O(mlog 3n) time an oracle of size O(mlog 2n) , that reports in O(k2log 2n) time the (at most 2k) edges either exiting from or entering into the MSF. Finally, for any integer k≥ 1 , we complement all our results with a lower bound of Ω(n1+1k) to the size of any f-EFT σ-ASPT with f≥ log n and σ<3k+1k+1, that holds if the Erdős’ girth conjecture is true.