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

For an edge-weighted graph G with n vertices and rn edges, we present a new deterministic algorithm for computing a minimum k-way cut for k = 3, 4. Th e algorithm runs in O(n(k-1)F(n, m)) = O(mn(k) log(n(2)/m)) time and O(n(2) ) space for k = 3, 4, where F(n, m) denotes the time bound required to solv e the maximum flow problem in G. The bound for k = 3 matches the current be st deterministic bound (O) over tilde(mn(3)) for weighted graphs, but impro ves the bound (O) over tilde(mn(3)) to O(n(2) F(n, m)) = O(min{mn(8/3), m(3 /2)n(2)}) for unweighted graphs. The bound (O) over tilde(mn(4)) for k = 4 improves the previous best randomized bound (O) over tilde(n(6)) (for m = o (n(2))). The algorithm is then generalized to the problem of finding a mini mum 3-way cut in a symmetric submodular system.