S
OLUTION
:
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
.
M
EASURE
:
Cardinality of the independent dominating set, i.e.,
|V'|
.
Bad News:
NPO PB-complete [
202
]. Not approximable within
for
any
[
149
].
Comment:
Also called
Minimum Maximal Independence Number
.
Transformation from S
HORTEST
P
ATH
WITH
F
ORBIDDEN
P
AIRS
.
Variation in which the degree of
G
is bounded by a constant
B
is
A
PX
-complete [
200
].
Approximable within 5 for unit disk graphs [
268
].
.
such
that for all
there is a
for which
,
and such that no two vertices in
V'
are joined by an edge in
E
.
for
any
[
149
].