Faster Minimum k-cut of a Simple Graph

We consider the (exact, minimum) k-CUT problem: given a graph and an integer k, delete a minimum-weight set of edges so that the remaining graph has at least k connected components. This problem is a natural generalization of the global minimum cut problem, where the goal is to break the graph into k=2 pieces. Our main result is a (combinatorial) k-CUT algorithm on simple graphs that runs in n (1+o (1) ) k time for any constant k, improving upon the previously best n (2ω/3+o (1) ) k time algorithm of Gupta et al. FOCS'18 and the previously best n^ (1. 981+o (1) ) k time combinatorial algorithm of Gupta et al. STOC'19. For combinatorial algorithms, this algorithm is optimal up to o (1) factors assuming recent hardness conjectures: we show by a straightforward reduction that k-CUT on even a simple graph is as hard as (k-1) -clique, establishing a lower bound of n (1-o (1) ) k for k-CUT. This settles, up to lower-order factors, the complexity of k-CUT on a simple graph for combinatorial algorithms.