Dual failure resilient BFS structure

We study breadth-first search (BFS) spanning trees, and ad- dress the problem of designing a sparse fault-tolerant BFS structure, or FT-BFS for short, resilient to the failure of up to two edges in the given unweighted undirected graph G, i.e., a sparse subgraph H of G such that subsequent to the failure of up to two edges, the surviving part H0 of H still contains a BFS spanning tree for (the surviving part of) G. FT-BFS structures, as well as the related notion of re- placement paths, have been studied so far for the restricted case of a single failure. It has been noted widely that when concerning shortest-paths in a variety of contexts, there is a sharp qualitative difference between a single failure and two or more failures [7]. Our main results are as follows. We present an algorithm that for every n-vertex unweighted undirected graph G and source node s constructs a (two edge failure) FT-BFS structure rooted at s with O(n5=3) edges. To provide a useful theory of shortest paths avoiding 2 edges failures, we take a principled approach to classifying the arrangement these paths. We believe that the structural analysis provided in this paper may decrease the barrier for understanding the general case of f ≥ 2 faults and pave the way to the future design of f-fault resilient structures for f ≥ 2. We also provide a matching lower bound, which in fact holds for the general case of f ≥ 1 and multiple sources S ⊆ V . It shows that for every f ≥ 1, and integer 1 ≤ σ ≥ n, there exist n-vertex graphs with a source set S ⊆ V of cardinality σ for which any FT-BFS structure rooted at each s 2 S, resilient to up to f-edge faults has Ω(σ1=/(f+1) σ n2-1/(f+1)) edges. In particular, for f = 2 and σ = 1, a dual failure FT-BFS structure rooted at s must have (n5=3) edges in the worst case. Finally, we also consider the optimization variant for this problem, and propose an O(log n) approximation algorithm for constructing FT-BFS structures resilient to up to f-faults for any constant f ≥ 1 and any source set S ⊆ V.