An approximation algorithm for the Generalized k-Multicut problem
An approximation algorithm for the Generalized k-Multicut problem
复制标题
DOI：
10.1016/j.dam.2012.01.016
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
Peng Zhang;Daming Zhu;Junfeng Luan
中科院分区：
文献类型：
--
作者：
Peng Zhang;Daming Zhu;Junfeng Luan
给定一个图G=（V，E），其边定义为非负代价，k为正整数，D={S1，S2，.，Sq}为q个端集的集合，其中每个Si是V（G）的子集，广义k-多割问题要求以最小代价找到一个边集C ∈ E（G），使得从G中删除它至少割D中的k个端集.一个终端子集Si被C切割，如果Si中的所有终端通过从G中移除C而彼此断开。这个问题是k-多割问题和多路割问题的推广。著名的Denk-Subgraph问题可以通过近似保持约简转化为树中的广义k-多割问题。本文首先给出了当输入图是树时广义k-多割问题的一个O（q）-近似算法。该算法是基于LP舍入和贪婪方法的混合策略。此外，该算法适用于处理一类NP-难的局部优化问题。作为它的推广，我们证明了该算法对于无向图中的广义k-多割问题可以给出O（qlogn）-逼近，对于k-森林问题可以给出O（q）-逼近.
Given a graph G=(V,E) with nonnegative costs defined on edges, a positive integer k, and a collection of q terminal sets D={S1,S2,…,Sq}, where each Siis a subset of V(G), the Generalized k-Multicut problem asks to find a set of edges C⊆E(G) at the minimum cost such that its removal from G cuts at least k terminal sets in D. A terminal subset Siis cut by C if all terminals in Siare 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(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(qlogn)-approximation for the Generalized k-Multicut problem in undirected graphs and O(q)-approximation for the k-Forest problem.