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., |V'|.
Comment:
Also called Minimum Maximal Independent Set.
The problem is also NPO PB-complete [269].
Variation in which the degree of G is bounded by a constant B is
trivially approximable within B, and is
APX-complete [267].
Approximable within 5 for unit disk graphs [350].
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
[213].