An approximation algorithm for the Generalized k-Multicut problem

作者：Zhang, Peng^*; Zhu, Daming; Luan, Junfeng

来源：Discrete Applied Mathematics, 2012, 160(7-8): 1240-1247.

DOI：10.1016/j.dam.2012.01.016

• k-Multicut
• k-Forest
• LP-rounding
• Approximation algorithm
• Combinatorial optimization

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

• 出版日期2012-5
• 单位山东大学