Groupe d’études et de recherche en analyse des décisions

# Price of independence for the dominating set problem

## Eglantine Camby

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