Retour

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.

, 13 pages

Document

G1783.pdf (380 Ko)