G-2017-83
Price of independence for the dominating set problem
référence BibTeX
Let γ(G)
and ι(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 ι(G)γ(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 Θp2
-complete. The class Θp2
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.
Paru en octobre 2017 , 13 pages
Document
G1783.pdf (380 Ko)