A dominating set for G, i.e., a subset
such that for all
there is a
for which .
Cardinality of the dominating set, i.e., .
since the problem is a special instance of
MINIMUM SET COVER .
Not approximable within ,
for some c > 0 .
Equivalent to MINIMUM SET COVER under L-reduction  and
See MINIMUM SET COVER for more comments.
Not approximable within
Complete for the class of -approximable problems .
Admits a PTAS for planar graphs 
and for unit disk graphs .
Variation in which the degree of G is bounded by a constant B is
 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
is the maximum degree,
for the vertex weighted version