- INSTANCE: Graph .
- SOLUTION:
An independent dominating set for
*G*, i.e., a subset such that for all there is a for which , and such that no two vertices in*V'*are joined by an edge in*E*. - MEASURE:
Cardinality of the independent dominating set, i.e., .

*Bad News:*Not approximable within for any [220].*Comment:*Also called*Minimum Maximal Independent Set*. Under the assumption that , the problem is not approximable within , for any . The problem is also NPO PB-complete [284]. Variation in which the degree of*G*is bounded by a constant*B*is trivially approximable within*B*, and is APX-complete [282]. Approximable within 5 for unit disk graphs [370]. Not approximable within even for circle graphs and bipartite graphs [132]. The maximization variation in which the set for some fixed*k*constrains how the independent set can dominate the remaining vertices is approximable within and is not approximable within for any unless [229].*Garey and Johnson:*GT2