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 \emph{f-edge-fault-tolerant} (f-EFT) ?{\em -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 at most by a factor of ?. 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 \emph{unweighted} graphs, having the same size but guaranteeing a larger stretch factor of 3(f+1), plus an additive term of (f+1)logn. Then, we show how to convert our structure into an efficient f-EFT \emph{single-source distance oracle} (SSDO), that can be built in O~(fm) time, has size O(fnlog2n), and is able to report, after the failure of the edge set F, in O(|F|2log2n) time a (2|F|+1)-approximate distance from the source to any node, and a corresponding approximate path in the same amount of time plus the path's size. Such an oracle is obtained by handling another fundamental problem, namely that of updating a \emph{minimum spanning forest} (MSF) of G after that a \emph{batch} of k simultaneous edge modifications (i.e., edge insertions, deletions and weight changes) is performed. For this problem, we build in O(mlog3n) time a \emph{sensitivity} oracle of size O(mlog2n), that reports in O(k2log2n) time the (at most 2k) edges either exiting from or entering into the MSF. [...]