A fast algorithm for computing minimum 3-way and 4-way cuts

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(n^k–1 F(n, m)) = O(mn^k log(n²/m)) time and O(n²) space for k = 3, 4, where F(n, m) denotes the time bound required to solve the maximum flow problem in G. The bound for k = 3 matches the current best deterministic bound Õ(mn³) for weighted graphs, but improves the bound Õ(mn³) to O(n² F(n, m)) = O(min{mn^8/3, m^3/2n²}) for unweighted graphs. The bound Õ(mn⁴) for k = 4 improves the previous best randomized bound Õ(n⁶) (for m = o(n²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.