IMSc Webinar

Optimal Output Sensitive Fault Tolerant Cuts

Niranka Banerjee

IMSc

Webinar: join at https://bluejeans.com/952068077 In this talk we consider two classic cut-problems, Global Minimum Cut and Minimum k-way cut, 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 upper and lower bounds on the size of the sparsest subgraph $H$ of $G$ that preserves edge connectivity of $G$ in the case of Global Minimum Cut, and the minimum number of edges whose removal partition the graph into at least $k$ connected components in the case of Minimum k-way cut, upon failure of any $f$ edges of $G$. Our upper bounds exploit the structural properties of $k$-connectivity 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 subgraph $H$ of $G$ must contain all its edges. This is joint work with Venkatesh Raman and Saket Saurabh.