  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 $\tilde O(n^{2k-2})$ time,
and recent, exciting developments have improved the running time to $O(n^k)$.
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-\epsilon)k})$ where $\epsilon>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.
