Download as iCal file

DIMACS Theory of Computing Seminar

The Number of Minimum k-Cuts: Improving the Karger-Stein Bound

 Euiwoong Lee (NYU)

Location:  CoRE 301
Date & time: Wednesday, 04 December 2019 at 11:00AM - 12:00PM

Abstract: Given an edge-weighted graph, how many minimum k-cuts can it have? This is a fundamental question in the intersection of algorithms, extremal combinatorics, and graph theory. It is particularly interesting in that the best known bounds are algorithmic: they stem from algorithms that compute the minimum k-cut. In 1994, Karger and Stein obtained a randomized contraction algorithm that finds a minimum k-cut in O(n^{(2-o(1))k}) time. It can also enumerate all such k-cuts in the same running time, establishing a corresponding extremal bound of O(n^{(2-o(1))k}). In this paper, we give an algorithm to enumerate all minimum k-cuts in O(n^{(1.981+o(1))k}) time, breaking the algorithmic and extremal barriers for enumerating minimum k-cuts. To obtain our result, we draw a new connection between minimum k-cut and extremal set theory. In particular, we give and use tighter bounds on the size of set systems with bounded dual VC-dimension, which may be of independent interest.