Gupta, Manoj ;
Khan, Shahbaz
Multiple Source Dual Fault Tolerant BFS Trees
Abstract
Let G=(V,E) be a graph with n vertices and m edges, with a designated set of sigma sources S subseteq V. The fault tolerant subgraph for any graph problem maintains a sparse subgraph H=(V,E') of G with E' subseteq E, such that for any set F of k failures, the solution for the graph problem on G\F is maintained in its subgraph H\F. We address the problem of maintaining a fault tolerant subgraph for computing Breath First Search tree (BFS) of the graph from a single source s in V (referred as k FTBFS) or multiple sources S subseteq V (referred as k FTMBFS). We simply refer to them as FTBFS (or FTMBFS) for k=1, and dual FTBFS (or dual FTMBFS) for k=2.
The problem of k FTBFS was first studied by Parter and Peleg [ESA13]. They designed an algorithm to compute FTBFS subgraph of size O(n^{3/2}). Further, they showed how their algorithm can be easily extended to FTMBFS requiring O(sigma^{1/2}n^{3/2}) space. They also presented matching lower bounds for these results. The result was later extended to solve dual FTBFS by Parter [PODC15] requiring (n^{5/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 FTMBFS problem.
We present a similar algorithm to solve dual FTBFS 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 FTMBFS problem, matching the lower bound of O(sigma^{1/3}n^{5/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].
BibTeX  Entry
@InProceedings{gupta_et_al:LIPIcs:2017:7418,
author = {Manoj Gupta and Shahbaz Khan},
title = {{Multiple Source Dual Fault Tolerant BFS Trees}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {127:1127:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7418},
URN = {urn:nbn:de:0030drops74184},
doi = {10.4230/LIPIcs.ICALP.2017.127},
annote = {Keywords: BFS, faulttolerant, graph, algorithms, datastructures}
}
07.07.2017
Keywords: 

BFS, faulttolerant, graph, algorithms, datastructures 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 