Edge dominating set
In graph theory, an edge dominating set for a graph G = (V, E) 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 (a)–(d) are examples of edge dominating sets (thick red lines).
A minimum edge dominating set is a smallest edge dominating set. Figures (a) and (b) are examples of minimum edge dominating sets (it can be checked that there is no edge dominating set of size 2 for this graph).
Any maximal matching is always an edge dominating set. Figures (b) and (d) 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 (b) is an example of a minimum maximal matching. A minimum edge dominating set is not necessarily a minimum maximal matching, as illustrated in Figure (a); however, given a minimum edge dominating set D, it is easy to find a minimum maximal matching with |D| edges (see, e.g., Yannakakis & Gavril 1980).
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.
- Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer.
- Minimum edge dominating set (optimisation version) is the problem GT3 in Appendix B (page 370).
- Minimum maximal matching (optimisation version) is the problem GT10 in Appendix B (page 374).
- Chlebík, Miroslav; Chlebíková, Janka (2006), "Approximation hardness of edge dominating set problems", Journal of Combinatorial Optimization, 11 (3): 279–290, doi:10.1007/s10878-006-7908-0.
- Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5.
- Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix A1.1.
- Minimum maximal matching (decision version) is the problem GT10 in Appendix A1.1.
- Yannakakis, Mihalis; Gavril, Fanica (1980), "Edge dominating sets in graphs", SIAM Journal on Applied Mathematics, 38 (3): 364–372, doi:10.1137/0138030, JSTOR 2100648.
- Fujito, Toshihiro; Nagamochi, Hiroshi (2002), "A 2-approximation algorithm for the minimum weight edge dominating set problem", Discrete Applied Mathematics, 118 (3): 199–207, doi:10.1016/S0166-218X(00)00383-8.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "A compendium of NP optimization problems":