Seminars & Colloquia Calendar

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.