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

arXiv: https://arxiv.org/abs/1906.00417 · HTML: https://mlsanity.com/paper/1906.00417/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2019.

## Built on by (most cited first, 1 of 1)

- [The Complexity of Manipulation of k-Coalitional Games on Graphs](https://mlsanity.com/paper/2408.07368/) (2024)

## Abstract (arXiv)

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.