An approximation algorithm for the Generalized k k -Multicut problem ?
Given a graph G=(V,E) G = ( V , E ) with nonnegative costs defined on edges, a positive integer k k , and a collection of q q terminal sets D={S1,S2,,Sq} D = { S 1 , S 2 ,  , S q } , where each Si S i is a subset of V(G) V ( G ) , the Generalized k k -Multicut problem asks to find a set of edges C?E(G) C ? E ( G ) at the minimum cost such that its removal from G G cuts at least k k terminal sets in D D . A terminal subset Si S i is cut  by C C if all terminals in Si S i are disconnected from one another by removing C C from G G . This problem is a generalization of the k k -Multicut problem and the Multiway Cut problem. The famous Densest k k -Subgraph problem can be reduced to the Generalized k k -Multicut problem in trees via an approximation preserving reduction. In this paper, we first give an O ( q ) -approximation algorithm for the Generalized k k -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 ( q log n ) -approximation for the Generalized k k -Multicut problem in undirected graphs and O ( q ) -approximation for the k k -Forest problem.
approximation algorithm lp-rounding k k -multicut k k k k k k k -forest k k k k k combinatorial optimization