Algorithms and Computational Complexity
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.
There is a simple polynomial-time approximation algorithm with approximation factor 2: find any maximal matching. A maximal matching is an edge dominating set; furthermore, a maximal matching M can be at worst 2 times as large as a smallest maximal matching, and a smallest maximal matching has the same size as the smallest edge dominating set.
Also the edge-weighted version of the problem can be approximated within factor 2, but the algorithm is considerably more complicated (Fujito & Nagamochi 2002).
Chlebík & Chlebíková (2006) show that finding a better than (7/6)-approximation is NP-hard.
Read more about this topic: Edge Dominating Set
Famous quotes containing the word complexity:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)