Optimal Bounds for the k-cut Problem

In the k-cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi) graph into k connected components. Algorithms of Karger \& Stein can solve this in roughly O (n^2k) time. On the other hand, lower bounds from conjectures about the k-clique problem imply that Ω (n^ (1-o (1) ) k) time is likely needed. Recent results of Gupta, Lee \& Li have given new algorithms for general k-cut in n^1. 98k + O (1) time, as well as specialized algorithms with better performance for certain classes of graphs (e. g. , for small integer edge weights). In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixed k-cut of weight αλₖ with probability Ωₖ (n^-αk), where λₖ denotes the minimum k-cut weight. This also gives an extremal bound of Oₖ (nᵏ) on the number of minimum k-cuts and an algorithm to compute λₖ with roughly nᵏ polylog (n) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight k-clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 λₖ/k, using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks -- and how the average degree evolves -- in the Karger process.