Approximate association via dissociation

Jie You, Jianxin Wang, Yixin Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)202-209
Number of pages8
JournalDiscrete Applied Mathematics
Volume219
DOIs
Publication statusPublished - 11 Mar 2017

Keywords

  • Association set (cluster vertex deletion)
  • Cluster graph
  • Dissociation set
  • Modular decomposition
  • Triangle-free graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this