Breaking the $n^k$ Barrier for Minimum $k$-cut on Simple Graphs
Breaking the $n^k$ 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 $\tilde O(n^{2k-2})$ time, and recent, exciting developments have improved the running time to $O(n^k)$. For …