A Bicriteria Approximation Algorithm for Generalized k-Multicut in Trees

Given a tree T = (V, E) with costs defined on edges, a positive integer k, and I terminal sets {S₁, S₂, . . ., S_l} with every S_i sube V, the generalized k-multicut in trees problem (k-GMC(T)) asks to find an edge subset in E at the minimum cost such that its removal cuts at least k terminal sets. The k-GMC(T) problem is a natural generalization of the classical multicut in trees problem and the multiway cut in trees problem. This problem is hard to be approximated within O(n^1/6-isin) for some small constant isin > 0 (Zhang, CiE´07). Based on a greedy approach and a rounding technique in linear programming, we give a bicriteria approximation algorithm for k-GMC(T). Our algorithm outputs in polynomial time a solution which cuts at least (1 - isin)k terminal sets and whose cost is within radic2/isinldrl times of the optimum for any small constant isin > 0, and hence gives sublinear approximation ratio for k-GMC(T).