MINIMUM EDGE DOMINATING SET

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: An edge dominating set for G, i.e., a subset $E'\subseteq E$ such that for all $e_1\in E-E'$ there is an $e_2\in E'$ such that $e_1$ and $e_2$ are adjacent.
• MEASURE: Cardinality of the edge dominating set, i.e., $\vert E'\vert$.

  
  

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