A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network's edges or vertices. This article addresses the problem of designing a fault-tolerant (α, β ) approximate BFS structure (or FT-ABFS structure for short), namely, a subgraph H of the network G such that subsequent to the failure of some subset F of edges or vertices, the surviving part of H (namely, H \ F ) still contains an approximate BFS spanning tree for (the surviving part of) G, Our first result is an algorithm that given an n-vertex unweighted undirected graph G and a source s constructs a multiplicative (3, 0) FT-ABFS structure rooted at s resilient to a failure of a single edge with at most 4n edges (improving by an O (log n) factor on the near-tight result of Baswana and Khanna (2010) for the special case of edge failures). This was recently improved to 2n edges by Bilò et al. (2014) . Next, we consider the multiple edge faults case, for a constant integer f > 1, we prove that there exists a (polynomial-time constructible) (3f , f log n) FT-ABFS structure with O ( f n) edges that is resilient against f faults. We also show the existence of a (3f + 1, 0) FT-ABFS structure with O ( f log f n · n) edges. We then consider additive (1, β ) FT-ABFS structures and demonstrate an interesting dichotomy between multiplicative and additive spanners. In contrast to the linear size of (α, 0) FT-ABFS structures, we show that for every n, there exist δ, ϵ > 0, and n-vertex graphs G with a source s for which any (1, n δ ) FT-ABFS structure rooted at s has Ω(n 7/6−ϵ ) edges. For the case of additive stretch 3, we show that (1, 3) FT-ABFS structures admit a lower bound of Ω(n 5/4 ) edges.
Parter and Peleg showed in REF a lower bound of Ω(n 1+ε β ) edges for single-source FT β-additive spanners.
Fault-Tolerant Approximate BFS Structures
TALG
Mathematics Computer Science