G-2017-83
Price of independence for the dominating set problem
BibTeX reference
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.
Published October 2017 , 13 pages
Document
G1783.pdf (400 KB)