GT3 M INIMUM E DGE D OMINATING S ET

       
• I NSTANCE : Graph .
• S OLUTION : An edge dominating set for G , i.e., a subset such that for all there is an such that and are adjacent.
• M EASURE : Cardinality of the edge dominating set, i.e., |E'| .

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