Next: MINIMUM INDEPENDENT DOMINATING SET Up: Covering and Partitioning Previous: MINIMUM DOMINATING SET Index

### MINIMUM EDGE DOMINATING SET

- INSTANCE: Graph .

- SOLUTION: An edge dominating set for G, i.e., a subset such that for all there is an such that e1 and e2 are adjacent.

- MEASURE: Cardinality of the edge dominating set, i.e., |E'|.

- Good News: Approximable within 2 (any maximal matching).

- Comment: Admits a PTAS for planar graphs [50] and for -precision unit disk graphs [249].

- Garey and Johnson: GT2