• This event has passed.

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

Tuesday, July 27, 2021 @ 3:00 PM - 4:00 PM KST

Room B232, IBS (기초과학연구원)

Speaker

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.

Details

Date:
Tuesday, July 27, 2021
Time:
3:00 PM - 4:00 PM KST
Event Category:
Event Tags:
,

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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