Comment:
Equivalent to MINIMUM SET COVER under L-reduction [267] and
[58].
See MINIMUM SET COVER for more comments.
Not approximable within
for any
,
unless NP
[142].
If it is NP-hard to approximate within
,
then it is complete
for the class of
-approximable problems [290].
Admits a PTAS for planar graphs [50]
and for unit disk graphs [249].
Variation in which the degree of G is bounded by a constant B is
APX-complete [371] and is approximable within
by reduction to MINIMUM SET COVER.
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
[195].
The problem MAXIMUM DOMATIC PARTITION, in which the graph should be
partitioned into a maximum number of dominating sets, is approximable
within 4 for circular-arc graphs [351].