We prove that the edge dominating set problem for graphs is $NP$-complete even when restricted to planar or bipartite graphs of maximum degree 3. We show as a corollary that the minimum maximal matching and the achromatic number problems are $NP$-complete. A new linear time algorithm for finding minimum independent edge dominating sets in trees is described, based on an observed relationship between edge dominating sets and independent sets in total graphs.
No takes yet. Share an insight, caveat, or question.
Yannakakis et al. (1980) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: