Approximation Algorithms for Generalized Multicut in Trees

Given a tree T with costs on edges and a collection of terminal sets X={S\-1,S\-2,…,S\-l}, the generalized multicut in trees problem asks to find a set of edges on T whose removal cuts every terminal set in X, such that the total cost of the picked edges is minimized. The problem has its own interest since it naturally generalizes the classical multicut problem and the multiway cut problem, respectively, and also is the dual of the generalized Steiner forest problem. It is shown that the full version of the problem can be approximated within a factor of 2 by reducing it to the classical multicut in trees problem. In the prize-collecting version of the problem, a terminal set must pay the penalty π\-i if it is not cut by the picked edges. A primal-dual 3-approximation algorithm is given for the prize-collecting generalized multicut in trees problem via primal-dual schema. The k-version of the problem has to cut at least k terminal sets at the minimum cost, where k is a given parameter. It is shown that the k-version of the problem can be approximated within a factor of min{2（l-k+1）,k} via a non-uniform approach. Furthermore, it is shown that there is an interesting relation between the generalized k-multicut in trees problem and the dense k-subgraph problem, implying that approximating the k-version of the problem within O（n\-\{16-ε\}） for some small ε>0 is difficult.