TY - GEN

T1 - The number of minimum k-cuts

T2 - 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019

AU - Gupta, Anupam

AU - Lee, Euiwoong

AU - Li, Jason

N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.

PY - 2019/6/23

Y1 - 2019/6/23

N2 - 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 kcuts 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.

AB - 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 kcuts 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.

KW - Extremal graph theory

KW - Graph algorithms

KW - Graph cuts

KW - Minimum k-cut

UR - http://www.scopus.com/inward/record.url?scp=85068744985&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068744985&partnerID=8YFLogxK

U2 - 10.1145/3313276.3316395

DO - 10.1145/3313276.3316395

M3 - Conference contribution

AN - SCOPUS:85068744985

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 229

EP - 240

BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

A2 - Charikar, Moses

A2 - Cohen, Edith

PB - Association for Computing Machinery

Y2 - 23 June 2019 through 26 June 2019

ER -