The multi-multiway cut problem

In this paper, we define and study a natural generalization of the multicut and multiway cut problems: the minimum multiintiltiwaY cut problem. The input to the problem is a weighted undirected graph G = (V, E) and k sets S-1, S-2,..., S-k of vertices. The goal is to find a subset of edges of minimum total weight whose removal completely disconnects each one of the sets S-1, S-2... S-k,. i.e., disconnects every pair of vertices u and v such that u, v E Si, for some i. This problem generalizes both the multicut problem, when vertical bar S-i vertical bar = 2, for 1 <= i <= k, and the multiway cut problem, when k = 1. We present an approximation algorithm for the multi-multiway cut problem with an approximation ratio which matches that obtained by Garg, Vazirani, and Yarmakakis on the standard multicut problem. Namely, our algorithm has an 0 (log k) approximation ratio. Moreover, we consider instances of the minimum multi-multiway cut problem which are known to have an optimal solution of light weight. We show that our algorithm has an approximation ratio substantially better than 0 (log k) when restricted to such "light" instances. Specifically, we obtain an O (log LP)-approximation algorithm for the problem when all edge weights are at least 1 (here LP denotes the.value of a natural linear programming relaxation of the problem). The latter improves the 0 (log LP log log LP) approximation ratio for the minimum multicut problem (implied by the work of Seymour and Even et al.). (c) 2007 Elsevier B.V. All rights reserved.