An approximation algorithm for the Generalized kk-Multicut problem

Given a graph G=(V,E)G=(V,E) with nonnegative costs defined on edges, a positive integer kk, and a collection of qq terminal sets D={S1,S2,…,Sq}D={S1,S2,…,Sq}, where each SiSi is a subset of V(G)V(G), the Generalized kk-Multicut problem asks to find a set of edges C⊆E(G)C⊆E(G) at the minimum cost such that its removal from GG cuts at least kk terminal sets in DD. A terminal subset SiSi is cut   by CC if all terminals in SiSi are disconnected from one another by removing CC from GG. This problem is a generalization of the kk-Multicut problem and the Multiway Cut problem. The famous Densest kk-Subgraph problem can be reduced to the Generalized kk-Multicut problem in trees via an approximation preserving reduction.In this paper, we first give an O(q)-approximation algorithm for the Generalized kk-Multicut problem when the input graph is a tree. The algorithm is based on a mixed strategy of LP-rounding and greedy approach. Moreover, the algorithm is applicable to deal with a class of NP  -hard partial optimization problems. As its extensions, we then show that the algorithm can be used to give O(qlogn)-approximation for the Generalized kk-Multicut problem in undirected graphs and O(q)-approximation for the kk-Forest problem.