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., .
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].