All-pairs minimum cuts in nearly quadratic time: a tutorial

Abstract: We recently showed an algorithm for computing all-pairs minimum cuts (or, more precisely, the Gomory-Hu tree) in $\tilde{O}(n^2)$ time in weighted graphs and even almost-linear time in unweighted graphs. For weighted graphs, this is the first improvement over the 60-year-old algorithm by Gomory and Hu. Thus, surprisingly, computing all-pairs minimum cuts seems to be strictly easier than computing all-pairs shortest paths, which is conjectured to require $n^{3-o(1)}$ time.

I will give a tutorial on the techniques behind our new result, one of which is called "isolating cuts". Then, I will survey recent progress in fast minimum cut algorithms and discuss open problems.

Joint work with Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, and Ohad Trabelsi.

computational complexitycomputational geometrycryptography and securitydiscrete mathematicsdata structures and algorithmsgame theorymachine learningquantum computing and informationcombinatoricsinformation theoryoptimization and controlprobability

Audience: researchers in the topic

TCS+

Series comments: Description: Theoretical Computer Science

People can register to a talk via our webpage sites.google.com/site/plustcs/livetalk , or subscribe to our calendar and mailing list at sites.google.com/site/plustcs/rss-feeds