Approximate association via dissociation

Jie You, Jianxin Wang, Yixin Cao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

� 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.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Revised Selected Papers
PublisherSpringer Verlag
Pages13-24
Number of pages12
ISBN (Print)9783662535356
DOIs
Publication statusPublished - 1 Jan 2016
Event42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016 - Istanbul, Turkey
Duration: 22 Jun 201624 Jun 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9941 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016
CountryTurkey
CityIstanbul
Period22/06/1624/06/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this