A divide-and-conquer approach to the minimum k-way cut problem

This paper presents algorithms for computing a minimum 3-way cut and a mini mum 4-way cut of an undirected weighted graph G. Let G = (V, E) bean undire cted graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k-way cut problem with fixed k, that requires O (n(4)) and O (n(6)) maximum flow computations, re spectively, to compute a minimum 3-way cut and a minimum 4-way cut of G. In this paper we first show some properties on minimum 3-way cuts and minimum 4-way cuts, which indicate a recursive structure of the minimum k-way cut problem when k = 3 and 4. Then, based on those properties, we give divide-a nd-conquer algorithms for computing a minimum 3-way cut and a minimum 4-way cut of G, which require O(n(3)) and O(n(4)) maximum flow computations, res pectively.