In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with the running time of O(n^{2k-2}). Using tree packings, Thorup gave a deterministic algorithm that has the same running time. In this work, we show that for any fixed k >= 2, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least Omega(n^{-k}). This also gives an extremal bound of O(n^k) on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are essentially tight. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks---and how the average degree evolves---under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most (2-delta)OPT/k, using the Sunflower lemma. Joint work with Anupam Gupta, David G. Harris, and Jason Li

ZOOM 회의 참가

•링크: https://snu-ac-kr.zoom.us/j/84541226235?pwd=N2lJNUNEUldabVU5dWw2d0p3cjZwZz09

•회의 ID: 845 4122 6235

•비밀번호: 210722

Euiwoong Lee is an assistant professor at the University of Michigan. He got his PhD from Carnegie Mellon University in 2017, and was a postdoc at New York University. His research interests lie in several topics of theoretical computer science including approximation algorithms and hardness of approximation.