Next: MINIMUM EDGE DOMINATING SET Up: Covering and Partitioning Previous: MINIMUM VERTEX COVER Index

### MINIMUM DOMINATING SET

- INSTANCE: Graph .

- 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., |V'|.

- Good News: Approximable within since the problem is a special instance of MINIMUM SET COVER [261].

- Bad News: Not approximable within , for some c > 0 [401].

- 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].

- Garey and Johnson: GT2

Next: MINIMUM EDGE DOMINATING SET Up: Covering and Partitioning Previous: MINIMUM VERTEX COVER Index