Approximate association via dissociation

详细信息    查看全文

• 作者：Jie You^a ; ^b ; Jianxin Wang^a ; Yixin Cao^b ; ^{yixin.cao@polyu.edu.hk}
• 关键词：Association set (cluster vertex deletion) ; Dissociation set ; Cluster graph ; Modular decomposition ; Triangle-free graph
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：11 March 2017
• 年：2017
• 卷：219
• 期：Complete
• 页码：202-209
• 全文大小：672 K
• 卷排序：219

文摘

A vertex set XX of a graph GG is an association set if each component of G−XG−X is a clique, and a dissociation set if each of these cliques has only one or two vertices. We observe some special structures and show that if none of them exists, then the minimum association set problem can be reduced to the minimum weighted dissociation set problem. This yields the first nontrivial approximation algorithm for the association set problem, with approximation ratio 2.5. The reduction is based on a combinatorial study of modular decomposition of graphs free of these special structures. Further, a novel algorithmic use of modular decomposition enables us to implement our algorithm in O(mn+n2)O(mn+n2) time.