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 [KS96] runs in Õ(n 2k-2 ) time, 1 and recent, exciting developments have improved the running time to O(n k ) [GHLL20]. For general, weighted graphs, this is tight assuming popular hardness conjectures.

In this work, we show that perhaps surprisingly, O(n k ) is not the right answer for simple, unweighted graphs. We design an algorithm that runs in time O(n (1-ǫ)k ) where ǫ > 0 is an absolute constant, breaking the natural n k barrier. This establishes a separation of the two problems in the unweighted and weighted cases.