Edge dominating set

Figures (a)–(d) are examples of edge dominating sets (thick red lines).

Determining whether there is an edge dominating set of a given size for a given graph is an NP-complete problem (and therefore finding a minimum edge dominating set is an NP-hard problem).

Yannakakis & Gavril (1980) show that the problem is NP-complete even in the case of a bipartite graph with maximum degree 3, and also in the case of a planar graph with maximum degree 3.

Also the edge-weighted version of the problem can be approximated within factor 2, but the algorithm is considerably more complicated (Fujito & Nagamochi 2002; Parekh 2002).

Schmied & Viehmann proved that the Problem is UGC-hard to approximate to within any constant better than 3/2.