On Independence Domination

摘要

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.