Banerjee, Niranka ;
Raman, Venkatesh ;
Saurabh, Saket
Optimal Output Sensitive Fault Tolerant Cuts
Abstract
In this paper we consider two classic cutproblems, Global MinCut and Min kCut, via the lens of fault tolerant network design. In particular, given a graph G on n vertices, and a positive integer f, our objective is to compute an upper bound on the size of the sparsest subgraph H of G that preserves edge connectivity of G (denoted by λ(G)) in the case of Global MinCut, and λ(G,k) (denotes the minimum number of edges whose removal would partition the graph into at least k connected components) in the case of Min kCut, upon failure of any f edges of G. The subgraph H corresponding to Global MinCut and Min kCut is called fFTCS and fFTkCS, respectively. We obtain the following results about the sizes of fFTCS and fFTkCS.
 There exists an fFTCS with (n1)(f+λ(G)) edges. We complement this upper bound with a matching lower bound, by constructing an infinite family of graphs where any fFTCS must have at least ((nλ(G)1)(λ(G)+f1))/2+(nλ(G)1)+/λ(G)(λ(G)+1))/2 edges.
 There exists an fFTkCS with min{(2f+λ(G,k)(k1))(n1), (f+λ(G,k))(nk)+𝓁} edges. We complement this upper bound with a lower bound, by constructing an infinite family of graphs where any fFTkCS must have at least ((nλ(G,k)1)(λ(G,k)+fk+1))/2)+nλ(G,k)+k3+((λ(G,k)k+3)(λ(G,k)k+2))/2 edges. Our upper bounds exploit the structural properties of kconnectivity certificates. On the other hand, for our lower bounds we construct an infinite family of graphs, such that for any graph in the family any fFTCS (or fFTkCS) must contain all its edges. We also add that our upper bounds are constructive. That is, there exist polynomial time algorithms that construct H with the aforementioned number of edges.
BibTeX  Entry
@InProceedings{banerjee_et_al:LIPIcs:2020:13251,
author = {Niranka Banerjee and Venkatesh Raman and Saket Saurabh},
title = {{Optimal Output Sensitive Fault Tolerant Cuts}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {10:110:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771740},
ISSN = {18688969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13251},
URN = {urn:nbn:de:0030drops132515},
doi = {10.4230/LIPIcs.FSTTCS.2020.10},
annote = {Keywords: Fault tolerant, minimum cuts, upper bound, lower bound}
}
04.12.2020
Keywords: 

Fault tolerant, minimum cuts, upper bound, lower bound 
Seminar: 

40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 