dominating set

In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The dominating set problem concerns testing whether for a given graph and input ; it is a classical NP-complete decision problem in computational complexity theory. Therefore it is believed that there may be no efficient algorithm that can compute for all graphs . However, there are efficient approximation algorithms, as well as efficient exact algorithms for certain graph classes. Dominating sets are of practical interest in several areas. In wireless networking, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in document summarization, and in designing secure systems for electrical grids. Dominating sets are closely related to independent sets: an independent set is also a dominating set if and only if it is a maximal independent set, so any maximal independent set in a graph is necessarily also a minimal dominating set.

In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The dominating set problem concerns testing whether for a given graph and input ; it is a classical NP-complete decision problem in computational complexity theory. Therefore it is believed that there may be no efficient algorithm that can compute for all graphs . However, there are efficient approximation algorithms, as well as efficient exact algorithms for certain graph classes. Dominating sets are of practical interest in several areas. In wireless networking, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in document summarization, and in designing secure systems for electrical grids. Dominating sets are closely related to independent sets: an independent set is also a dominating set if and only if it is a maximal independent set, so any maximal independent set in a graph is necessarily also a minimal dominating set. Every graph has at least one dominating set: if D=V= the set of all vertices, then by definition D is a dominating set, since there is no vertex u\in V\setminus D . A more interesting challenge is to find small dominating sets. The domination number of is defined as: \gamma(G) := \min \{|D| : D \text{ is a dominating set of } G \} .

History

The domination problem was studied from the 1950s onwards, but the rate of research on domination significantly increased in the mid-1970s. In 1972, Richard Karp proved the set cover problem to be NP-complete. This had immediate implications for the dominating set problem, as there are straightforward vertex to set and edge to non-disjoint-intersection bijections between the two problems. This proved the dominating set problem to be NP-complete as well. The approximability of set covering is also well understood: a logarithmic approximation factor can be found by using a simple greedy algorithm, and finding a sublogarithmic approximation factor is NP-hard. More specifically, the greedy algorithm provides a factor approximation of a minimum dominating set, and no polynomial time algorithm can achieve an approximation factor better than for some unless P = NP.

L-reductions

The following two reductions show that the minimum dominating set problem and the set cover problem are equivalent under L-reductions: given an instance of one problem, we can construct an equivalent instance of the other problem.

From dominating set to set covering

Given a graph with construct a set cover instance as follows: the universe is , and the family of subsets is such that consists of the vertex and all vertices adjacent to in . Now if is a dominating set for , then is a feasible solution of the set cover problem, with . Conversely, if is a feasible solution of the set cover problem, then is a dominating set for , with . Hence the size of a minimum dominating set for equals the size of a minimum set cover for . Furthermore, there is a simple algorithm that maps a dominating set to a set cover of the same size and vice versa. In particular, an efficient algorithm for set covering provides an efficient algorithm for minimum dominating sets. For example, given the graph shown on the right, we construct a set cover instance with the universe and the subsets and In this example, is a dominating set for – this corresponds to the set cover For example, the vertex is dominated by the vertex , and the element is contained in the set .

From set covering to dominating set

Let be an instance of the set cover problem with the universe and the family of subsets we assume that and the index set are disjoint. Construct a graph as follows: the set of vertices is , there is an edge between each pair , and there is also an edge for each and . That is, is a split graph: is a clique and is an independent set. Now if is a feasible solution of the set cover problem for some subset , then is a dominating set for , with : First, for each there is an such that , and by construction, and are adjacent in ; hence is dominated by . Second, since must be nonempty, each is adjacent to a vertex in . Conversely, let be a dominating set for . Then it is possible to construct another dominating set such that and : simply replace each by a neighbour of . Then is a feasible solution of the set cover problem, with . The illustration on the right show the construction for and In this example, is a set cover; this corresponds to the dominating set is another dominating set for the graph . Given , we can construct a dominating set which is not larger than and which is a subset of . The dominating set corresponds to the set cover

Special cases

If the graph has maximum degree Δ, then the greedy approximation algorithm finds an -approximation of a minimum dominating set. Also, let be the cardinality of dominating set obtained using greedy approximation then following relation holds, d_g \le N+1 - \sqrt{2M+1} , where is number of nodes and is number of edges in given undirected graph. For fixed Δ, this qualifies as a dominating set for APX membership; in fact, it is APX-complete. The problem admits a polynomial-time approximation scheme (PTAS) for special cases such as unit disk graphs and planar graphs. A minimum dominating set can be found in linear time in series–parallel graphs.

Exact algorithms

A minimum dominating set of an -vertex graph can be found in time by inspecting all vertex subsets. show how to find a minimum dominating set in time and exponential space, and in time and polynomial space. A faster algorithm, using time was found by , who also show that the number of minimum dominating sets can be computed in this time. The number of minimal dominating sets is at most and all such sets can be listed in time .

Parameterized complexity

Finding a dominating set of size plays a central role in the theory of parameterized complexity. It is the most well-known problem complete for the class [[W(2)|W[2] and used in many reductions to show intractability of other problems. In particular, the problem is not fixed-parameter tractable in the sense that no algorithm with running time for any function exists unless the W-hierarchy collapses to FPT=W[2]. On the other hand, if the input graph is planar, the problem remains NP-hard, but a fixed-parameter algorithm is known. In fact, the problem has a kernel of size linear in , and running times that are exponential in and cubic in may be obtained by applying dynamic programming to a branch-decomposition of the kernel. More generally, the dominating set problem and many variants of the problem are fixed-parameter tractable when parameterized by both the size of the dominating set and the size of the smallest forbidden complete bipartite subgraph; that is, the problem is FPT on biclique-free graphs, a very general class of sparse graphs that includes the planar graphs. The complementary set to a dominating set, a nonblocker, can be found by a fixed-parameter algorithm on any graph. A global dominating set is a dominating set of a graph G that is also a dominating set of the complement graph \overline{G} . The global domination number \gamma_g(G) is the minimum cardinality of a global dominating set. Equivalently, a dominating set S is a global dominating set if and only if for each vertex v \in V - S , there exists a vertex u \in S such that u is not adjacent to v . By definition, \gamma_g(G) = \gamma_g\big(\overline{G}\big) and \gamma(G) \leq \gamma_g(G) . For a graph G with p vertices, \gamma_g(G) = p if and only if G = K_p or G = \overline{K_p} . A certified dominating set is a dominating set in which every vertex in the set has either zero or at least two neighbours outside the set. The certified domination number \gamma_{\text{cer}}(G) is the minimum size of a certified dominating set. Clearly, \gamma_{\text{cer}}(G) \geq \gamma(G) , and equality holds whenever the graph has no weak support vertex (in particular, when \delta(G) \geq 2 ). For a connected graph, \gamma_{\text{cer}}(G) \leq 2\gamma(G) . A paired dominating set of a graph G = (V, E) is a dominating set S of vertices such that the induced subgraph G[S] contains at least one perfect matching. The paired domination number \gamma_p(G) is the minimum cardinality of a paired dominating set of G . The concept models a situation in which guards are placed at vertices of a graph to dominate (protect) all vertices, with the additional constraint that each guard is assigned another adjacent guard as a backup. Other variants include restrained dominating set, secure dominating set, triple connected dominating set, signed dominating set, minus dominating set, and friendly dominating set.

Further reading

. . . . .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374757470 under CC BY-SA 4.0; modifications have been made.