In the k-cut problem, we want to find the smallest set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger & Stein and Thorup showed how to find such a minimum k-cut in time approximately O(n^{2k}). The best lower bounds come from conjectures about the solvability of the k-clique problem and a reduction from k-clique to k-cut , and show that solving k-cut is likely to require time \Omega(n^k). Recent results of Gupta, Lee & Li have given special-purpose algorithms that solve the problem in time n^{1.98k + O(1)}, and ones that have better performance for special classes of graphs (e.g., for small integer weights). In this work, we resolve the problem for general graphs, by showing that for any fixed k \geq 2, the Karger-Stein algorithm outputs any fixed k-cut of weight \alpha \lambda_k with probability at least O _k(n^{-\alpha k}), where \lambda_k denotes the minimum k-cut size. This also gives an extremal bound of O_k(n^k) on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar 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 a fine-grained analysis of how the graph shrinks---and how the average degree evolves---under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size less than 2 \lambda_k/k, using the Sunflower lemma.
In the k-cut problem, we want to find the smallest set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger & Stein and Thorup showed how to find such a minimum k-cut in time approximately O(n^{2k}). The best lower bounds come from conjectures about the solvability of the k-clique problem , and show that solving k-cut is likely to require time \Omega(n^k). Recent results of Gupta, Lee & Li have given special-purpose algorithms that solve the problem in time n^{1.98k + O(1)}, and ones that have better performance for special classes of graphs (e.g., for small integer weights). In this work, we resolve the problem for general graphs, by showing that the Contraction Algorithm of Karger outputs any fixed k-cut of weight \alpha \lambda_k with probability \Omega _k(n^{-\alpha k}), where \lambda_k denotes the minimum k-cut size. This also gives an extremal bound of O_k(n^k) on the number of minimum k-cuts and an algorithm to compute a minimum k-cut in similar 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 a fine-grained analysis of how the graph shrinks -- and how the average degree evolves -- in the Karger process. The second ingredient is an extremal bound on the number of cuts of size less than 2 \lambda_k/k, using the Sunflower lemma.
D
and a reduction from k-clique to k-cut
R
for any fixed k \geq 2, the Karger-Stein algorithm
the Contraction Algorithm of Karger
R
at least O
\Omega
D
in an n-vertex graph
R
shrinks---and
shrinks -- and
R
evolves---under the Karger-Stein
evolves -- in the Karger
R
result bounding
bound on