Article ID Journal Published Year Pages File Type
4949739 Discrete Applied Mathematics 2017 8 Pages PDF
Abstract
A vertex set X of a graph G is an association set if each component of G−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) time.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,