The Karger-Stein algorithm is optimal for k-cut

In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum k-cut in time approximately O(n 2k−2). 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 Ω(n k ). Our recent results 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).