On independence domination

Wing Kai Hon, Ton Kloks, Hsiang Hsuan Liu, Sheung Hung Poon, Yue Li Wang

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)


Let G be a graph. The independence-domination number γi (G) is the maximum over all independent sets I in G of the minimal number of vertices needed to dominate I. In this paper we investigate the computational complexity of γi (G) for graphs in several graph classes related to cographs. We present an exact exponential algorithm. We show that there is a polynomial-time algorithm to compute a maximum independent set in the Cartesian product of two cographs. We prove that independence domination is NP-hard for planar graphs and we present a PTAS.

Original languageEnglish
Title of host publicationFundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings
Number of pages12
Publication statusPublished - 2013
Externally publishedYes
Event19th International Symposium on Fundamentals of Computation Theory, FCT 2013 - Liverpool, United Kingdom
Duration: 19 Aug 201321 Aug 2013

Publication series

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


Conference19th International Symposium on Fundamentals of Computation Theory, FCT 2013
Country/TerritoryUnited Kingdom


  • Cograph
  • Distance-hereditary graph
  • Domination
  • Exact algorithm
  • Independence domination
  • Permutation graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On independence domination'. Together they form a unique fingerprint.

Cite this