Sparse Fault-Tolerant BFS Trees

This paper addresses the problem of designing a sparse {\em fault-tolerant} BFS tree, or {\em FT-BFS tree} for short, namely, a sparse subgraph \(T\) of the given network \(G\) such that subsequent to the failure of a single edge or vertex, the surviving part \(T'\) of \(T\) still contains a BFS spanning tree for (the surviving part of) \(G\). Our main results are as follows. We present an algorithm that for every \(n\)-vertex graph \(G\) and source node \(s\) constructs a (single edge failure) FT-BFS tree rooted at \(s\) with \(O(n \cdot \min\{\Depth(s), \sqrt{n}\})\) edges, where \(\Depth(s)\) is the depth of the BFS tree rooted at \(s\). This result is complemented by a matching lower bound, showing that there exist \(n\)-vertex graphs with a source node \(s\) for which any edge (or vertex) FT-BFS tree rooted at \(s\) has \(\Omega(n^{3/2})\) edges. We then consider {\em fault-tolerant multi-source BFS trees}, or {\em FT-MBFS trees} for short, aiming to provide (following a failure) a BFS tree rooted at each source \(s\in S\) for some subset of sources \(S\subseteq V\). Again, tight bounds are provided, showing that there exists a poly-time algorithm that for every \(n\)-vertex graph and source set \(S \subseteq V\) of size \(\sigma\) constructs a (single failure) FT-MBFS tree \(T^*(S)\) from each source \(s_i \in S\), with \(O(\sqrt{\sigma} \cdot n^{3/2})\) edges, and on the other hand there exist \(n\)-vertex graphs with source sets \(S \subseteq V\) of cardinality \(\sigma\), on which any FT-MBFS tree from \(S\) has \(\Omega(\sqrt{\sigma}\cdot n^{3/2})\) edges. Finally, we propose an \(O(\log n)\) approximation algorithm for constructing FT-BFS and FT-MBFS structures. The latter is complemented by a hardness result stating that there exists no \(\Omega(\log n)\) approximation algorithm for these problems under standard complexity assumptions.