Next: MINIMUM GRAPH COLORING Up: Covering and Partitioning Previous: MINIMUM EDGE DOMINATING SET Index

### MINIMUM INDEPENDENT DOMINATING SET

- INSTANCE: Graph .

- SOLUTION: An independent dominating set for G, i.e., a subset such that for all there is a for which , and such that no two vertices in V' are joined by an edge in E.

- MEASURE: Cardinality of the independent dominating set, i.e., |V'|.

- Bad News: Not approximable within for any [207].

- Comment: Also called Minimum Maximal Independent Set. The problem is also NPO PB-complete [269]. Variation in which the degree of G is bounded by a constant B is trivially approximable within B, and is APX-complete [267]. Approximable within 5 for unit disk graphs [350]. The maximization variation in which the set for some fixed k constrains how the independent set can dominate the remaining vertices is approximable within and is not approximable within for any unless [213].

- Garey and Johnson: GT2

Next: MINIMUM GRAPH COLORING Up: Covering and Partitioning Previous: MINIMUM EDGE DOMINATING SET Index