Breaking the $n^k$ Barrier for Minimum $k$-cut on Simple Graphs

Zhiyang He, Jason Li

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 K…