For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k = 3, 4. The algorithm runs in O(nk-2(nF(n,m) + C2(n,m) + n2)) = O(mnk log(n2/m)) time for k = 3, 4, where F(n,m) and C2(n,m) denote respectively the time bounds required to solve the maximum flow problem and the minimum 2-way cut problem in G. The bound for k = 3 matches the current best deterministic bound O(mn3) for weighted graphs, but improves the bound O(mn3) to O(n(nF(n,m) + C2(n,m) + n2)) = O(min{mn8/3, m3/2n2}) for unweighted graphs. The bound O(mn4) for k = 4 improves the previous best randomized bound O(n6) (for m = o(n2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.
['Hiroshi Nagamochi', 'Toshihide Ibaraki']
A Fast Algorithm for Computing Minimum 3-Way and 4-Way Cuts