#### 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.*

Done