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 minimum 4 -way cut of an undirected weighted graph G . Let G=(V, E) be an undirected 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, respectively, 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-and-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, respectively.