Faster Minimum k-cut of a Simple Graph
Jason Li · 2019
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))ktime for any constant k, improving upon the previously best n(2ω/3+o(1))ktime 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))kfor k-CUT. This settles, up to lower-order factors, the complexity of k-CUT on a simple graph for combinatorial algorithms.