![Dominating-set](https://upload.wikimedia.org/wikipedia/commons/e/e1/Dominating-set.svg)
In
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 conne ...
, a dominating set for a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
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 problem concerns testing whether for a given graph and input ; it is a classical
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 tryi ...
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
. Therefore it is believed that there may be no
efficient algorithm
In computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. An algorithm must be analyzed to determine its resource usage, and the efficiency of an algo ...
that can compute for all graphs . However, there are efficient
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 ...
s, as well as efficient exact algorithms for certain graph classes.
Dominating sets are of practical interest in several areas. In
wireless networking
A wireless network is a computer network that uses wireless data connections between network nodes.
Wireless networking is a method by which homes, telecommunications networks and business installations avoid the costly process of introducing c ...
, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in
document summarization
Automatic summarization is the process of shortening a set of data computationally, to create a subset (a Abstract (summary), summary) that represents the most important or relevant information within the original content. Artificial intelligence ...
, and in designing secure systems for
electrical grids.
Formal definition
Given an undirected graph , a
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of vertices
is called a dominating set if for every vertex
, there is a vertex
such that
.
Every graph has at least one dominating set: if
the set of all vertices, then by definition ''D'' is a dominating set, since there is no vertex
. A more interesting challenge is to find small dominating sets. The domination number of is defined as:
.
Variants
A
connected dominating set is a dominating set that is also
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
. If ''S'' is a connected dominating set, one can form a
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
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 (or strongly-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. That is: for every vertex
, there is a vertex
such that
. 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 strong domination number of is defined as:
; obviously,
.
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 strongly-dominating set. Therefore, the smallest size of an edge-dominating set is at least
.
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 ''k''-dominating set is a set of vertices such that each vertex not in the set has at least ''k'' neighbors in the set (a standard dominating set is a 1-dominating set). Similarly, a ''k''-tuple dominating set is a set of vertices such that each vertex in the graph has at least ''k'' neighbors in the set (a total dominating set is a 1-tuple dominating set). An -approximation of a minimum ''k''-tuple dominating set can be found in polynomial time. Every graph admits a ''k''-dominating set (for example, the set of all vertices); but only graphs with minimum degree admit a ''k''-tuple dominating set. However, even if the graph admits ''k''-tuple dominating set, a minimum ''k''-tuple dominating set can be nearly ''k'' times as large as a minimum ''k''-dominating set for the same graph; An -approximation of a minimum ''k''-dominating set can be found in polynomial time as well.
A star-dominating set is a
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
''D'' of ''V'' such that, for every vertex ''v'' in ''V'', the
star
A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...
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.
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 In graph theory, an eternal dominating set for a graph ''G'' = (''V'', ''E'') is a subset ''D'' of ''V'' such that ''D'' is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex ...
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''.
Dominating and independent sets
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
In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is max ...
, so any maximal independent set in a graph is necessarily also a minimal dominating set.
Domination ''by'' independent sets
A dominating set may or may not be an independent set. For example, figures (a) and (b) above show independent dominating sets, while figure (c) illustrates a dominating set that is not an independent set.
The independent domination number of a graph is the size of the smallest dominating set that is an independent set. Equivalently, it is the size of the smallest maximal independent set. The minimum in is taken over less elements (only the independent sets are considered), so for all graphs .
The inequality can be strict - there are graphs for which . For example, let be the ''double star graph'' consisting of vertices , where . The edges of are defined as follows: each is adjacent to , is adjacent to , and is adjacent to each . Then since is a smallest dominating set. If , then since is a smallest dominating set that is also independent (it is a smallest maximal independent set).
There are graph families in which , that is, every minimum maximal independent set is a minimum dominating set. For example, if is a
claw-free graph
In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.
A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...
.
A graph is called a domination-perfect graph if in every
induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
of . Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graphs is also domination-perfect.
For any graph , 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 ...
is claw-free, and hence a minimum maximal independent set in is also a minimum dominating set in . An independent set in corresponds to a
matching in , and a dominating set in corresponds to an
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 ...
in . Therefore a
minimum 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.
Definit ...
has the same size as a minimum edge dominating set.
Domination ''of'' independent sets
The independence domination number of a graph is the maximum, over all independent sets of , of the smallest set dominating .
Dominating subsets of vertices requires potentially less vertices than dominating all vertices, so for all graphs .
The inequality can be strict - there are graphs for which . For example, for some integer , let be a graph in which the vertices are the rows and columns of an -by- board, and two such vertices are connected if and only if they intersect. The only independent sets are sets of only rows or sets of only columns, and each of them can be dominated by a single vertex (a column or a row), so . However, to dominate all vertices we need at least one row and one column, so . Moreover, the ratio between can be arbitrarily large. For example, if the vertices of are all the subsets of squares of an -by- board, then still , but .
The bi-independent domination number of a graph is the maximum, over all independent sets of , of the smallest independent set dominating . The following relations hold for any graph :
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
Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing ...
proved the
set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the un ...
to be
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 tryi ...
. 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
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 tryi ...
as well.
Algorithms and computational complexity
The set cover problem is a well-known
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 – the decision version of set covering was one of
Karp's 21 NP-complete problems
In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the b ...
. There exist a pair of polynomial-time
L-reduction In computer science, particularly the study of approximation algorithms, an
L-reduction ("''linear reduction''") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preser ...
s between the minimum dominating set problem and the
set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the un ...
. 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
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
: for any α, a polynomial-time algorithm for minimum dominating sets would provide a polynomial-time algorithm for the set cover problem and vice versa. Both problems are in fact
Log-APX-complete.
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
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used abov ...
.
L-reductions
The following two reductions show that the minimum dominating set problem and the
set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the un ...
are equivalent under
L-reduction In computer science, particularly the study of approximation algorithms, an
L-reduction ("''linear reduction''") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preser ...
s: 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
The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the universe. Acc ...
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.
![Dominating-set-2](https://upload.wikimedia.org/wikipedia/commons/5/51/Dominating-set-2.svg)
::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
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by .
A split graph may have m ...
: is a
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
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 .
![Dominating-set-reduction](https://upload.wikimedia.org/wikipedia/commons/2/2c/Dominating-set-reduction.svg)
::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,
, where is number of nodes and is number of edges in given undirected graph. For fixed Δ, this qualifies as a dominating set for
APX
In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor ap ...
membership; in fact, it is APX-complete.
The problem admits a
polynomial-time approximation scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an insta ...
(PTAS) for special cases such as
unit disk graph
In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corr ...
s and
planar graphs. A minimum dominating set can be found in linear time in
series–parallel graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Definition and t ...
s.
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 "> and used in many reductions to show intractability of other problems. In particular, the problem is not
fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
in the sense that no algorithm with running time for any function exists unless the W-hierarchy collapses to FPT=W
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
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
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 graph
In graph theory, a branch of mathematics, a -biclique-free graph is a graph that has no -vertex complete bipartite graph as a subgraph. A family of graphs is biclique-free if there exists a number such that the graphs in the family are all -bic ...
s, 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.
See also
*
Vizing's conjecture
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs.
This conjecture was first stated by , and states that, if denotes the minimum number of vertices in a dominating set for ...
- relates the domination number of a
cartesian product of graphs Cartesian means of or relating to the French philosopher René Descartes—from his Latinized name ''Cartesius''. It may refer to:
Mathematics
* Cartesian closed category, a closed category in category theory
*Cartesian coordinate system, moder ...
to the domination number of its factors.
*
Set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the un ...
*
Bondage number
*
Nonblocker - the complement of a dominating set.
Notes
References
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*, p. 190, problem GT2.
*.
*.
*.
*
*
*.
*.
*.
*.
Further reading
*.
*.
*.
*.
*.
{{Authority control
Graph theory objects
NP-complete problems
Computational problems in graph theory