TY - GEN

T1 - Approximate association via dissociation

AU - You, Jie

AU - Wang, Jianxin

AU - Cao, Yixin

PY - 2016/1/1

Y1 - 2016/1/1

N2 - ï¿½ Springer-Verlag GmbH Germany 2016. A vertex set X of a graph G is an association set if each component of G − X is a clique, or a dissociation set if each component of G − X is a single vertex or a single edge. Interestingly, G − X is then precisely a graph containing no induced P3’s or containing no P3’s, respectively. 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 is 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 this approach in O(mn + n2) time.

AB - ï¿½ Springer-Verlag GmbH Germany 2016. A vertex set X of a graph G is an association set if each component of G − X is a clique, or a dissociation set if each component of G − X is a single vertex or a single edge. Interestingly, G − X is then precisely a graph containing no induced P3’s or containing no P3’s, respectively. 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 is 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 this approach in O(mn + n2) time.

UR - http://www.scopus.com/inward/record.url?scp=84992730911&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-53536-3_2

DO - 10.1007/978-3-662-53536-3_2

M3 - Conference article published in proceeding or book

SN - 9783662535356

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 24

BT - Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Revised Selected Papers

PB - Springer Verlag

T2 - 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016

Y2 - 22 June 2016 through 24 June 2016

ER -