## Euiwoong Lee (이의웅) gave a talk on the minimum k-cut problem at the Discrete Math Seminar

On July 27, 2021, Euiwoong Lee (이의웅) from the University of Michigan gave a talk at the Discrete Math Seminar on the proof that the Karger-Stein algorithm finds the minimum k-cuts with the probability $\Omega(n^{-k})$, which is tight and improves previous bounds. The title of his talk was “The Karger-Stein algorithm is optimal for k-cut“.

## Euiwoong Lee (이의웅), The Karger-Stein algorithm is optimal for k-cut

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\ge 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. 기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209