Group for Research in Decision Analysis

G-2017-83

Price of independence for the dominating set problem

Let \(\gamma(G)\) and \(\iota(G)\) be the domination and independent domination numbers of a graph \(G\), respectively. In this paper, we define the Price of Independence of a graph \(G\) as the ratio \(\frac{\iota(G)}{\gamma(G)}\). Firstly, we bound the Price of Independence by values depending on the number of vertices. Secondly, we consider the question of computing the Price of Independence of a given graph. Unfortunately, the decision version of this question is \(\Theta_2^p\)-complete. The class \(\Theta_2^p\) is the class of decision problems solvable in polynomial time, for which we can make \(O(\log(n))\) queries to an NP-oracle. Finally, we restore the true characterization of domination perfect gaphs, i.e. graphs whose the Price of Independence is always \(1\) for all induced subgraphs, and we propose a conjecture on futher problems.

, 13 pages