Fault Tolerant Approximate BFS Structures with Additive Stretch

This paper addresses the problem of designing a ββ-additive fault-tolerant approximate BFS (or FT-ABFS for short) structure, namely, a subgraph H of the network G such that subsequent to the failure of a single edge e, the surviving part of H still contains an approximate BFS spanning tree for (the surviving part of) G, whose distances satisfy dist(s,v,H∖{e})≤dist(s,v,G∖{e})+βdist(s,v,H∖{e})≤dist(s,v,G∖{e})+β for every v∈Vv∈V. It was shown in Parter and Peleg (SODA, 2014), that for every β∈[1,O(logn)]β∈[1,O(log⁡n)] there exists an n-vertex graph G with a source s for which any ββ-additive FT-ABFS structure rooted at s has Ω(n1+ϵ(β))Ω(n1+ϵ(β)) edges, for some function ϵ(β)∈(0,1)ϵ(β)∈(0,1). In particular, 3-additive FT-ABFS structures admit a lower bound of Ω(n5/4)Ω(n5/4) edges. In this paper we present the first upper bound, showing that there exists a poly-time algorithm that for every n-vertex unweighted undirected graph G and source s constructs a 4-additive FT-ABFS structure rooted at s with at most O(n4/3)O(n4/3) edges. The main technical contribution of our algorithm is in adapting the path-buying strategy used in Baswana et al. (ACM Trans Algorithms 7:A5, 2010) and Cygan et al. (Proceedings of the 30th symposium on theoretical aspects of computer science, pp 209–220, 2013) to failure-prone settings.