Dominating set

Three dominating sets of the same graph (in red). The domination number of this graph is 2: (b) and (c) show that there is a dominating set with 2 vertices, and there is no dominating set with only 1 vertex.

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

The dominating set problem concerns testing whether Template:Math for a given graph Template:Mvar and input Template:Mvar; it is a classical NP-complete decision problem in computational complexity theory.Template:Sfnp Therefore it is believed that there may be no efficient algorithm that can compute Template:Math for all graphs Template:Math. 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.

Formal definition

Given an undirected graph Template:Math, a subset of vertices $D\subseteq V$ is called a dominating set if for every vertex $u\in V\setminus D$, there is a vertex $v\in D$ such that $\{u,v\}\in E$.

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 Template:Math 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.Template:Sfnp

Algorithms and computational complexity

The set cover problem is a well-known NP-hard problem – the decision version of set covering was one of Karp's 21 NP-complete problems. There exist a pair of polynomial-time L-reductions between the minimum dominating set problem and the set cover problem.Template:Sfnp These reductions (see below) show that an efficient algorithm for the minimum dominating set problem would provide an efficient algorithm for the set cover problem, and vice versa. Moreover, the reductions preserve the approximation ratio: for any α, a polynomial-time Template:Nowrap algorithm for minimum dominating sets would provide a polynomial-time Template:Nowrap algorithm for the set cover problem and vice versa. Both problems are in fact Log-APX-complete.Template:Sfnp

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 Template:Math approximation of a minimum dominating set, and no polynomial time algorithm can achieve an approximation factor better than Template:Math for some Template:Math unless P = NP.Template:Sfnp

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.Template:Sfnp

From dominating set to set covering

Given a graph Template:Math with Template:Math construct a set cover instance Template:Math as follows: the universe Template:Mvar is Template:Mvar, and the family of subsets is Template:Math such that Template:Mvar consists of the vertex Template:Mvar and all vertices adjacent to Template:Mvar in Template:Mvar.

Now if Template:Mvar is a dominating set for Template:Mvar, then Template:Math is a feasible solution of the set cover problem, with Template:Math. Conversely, if Template:Math is a feasible solution of the set cover problem, then Template:Mvar is a dominating set for Template:Mvar, with Template:Math.

Hence the size of a minimum dominating set for Template:Mvar equals the size of a minimum set cover for Template:Math. 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 Template:Nowrap algorithm for set covering provides an efficient Template:Nowrap algorithm for minimum dominating sets.

For example, given the graph Template:Mvar shown on the right, we construct a set cover instance with the universe Template:Math and the subsets Template:Math Template:Math Template:Math Template:Math Template:Math and Template:Math In this example, Template:Math is a dominating set for Template:Mvar – this corresponds to the set cover Template:Math For example, the vertex Template:Math is dominated by the vertex Template:Math, and the element Template:Math is contained in the set Template:Math.

From set covering to dominating set

Let Template:Math be an instance of the set cover problem with the universe Template:Mvar and the family of subsets Template:Math we assume that Template:Mvar and the index set Template:Mvar are disjoint. Construct a graph Template:Math as follows: the set of vertices is Template:Math, there is an edge Template:Math between each pair Template:Math, and there is also an edge Template:Math for each Template:Math and Template:Math. That is, Template:Mvar is a split graph: Template:Mvar is a clique and Template:Mvar is an independent set.

Now if Template:Math is a feasible solution of the set cover problem for some subset Template:Math, then Template:Mvar is a dominating set for Template:Mvar, with Template:Math: First, for each Template:Math there is an Template:Math such that Template:Math, and by construction, Template:Mvar and Template:Mvar are adjacent in Template:Mvar; hence Template:Mvar is dominated by Template:Mvar. Second, since Template:Mvar must be nonempty, each Template:Math is adjacent to a vertex in Template:Mvar.

Conversely, let Template:Mvar be a dominating set for Template:Mvar. Then it is possible to construct another dominating set Template:Mvar such that Template:Math and Template:Math: simply replace each Template:Math by a neighbour Template:Math of Template:Mvar. Then Template:Math is a feasible solution of the set cover problem, with Template:Math.

The illustration on the right show the construction for Template:Math Template:Math Template:Math Template:Math and Template:Math

In this example, Template:Math is a set cover; this corresponds to the dominating set Template:Math

Template:Math is another dominating set for the graph Template:Mvar. Given Template:Mvar, we can construct a dominating set Template:Math which is not larger than Template:Mvar and which is a subset of Template:Mvar. The dominating set Template:Mvar corresponds to the set cover Template:Math

Special cases

If the graph has maximum degree Δ, then the greedy approximation algorithm finds an Template:Math-approximation of a minimum dominating set. Also, let Template:Mvar be the cardinality of dominating set obtained using greedy approximation then following relation holds, $d_g\le N+1-\sqrt{2M+1}$, where Template:Mvar is number of nodes and Template:Mvar is number of edges in given undirected graph.Template:Sfnp For fixed Δ, this qualifies as a dominating set for APX membership; in fact, it is APX-complete.Template:Sfnp

The problem admits a polynomial-time approximation scheme (PTAS) for special cases such as unit disk graphs and planar graphs.Template:Sfnp A minimum dominating set can be found in linear time in series–parallel graphs.Template:Sfnp

Exact algorithms

A minimum dominating set of an Template:Mvar-vertex graph can be found in time Template:Math by inspecting all vertex subsets. Template:Harvtxt show how to find a minimum dominating set in time Template:Math and exponential space, and in time Template:Math and polynomial space. A faster algorithm, using Template:Math time was found by Template:Harvtxt, 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 Template:Math and all such sets can be listed in time Template:Math.Template:Sfnp

Parameterized complexity

Finding a dominating set of size Template:Mvar plays a central role in the theory of parameterized complexity. It is the most well-known problem complete for the class 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 Template:Math for any function Template:Mvar 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 Template:Mvar,Template:Sfnp and running times that are exponential in Template:Radic and cubic in Template:Mvar may be obtained by applying dynamic programming to a branch-decomposition of the kernel.Template:Sfnp 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.Template:Sfnp

The complementary set to a dominating set, a nonblocker, can be found by a fixed-parameter algorithm on any graph.Template:Sfnp

Variants

An independent dominating set is a dominating set that is also an independent set, or equivalently, a maximal independent set. The independent domination number $i(G)$ is the minimum size of an independent dominating set of Template:Mvar. Since the minimum is taken over fewer sets, $\gamma (G)\le i(G)$ for all graphs Template:Mvar, and the inequality can be strict. Equality holds for claw-free graphs;Template:Sfnp since every line graph is claw-free, it follows that the minimum maximal matching and the minimum edge dominating set of any graph have the same size.

An independence dominating set of a graph $G$ is a set that dominates every independent set of $G$. The independence domination number $i\gamma (G)$ is the maximum, over all independent sets $A$ of $G$, of the smallest set dominating $A$.Template:Sfnp Dominating only independent sets requires potentially fewer vertices than dominating all vertices, so $i\gamma (G)\le \gamma (G)$ for all graphs $G$, and the ratio $\gamma (G)/i\gamma (G)$ can be arbitrarily large.Template:Sfnp

A connected dominating set is a dominating set that is also connected. If $S$ is a connected dominating set, one can form a spanning tree of $G$ in which $S$ forms the set of non-leaf vertices of the tree; conversely, if $T$ is any spanning tree in a graph with more than two vertices, the non-leaf vertices of $T$ form a connected dominating set. Therefore, finding minimum connected dominating sets is equivalent to finding spanning trees with the maximum possible number of leaves.

A total dominating set is a set of vertices such that all vertices in the graph, including the vertices in the dominating set themselves, have a neighbor in the dominating set.Template:Sfnp That is: for every vertex $u\in V$, there is a vertex $v\in D$ such that $\{u,v\}\in E$. Figure (c) above shows a dominating set that is a connected dominating set and a total dominating set; the examples in figures (a) and (b) are neither. In contrast to a simple dominating set, a total dominating set may not exist. For example, a graph with one or more vertices and no edges does not have a total dominating set. The total domination number ${\gamma }^{\text{total}}(G)$ is defined as the minimum size of a total dominating set of Template:Math; obviously, ${\gamma }^{\text{total}}(G)\ge \gamma (G)$.

A dominating edge-set is a set of edges (vertex pairs) whose union is a dominating set; such a set may not exist (for example, a graph with one or more vertices and no edges does not have it). If it exists, then the union of all its edges is a total dominating set. Therefore, the smallest size of an edge-dominating set is at least ${\gamma }^{\text{total}}(G)/2$.

In contrast, an edge-dominating set is a set $D$ of edges, such that every edge not in $D$ is adjacent to at least one edge in $D$; such a set always exists (for example, the set of all edges is an edge-dominating set).

A Template:Mvar-dominating set is a set of vertices such that each vertex not in the set has at least Template:Mvar neighbors in the set (a standard dominating set is a 1-dominating set). Similarly, a Template:Mvar-tuple dominating set is a set of vertices such that each vertex in the graph has at least Template:Mvar neighbors in the set (a total dominating set is a 1-tuple dominating set). An Template:Math-approximation of a minimum Template:Mvar-tuple dominating set can be found in polynomial time.Template:Sfnp Every graph admits a Template:Mvar-dominating set (for example, the set of all vertices); but only graphs with minimum degree Template:Math admit a Template:Mvar-tuple dominating set. However, even if the graph admits Template:Mvar-tuple dominating set, a minimum Template:Mvar-tuple dominating set can be nearly Template:Mvar times as large as a minimum Template:Mvar-dominating set for the same graph;Template:Sfnp An Template:Math-approximation of a minimum Template:Mvar-dominating set can be found in polynomial time as well.

A fractional dominating set is defined from a fractional dominating function, a function $f:V(G)\to [0,1]$ such that for every vertex $v\in V$, the sum of $f$ over the closed neighborhood $N[v]$ is at least 1.Template:Sfnp The fractional domination number ${\gamma }_f(G)$ is the minimum total weight (sum of all vertex values) of such a function, and satisfies ${\gamma }_f(G)\le \gamma (G)$. For a $k$-regular graph with $n$ vertices ($k\ge 1$), the fractional domination number equals $n/(k+1)$.

A star-dominating set is a subset $D$ of $V$ such that, for every vertex $v$ in $V$, the star of $v$ (the set of edges adjacent to $v$) intersects the star of some vertex in $D$. Clearly, if $G$ has isolated vertices then it has no star-dominating sets (since the star of isolated vertices is empty). If $G$ has no isolated vertices, then every dominating set is a star-dominating set and vice versa. The distinction between star-domination and usual domination is more substantial when their fractional variants are considered.Template:Sfnp

A domatic partition is a partition of the vertices into disjoint dominating sets. The domatic number is the maximum size of a domatic partition.

An eternal dominating set is a dynamic version of domination in which a vertex $v$ in dominating set $D$ is chosen and replaced with a neighbor $u$ ($u$ is not in $D$) such that the modified $D$ is also a dominating set and this process can be repeated over any infinite sequence of choices of vertices $v$.

An efficient dominating set (also called an e.d. set or independent perfect dominating setTemplate:Sfnp) is a dominating set with the additional property that every vertex in the graph is dominated by exactly one vertex in the set.Template:Sfnp

A Roman dominating set is defined through a Roman dominating function, which assigns to each vertex a value from $\{0,1,2\}$ such that every vertex assigned 0 is adjacent to at least one vertex assigned 2. The Roman domination number ${\gamma }_R(G)$ is the minimum sum of all vertex values over all such functions. The concept is inspired by a defensive strategy of the Roman Empire, where vertices represent cities and values represent stationed legions. For any graph $G$, $\gamma (G)\le {\gamma }_R(G)\le 2\gamma (G)$, with the lower bound achieved only by the empty graph.Template:Sfnp

A global dominating set is a dominating set of a graph $G$ that is also a dominating set of the complement graph $\bar{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\left(\bar{G}\right)$ and $\gamma (G)\le {\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}$.Template:Sfnp

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.Template:Sfnp The certified domination number ${\gamma }_{\text{cer}}(G)$ is the minimum size of a certified dominating set. Clearly, ${\gamma }_{\text{cer}}(G)\ge \gamma (G)$, and equality holds whenever the graph has no weak support vertex (in particular, when $\delta (G)\ge 2$). For a connected graph, ${\gamma }_{\text{cer}}(G)\le 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.Template:Sfnp 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,Template:Sfnp
• secure dominating set,Template:Sfnp
• triple connected dominating set,Template:Sfnp
• signed dominating set,Template:Sfnp
• minus dominating set,Template:Sfnp and
• friendly dominating set.Template:Sfnp

See also

• Vizing's conjecture – relates the domination number of a cartesian product of graphs to the domination number of its factors
• Set cover problem
• Bondage number
• Nonblocker – the complement of a dominating set
• Universal vertex – a single-vertex dominating set

References

• Template:Cite journal
• Template:Citation.
• Template:Citation.
• Template:Cite conference
• Template:Cite conference
• Template:Cite journal
• Template:Cite journal
• Template:Citation.
• Template:Citation.
• Template:Cite journal
• Template:Cite journal
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Garey-Johnson, p. 190, problem GT2.
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Citation.
• Template:Cite book
• Template:Citation.
• Template:Citation.
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Citation
• Template:Citation
• Template:Citation.
• Template:Cite journal
• Template:Citation.
• Template:Citation.
• Template:Citation.

Further reading

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.