graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, 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).

Properties

An edge dominating set for ''G'' is a

dominating set In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The dominating set ...

for its

line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

''L''(''G'') and vice versa. Any

maximal matching In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem. Definiti ...

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., ).

Algorithms and computational complexity

Determining whether there is an edge dominating set of a given size for a given graph is an

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

problem (and therefore finding a minimum edge dominating set is an

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

problem). show that the problem is NP-complete even in the case of a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

with maximum degree 3, and also in the case of a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

with maximum degree 3. There is a simple polynomial-time

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

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 (7/6)-approximation is NP-hard. Schmied & Viehmann proved that the Problem is UGC-hard to approximate to within any constant better than 3/2.

References

*. ::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). * . *. ::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. * . * . * {{citation , last1=Parekh , first1=Ojas , contribution=Edge dominating and hypomatchable sets , title=Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms , year=2002 , pages=287–291 , contribution-url=http://dl.acm.org/citation.cfm?id=545381.545419 . *Richard Schmied & Claus Viehmann (2012), "Approximating edge dominating set in dense graphs", Theor. Comput. Sci. 414(1), pp. 92-99.

External links

* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski,

Gerhard Woeginger Gerhard J. Woeginger (31 May 1964 – 1 April 2022) was an Austrian mathematician and computer scientist who worked in Germany as a professor at RWTH Aachen University, where he chaired the algorithms and complexity group in the department of co ...

(2000)
"A compendium of NP optimization problems"
:

:

NP-complete problems Computational problems in graph theory