### 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)