SOLUTION:
A dominating set for G, i.e., a subset
such that for all
there is a
for which .
MEASURE:
Cardinality of the dominating set, i.e., .
Good News:
Approximable within
since the problem is a special instance of
MINIMUM SET COVER [276].
Bad News:
Not approximable within ,
for some c > 0 [423].
Comment:
Equivalent to MINIMUM SET COVER under L-reduction [282] and
[63].
See MINIMUM SET COVER for more comments.
Not approximable within
for any
,
unless NP
[153].
Complete for the class of -approximable problems [305].
Admits a PTAS for planar graphs [53]
and for unit disk graphs [264].
Variation in which the degree of G is bounded by a constant B is
APX-complete for
[393] and is approximable within
by reduction to MINIMUM SET COVER.
The bad news hold also for bipartite graphs and split graphs (observation).
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
[208].