The number of minimum k -cuts: improving the Karger-Stein bound

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 ). Since then, the algorithmic side of the minimum k -cut problem has seen much progress, leading to a deterministic algorithm based on a tree packing result of Thorup, which enumerates all minimum k -cuts in the same asymptotic running time, and gives an alternate proof of the O ( n (2− o (1)) k ) bound. However, beating the Karger–Stein bound, even for computing a single minimum k -cut, has remained out of reach. 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 combine ideas from both the Karger–Stein and Thorup results, and draw a novel 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.

Authors

• Anupam Gupta 0001
• Euiwoong Lee
• Jason Li 0006

Keywords

• extremal graph theory
• graph algorithms
• graph cuts
• minimum k-cut