- INSTANCE: Graph .
- SOLUTION:
A partition of
*V*into disjoint sets such that each is a domatinating set of*G*. - MEASURE:
Cardinality of the partition, i.e., the number of disjoint subsets
.

*Good News:*Approximable within [155].*Bad News:*Not approximable within , for any , unless [155].*Comment:*The problem is also approximable within , where is the maximum degree, and is not approximable within , for any under the same hypothesis. The bad news also hold for split graphs and bipartite graphs. The problem is approximable within 4 on circular-arc graphs [371].*Garey and Johnson:*GT3