Generalizedk-multiway cut problems

This paper considers the following problem: given an edgeweighted graphG = (V, E, w) and disjointk-subsetsU _p ofV, find a minimum weighted set of edgesE′ ?E such that its removal disconnects the graph intok parts and each part contains exactly one vertex from eachU _p for 1 ≤p ≤r. This generalizes some well-known NP-hard problems. In this paper, we first apply greedy local search algorithm to obtain better approximation solutions. Then we give a randomized local search algorithm which produces a solution within a factor (1 + ε) with the probability at least (1 - 1/e) for any small ε. Simple near-optimum approximation algorithms are also proposed. Analogously, there is a maximumk-multiway cut problem with the same restrictions.