Fast and Deterministic Approximations for k-Cut

In an undirected graph, a k-cut is a set of edges whose removal breaks the graph into at least k connected components. The minimum-weight k-cut can be computed in n(O(k)) time, but when k is treated as part of the input, computing the minimum-weight k-cut is NP-hard [Goldschmidt and Hochbaum 1994]. For poly(m, n, k)-time algorithms, the best possible approximation factor is essentially 2 under the Small-Set Expansion Hypothesis [Manurangsi 2017]. Saran and Vazirani [1995] showed that a (2-2/k)-approximately minimum-weight k-cut can be computed via O(k) minimum cuts, which implies a (O) over tilde (km) randomized running time via the nearly linear-time randomized min-cut algorithm of Karger [2000]. Nagamochi and Kamidoi [2007] showed that a (2-2/k)-approximately minimum-weight k-cut can be computed deterministically in O(mn + n(2)log n) time. These results prompt two basic questions. The first concerns the role of randomization. Is there a deterministic algorithm for 2-approximate minimum k-cut, matching the randomized running time of (O) over tilde (km)? The second question qualitatively compares minimum cut to 2-approximate minimum k-cut. Can 2-approximate minimum k-cut be computed as fast as the minimum cut-in (O) over tilde (m) randomized time?