Edge dominating set


In graph theory, an edge dominating set for a graph G = is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known as a line dominating set. Figures – are examples of edge dominating sets.
A minimum edge dominating set is a smallest edge dominating set. Figures and are examples of minimum edge dominating sets.

Properties

An edge dominating set for G is a dominating set for its line graph L and vice versa.
Any maximal matching is always an edge dominating set. Figures and are examples of maximal matchings.
Furthermore, the size of a minimum edge dominating set equals the size of a minimum maximal matching. A minimum maximal matching is a minimum edge dominating set; Figure is an example of a minimum maximal matching. A minimum edge dominating set is not necessarily a minimum maximal matching, as illustrated in Figure ; however, given a minimum edge dominating set D, it is easy to find a minimum maximal matching with |D| edges.

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. 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 .
show that finding a better than -approximation is NP-hard.