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)