Also called Minimum Maximal Independent Set.
Under the assumption that
the problem is not approximable within
The problem is also NPO PB-complete .
Variation in which the degree of G is bounded by a constant B is
trivially approximable within B, and is APX-complete .
Approximable within 5 for unit disk graphs .
Not approximable within
circle graphs and bipartite graphs .
The maximization variation in which the set
fixed k constrains how the independent set can dominate the
remaining vertices is approximable within
is not approximable within