An Improved Divide-and-Conquer Algorithm for Finding All Minimum κ-Way Cuts

摘要

Given a positive integer k and an edge-weighted undirected graph G = (V, E; w), the minimum k-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. This problem is a natural generalization of the classical minimum cut problem and has been well-studied in the literature.rnA simple and natural method to solve the minimum k-way cut problem is the divide-and-conquer method: getting a minimum k-way cut by properly separating the graph into two small graphs and then finding minimum k'-way cut and k"-way cut respectively in the two small graphs, where k' + k" = k. In this paper, we present the first algorithm for the tight case of k' = 「k/2」 Our algorithm runs in O(n~(4k-1g k)) time and can enumerate all minimum k-way cuts, which improves all the previously known divide-and-conquer algorithms for this problem.