Breaking the nk barrier for minimum k-cut on simple graphs

In the minimum k-cut problem, we want to find the minimum number of edges whose deletion breaks the input graph into at least k connected components. The classic algorithm of Karger and Stein runs in Õ(n2k−2) time, and recent, exciting developments have improved the running time to O(nk). For general, weighted graphs, this is tight assuming popular hardness conjectures.