Algorithms & Randomness Center (ARC)
Debmalya Panigrahy (Duke University)
Monday, August 24, 2020
Virtual via Bluejeans - 11:00 am
Title: Deterministic Min-cut in Poly-logarithmic Max-flows
Abstract: The min-cut problem in undirected graphs asks for a minimum (weight) subset of edges whose removal disconnects the graph. In the 1990s, Karger developed several randomized (Monte Carlo) algorithms for this problem, leading to an eventual running time bound of \tilde{O}(m). At the time, the best deterministic algorithms for the problem, from the early 1990s, were much slower and ran in \tilde{O}(mn) time. This led him to ask whether the min-cut problem can be solved in \tilde{O}(m) time deterministically as well. Unfortunately, even after almost 30 years, the \tilde{O}(mn) bound is still the best known for general weighted graphs. In this talk, I will present a new deterministic min-cut algorithm that uses polylog(n) max-flow computations. Using the current best max-flow algorithms, this results in an overall running time of \tilde{O}(m \min(\sqrt{m}, n^{2/3}}) for weighted graphs, and \tilde{O}(m^{4/3}) for unweighted (multi)-graphs, thereby breaking the longstanding \tilde{O}(mn) bound. (The \tilde{O} notation hides sub-polynomial factors.) This is based on joint work with Jason Li.
----------------------------------
Videos of recent talks are available at: http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
