Abstract
Minimum cut problems are among the most well-studied questions in combinatorial optimization. In this talk, I will introduce a simple but powerful new tool for solving minimum cut problems called the minimum isolating cuts. I will show how this tool can be employed to obtain faster algorithms for several fundamental min-cut problems, namely global min-cut, Steiner min-cut, and all-pairs min-cut. For these problems, the new results represent the first improvement in their runtimes in several decades.
These results are in collaboration with Amir Abboud, Robert Krauthgamer, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi.