Minimum k-way cuts via deterministic greedy tree packing

We present a simple and fast deterministic algorithm for the minimum k-way cut problem in a capacitated graph, that is, finding a set of edges with minimum total capacity whose removal splits the graph into at least k components. The algorithm packs O(mk 3 log n) trees. Each new tree is a minimal spanning tree with respect to the edge utilizations, and the utilization of an edge is the number of times it has been used in previous spanning trees divided by its capacity. We prove that each minimum k-way cut is crossed at most 2k-2 times by one of the trees. We can enumerate all such cuts in ~O(n 2k ) time, which is hence the running time of our algorithm producing all minimum k-way cuts. The previous fastest deterministic algorithm of Kamidoi et al. [SICOMP'06] took O(n (4+o(1))k ) time, so this is a near-quadratic improvement. Moreover, we essentially match the O(n (2-o(1))k ) running time of the Monto Carlo (no correctness guarantee) randomized algorithm of Karger and Stein [JACM'96].

Authors

• Mikkel Thorup

Keywords

• k-way cuts
• tree packing