- INSTANCE: Graph .
- SOLUTION:
An edge dominating set for
*G*, i.e., a subset such that for all there is an such that and are adjacent. - MEASURE:
Cardinality of the edge dominating set, i.e., .

*Good News:*Approximable within 2 (any maximal matching).*Comment:*Admits a PTAS for planar graphs [53] and for -precision unit disk graphs [264].*Garey and Johnson:*GT2