Minimum cost subpartitions in graphs

Given an edge-weighted graph G=(V,E), a subset S⊆V, an integer k⩾1 and a real b⩾0, the minimum subpartition problem asks to find a family of k nonempty disjoint subsets X1,X2,…,Xk⊆S with d(Xi)⩽b, 1⩽i⩽k, so as to minimize ∑1⩽i⩽kd(Xi), where d(X) denotes the total weight of edges between X and V−X. In this paper, we show that the minimum subpartition problem can be solved in O(mn+n2logn) time. The result is then applied to the minimum k-way cut problem and the graph strength problem to improve the previous best time bounds of 2-approximation algorithms for these problems to O(mn+n2logn).