2017/04/23 by Manoj Gupta, Gupta, Manoj, Shahbaz Khan +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #E.1 #F.2.2 #FOS: Computer and information sciences #G.2.2 #G.4 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1704.06907
openalex publication_date 2017/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a graph with n vertices and m edges, with a designated set of σ sources S⊆ V. The fault tolerant subgraph for any graph problem maintains a sparse subgraph H of G, such that for any set F of k failures, the solution for the graph problem on G∖ F is maintained in H∖ F. We address the problem of maintaining a fault tolerant subgraph for Breath First Search tree (BFS) of the graph from a single source s∈ V (referred as k FT-BFS) or multiple sources S⊆ V (referred as k FT-MBFS). The problem of k FT-BFS was first studied by Parter and Peleg [ESA13]. They designed an algorithm to compute FT-BFS subgraph of size O(n3/2). Further, they showed how their algorithm can be easily extended to FT-MBFS requiring O(σ1/2n3/2) space. They also presented matching lower bounds for these results. The result was later extended to solve dual FT-BFS by Parter [PODC15] requiring O(n5/3) space, again with matching lower bounds. However, their result was limited to only edge failures in undirected graphs and involved very complex analysis. Moreover, their solution doesn't seems to be directly extendible for dual FT-MBFS problem. We present a similar algorithm to solve dual FT-BFS problem with a much simpler analysis. Moreover, our algorithm also works for vertex failures and directed graphs, and can be easily extended to handle dual FT-MBFS problem, matching the lower bound of O(σ1/3n5/3) space described by Parter [PODC15].The key difference in our approach is a much simpler classification of path interactions which formed the basis of the analysis by Parter [PODC15]. Our dual FT-MBFS structure also seamlessly gives a dual fault tolerant spanner with additive stretch of +2 having size O(n7/8).