.
such that for all
there is a
for which
.
since the problem is a special instance of
M
INIMUM
S
ET
C
OVER
[
194
].
for any
,
unless NP
[
103
].
If it is NP-hard to approximate within
, then it is complete
for the class of
-approximable problems [
217
].
Admits a PTAS for planar graphs [
33
]
and for unit disk graphs [
181
].
Variation in which the degree of
G
is bounded by a constant
B
is
A
PX
-complete [
284
] and is approximable within
by reduction to M
INIMUM
S
ET
C
OVER
.
If the dominating set is restricted to be connected the problem
is approximable within
where
is the maximum degree,
and within
for the vertex weighted version
[
143
].
Viggo Kann