Seminar Talk: Minimum Cuts in Graphs: Old Problems, New Ideas, and Near-Optimal Algorithms

Abstract: Minimum cut problems in graphs are among the most basic questions in algorithm design. We teach them in our classes, use them as standard tools in algorithms research, and apply them to solve real-world problems in a broad range of domains. Yet, after decades of research into designing faster algorithms for these problems, progress on many of the key questions stalled in the late 1990s. This lull of over two decades has been dramatically broken in the last few years with a series of results in rapid progression that have achieved close to optimal solutions for many of the important problems in this area such as global minimum cut, vertex connectivity, and all-pairs minimum cuts. A common theme running through these results is a fundamentally better understanding of how these problems relate to maximum flows, which then allows leveraging recent progress in maximum flow algorithms for solving these problems. In this talk, I will discuss our work on identifying these connections and the results they lead to, focusing on the conceptually new ideas that have driven this progress. I will also outline what lies ahead: the (equally important) questions that we haven’t made progress on and where the challenges of the future lie.

Bio: Debmalya Panigrahi is a Professor of Computer Science at Duke University. His research interests are broadly in the design and analysis of algorithms. In graph algorithms, his recent work has obtained nearly optimal algorithms for fundamental cut problems, overcoming long-standing barriers that have stood for several decades. In algorithms under uncertainty, his recent work has leveraged machine-learned future predictions in the design of online algorithms. Other areas that he has worked in include online and approximation algorithms, combinatorial optimization, algorithmic game theory, and applied algorithms. He is a recipient of an NSF CAREER Award, faculty research awards from Google and Yahoo, a best paper award at SPAA, a best paper honorable mention at WWW, and multiple special issue invitations at FOCS and STOC. He received his PhD from MIT in 2012 where he was a Presidential Fellow.