View source for Dominating set

{{Short description|Subset of a graph's nodes such that all other nodes link to at least one}}
{{For|Dominator in control flow graphs|Dominator (graph theory)}}

[[File:Dominating-set.svg|frame|right|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 (discrete mathematics)|graph]] {{math|1=''G''}} is a subset {{math|1=''D''}} of its vertices, such that any vertex of {{math|1=''G''}} is in {{math|1=''D''}}, or has a neighbor in {{math|1=''D''}}. The '''domination number''' {{math|γ(''G'')}} is the number of vertices in a smallest dominating set for {{mvar|G}}.

The '''dominating set problem''' concerns testing whether {{math|γ(''G'') ≤ ''K''}} for a given graph {{mvar|G}} and input {{mvar|K}}; it is a classical [[NP-complete]] [[decision problem]] in [[computational complexity theory]].{{sfnp|Garey|Johnson|1979}} Therefore it is believed that there may be no [[polynomial-time algorithm|efficient algorithm]] that can compute {{math|γ(''G'')}} for all graphs {{math|1=''G''}}. However, there are efficient [[approximation algorithm]]s, 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 grid|electrical grids]].

== Formal definition ==
Given an undirected graph {{math|1=''G'' = (''V'', ''E'')}}, a [[subset]] of vertices <math>D\subseteq V</math> is called a '''dominating set''' if for every vertex <math>u\in V\setminus D</math>, there is a vertex <math>v\in D</math> such that <math>\{u,v\} \in E</math>.  

Every graph has at least one dominating set: if <math>D=V=</math> the set of all vertices, then by definition ''D'' is a dominating set, since there is no vertex <math>u\in V\setminus D</math>. A more interesting challenge is to find small dominating sets. The '''domination number''' of {{math|1=''G''}} is defined as:  <math>\gamma(G) := \min \{|D| : D \text{ is a dominating set of } G \}</math>.

== Variants ==

A '''[[connected dominating set]]''' is a dominating set that is also [[Connected (graph theory)|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''' (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.{{sfnp|West|2001|loc = Section 3.1}} That is: for every vertex <math>u\in V</math>, there is a vertex <math>v\in D</math> such that <math>\{u,v\} \in E</math>. 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 {{math|1=''G''}} is defined as:  <math>\gamma^{strong}(G) := \min \{|D| : D \text{ is a strongly-dominating set of } G \}</math>; obviously, <math>\gamma^{strong}(G) \geq \gamma(G)</math>.

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 <math>\gamma^{strong}(G) /2</math>.

In contrast, an [[Edge dominating set|'''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 {{math|(1&thinsp;+&nbsp;log ''n'')}}-approximation of a minimum ''k''-tuple dominating set can be found in polynomial time.{{sfnp|Klasing|Laforest|2004}} Every graph admits a ''k''-dominating set (for example, the set of all vertices); but only graphs with minimum degree {{math|''k'' − 1}} 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;{{sfnp|Förster|2013}} An {{math|(1.7 + log Δ)}}-approximation of a minimum ''k''-dominating set can be found in polynomial time as well.

A '''star-dominating set'''  is a [[subset]] ''D'' of ''V'' such that, for every vertex ''v'' in ''V'', the [[Star (graph theory)|star]] of ''v'' (the set of edges adjacent to ''v'') intersects the star of some vertex in ''D''. Clearly, if G has [[Isolated vertex|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.<ref name=":0">{{Cite journal |last=Meshulam |first=Roy |date=2003-05-01 |title=Domination numbers and homology |journal=Journal of Combinatorial Theory, Series A |language=en |volume=102 |issue=2 |pages=321–330 |doi=10.1016/S0097-3165(03)00045-1 |issn=0097-3165 |doi-access=free}}</ref>

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&nbsp;''v''.

==Dominating and independent sets==

Dominating sets are closely related to [[Independent set (graph theory)|independent set]]s: 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.

=== 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''' {{math|''i''(''G'')}} of a graph {{mvar|G}} 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 {{math|''i''(''G'')}} is taken over less elements (only the independent sets are considered), so {{math|''γ''(''G'') ≤ ''i''(''G'')}} for all graphs {{mvar|G}}.

The inequality can be strict - there are graphs {{mvar|G}} for which {{math|''γ''(''G'') < ''i''(''G'')}}.  For example, let {{mvar|G}} be the ''double star graph'' consisting of vertices {{tmath|x_1, \ldots, x_p, a, b, y_1, \ldots, y_q}}, where {{math|''p'', ''q'' > 1}}.  The edges of {{mvar|G}} are defined as follows: each {{mvar|x{{sub|i}}}} is adjacent to {{mvar|a}}, {{mvar|a}} is adjacent to {{mvar|b}}, and {{mvar|b}} is adjacent to each {{mvar|y{{sub|j}}}}.  Then {{math|1=γ(''G'') = 2}} since {{math|{''a'', ''b''} }} is a smallest dominating set.  If {{math|1=''p'' ≤ ''q''}}, then {{math|1=''i''(''G'') = ''p'' + 1}} since {{tmath|\{x_1, \ldots, x_p, b\} }} is a smallest dominating set that is also independent (it is a smallest maximal independent set).

There are graph families in which {{math|1=γ(''G'') = ''i''(''G'')}}, that is, every minimum maximal independent set is a minimum dominating set. For example, {{math|1=γ(''G'') = ''i''(''G'')}} if {{mvar|G}} is a [[claw-free graph]].{{sfnp|Allan|Laskar|1978}}

A graph {{mvar|G}} is called a '''domination-perfect graph''' if {{math|1=''γ''(''H'') = ''i''(''H'')}} in every [[induced subgraph]] {{mvar|H}} of {{mvar|G}}. Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graphs is also domination-perfect.{{sfnp|Faudree|Flandrin|Ryjáček|1997}}

For any graph {{mvar|G}}, its [[line graph]] {{math|''L''(''G'')}} is claw-free, and hence a minimum maximal independent set in {{math|''L''(''G'')}} is also a minimum dominating set in {{math|''L''(''G'')}}. An independent set in {{math|''L''(''G'')}} corresponds to a [[Matching (graph theory)|matching]] in {{mvar|G}}, and a dominating set in {{math|''L''(''G'')}} corresponds to an [[edge dominating set]] in {{mvar|G}}. Therefore a [[minimum maximal matching]] has the same size as a minimum edge dominating set.

=== Domination ''of'' independent sets ===
The '''independence domination number''' {{math|''iγ''(''G'')}} of a graph {{mvar|G}} is the maximum, over all independent sets {{mvar|A}} of {{mvar|G}}, of the smallest set dominating {{mvar|A}}.<ref name=":1">{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Ziv|first3=Ran|date=2007-05-01|title=Independent systems of representatives in weighted graphs|journal=Combinatorica|language=en|volume=27|issue=3|pages=253–267|doi=10.1007/s00493-007-2086-y|s2cid=43510417|issn=1439-6912}}</ref> Dominating subsets of vertices requires potentially less vertices than dominating all vertices, so {{math|''iγ''(''G'') ≤ ''γ''(''G'')}} for all graphs {{mvar|G}}.

The inequality can be strict - there are graphs {{mvar|G}} for which {{math|''iγ''(''G'') < ''γ''(''G'')}}.  For example, for some integer {{mvar|n}}, let {{mvar|G}} be a graph in which the vertices are the rows and columns of an {{mvar|n}}-by-{{mvar|n}} 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 {{math|1=''iγ''(''G'') = 1}}. However, to dominate all vertices we need at least one row and one column, so {{math|1=''γ''(''G'') = 2}}.  Moreover, the ratio between {{math|''γ''(''G'') / ''iγ''(''G'')}} can be arbitrarily large. For example, if the vertices of {{mvar|G}} are all the subsets of squares of an {{mvar|n}}-by-{{mvar|n}} board, then still {{math|1=''iγ''(''G'') = 1}}, but {{math|1=''γ''(''G'') = n}}.<ref name=":1" />

The '''bi-independent domination number''' {{math|''iγi''(''G'')}} of a graph {{mvar|G}} is the maximum, over all independent sets {{mvar|A}} of {{mvar|G}}, of the smallest independent set dominating {{mvar|A}}. The following relations hold for any graph {{mvar|G}}:
<math display="block">\begin{align}
i(G)&\geq \gamma (G) \geq i\gamma(G)
\\
i(G)&\geq i\gamma i(G) \geq i\gamma(G)
\end{align}</math>

==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.{{sfnp|Hedetniemi|Laskar|1990}}

== 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-reduction]]s between the minimum dominating set problem and the [[set cover problem]].{{sfnp|Kann|1992|pp=108–109}} These reductions ([[#L-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 algorithm|approximation ratio]]: for any α, a polynomial-time {{nowrap|α-approximation}} algorithm for minimum dominating sets would provide a polynomial-time {{nowrap|α-approximation}} algorithm for the set cover problem and vice versa. Both problems are in fact [[APX#Related complexity classes|Log-APX-complete]].{{sfnp|Escoffier|Paschos|2006}}

The approximability of set covering is also well understood: a logarithmic approximation factor can be found by using a [[Set cover problem#Greedy algorithm|simple greedy algorithm]], and finding a sublogarithmic approximation factor is NP-hard. More specifically, the greedy algorithm provides a factor {{math|1 + log{{abs|''V''}}}} approximation of a minimum dominating set, and no polynomial time algorithm can achieve an approximation factor better than {{math|''c'' log{{abs|''V''}}}} for some {{math|''c'' > 0}} unless [[P = NP]].{{sfnp|Raz|Safra|1997}}

===L-reductions===

The following two reductions show that the minimum dominating set problem and the [[set cover problem]] are equivalent under [[L-reduction]]s: given an instance of one problem, we can construct an equivalent instance of the other problem.{{sfnp|Kann|1992|pp=108–109}}

====From dominating set to set covering====
Given a graph {{math|1=''G'' = (''V'', ''E'')}} with {{math|1=''V'' = {1, 2, ..., ''n''},}} construct a set cover instance {{math|(''U'', ''S'')}} as follows: the [[Universe (mathematics)|universe]] {{mvar|U}} is {{mvar|V}}, and the family of subsets is {{math|1=''S'' = {''S''{{sub|1}}, ''S''{{sub|2}}, ..., ''S''{{sub|''n''}}} }} such that {{mvar|S{{sub|v}}}} consists of the vertex {{mvar|v}} and all vertices adjacent to {{mvar|v}} in {{mvar|G}}.

Now if {{mvar|D}} is a dominating set for {{mvar|G}}, then {{math|1=''C'' = {''S''{{sub|''v''}} : ''v'' ∈ ''D''} }} is a feasible solution of the set cover problem, with {{math|1={{abs|''C''}} = {{abs|''D''}}}}. Conversely, if {{math|1=''C'' = {''S''{{sub|''v''}} : ''v'' ∈ ''D''} }} is a feasible solution of the set cover problem, then {{mvar|D}} is a dominating set for {{mvar|G}}, with {{math|1={{abs|''D''}} = {{abs|''C''}}}}.

Hence the size of a minimum dominating set for {{mvar|G}} equals the size of a minimum set cover for {{math|(''U'', ''S'')}}. 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 {{nowrap|α-approximation}} algorithm for set covering provides an efficient {{nowrap|α-approximation}} algorithm for minimum dominating sets.

[[File:Dominating-set-2.svg|right]]
::For example, given the graph {{mvar|G}} shown on the right, we construct a set cover instance with the universe {{math|1=''U'' = {1, 2, ..., 6} }} and the subsets {{math|1=''S''{{sub|1}} = {1, 2, 5},}} {{math|1=''S''{{sub|2}} = {1, 2, 3, 5},}} {{math|1=''S''{{sub|3}} = {2, 3, 4, 6},}} {{math|1=''S''{{sub|4}} = {3, 4},}} {{math|1=''S''{{sub|5}} = {1, 2, 5, 6},}} and {{math|1=''S''{{sub|6}} = {3, 5, 6}.}} In this example, {{math|1=''D'' = {3, 5} }} is a dominating set for {{mvar|G}} – this corresponds to the set cover {{math|1=''C'' = {''S''{{sub|3}}, ''S''{{sub|5}}}.}} For example, the vertex {{math|4 ∈ ''V''}} is dominated by the vertex {{math|3 ∈ ''D''}}, and the element {{math|4 ∈ ''U''}} is contained in the set {{math|''S''{{sub|3}} ∈ ''C''}}.

====From set covering to dominating set====
Let {{math|1=(''S'', ''U'')}} be an instance of the set cover problem with the universe {{mvar|U}} and the family of subsets {{math|1=''S'' = {''S''{{sub|''i''}} : ''i'' ∈ ''I''};}} we assume that {{mvar|U}} and the index set {{mvar|I}} are disjoint. Construct a graph {{math|1=''G'' = (''V'', ''E'')}} as follows: the set of vertices is {{math|1=''V'' = ''I'' ∪ ''U''}}, there is an edge {{math|{''i'', ''j''} ∈ ''E''}} between each pair {{math|1=''i'', ''j'' ∈ ''I''}}, and there is also an edge {{math|{''i'', ''u''} }} for each {{math|''i'' ∈ ''I''}} and {{math|''u'' ∈ ''S''{{sub|''i''}}}}. That is, {{mvar|G}} is a [[split graph]]: {{mvar|I}} is a [[Clique (graph theory)|clique]] and {{mvar|U}} is an [[Independent set (graph theory)|independent set]].

Now if {{math|1=''C'' = {''S''{{sub|''i''}} : ''i'' ∈ ''D''} }} is a feasible solution of the set cover problem for some subset {{math|''D'' ⊆ ''I''}}, then {{mvar|D}} is a dominating set for {{mvar|G}}, with {{math|1={{abs|''D''}} = {{abs|''C''}}}}: First, for each {{math|''u'' ∈ ''U''}} there is an {{math|''i'' ∈ ''D''}} such that {{math|''u'' ∈ ''S''{{sub|''i''}}}}, and by construction, {{mvar|u}} and {{mvar|i}} are adjacent in {{mvar|G}}; hence {{mvar|u}} is dominated by {{mvar|i}}. Second, since {{mvar|D}} must be nonempty, each {{math|''i'' ∈ ''I''}} is adjacent to a vertex in {{mvar|D}}.

Conversely, let {{mvar|D}} be a dominating set for {{mvar|G}}. Then it is possible to construct another dominating set {{mvar|X}} such that {{math|{{abs|''X''}} ≤ {{abs|''D''}}}} and {{math|''X'' ⊆ ''I''}}: simply replace each {{math|''u'' ∈ ''D'' ∩ ''U''}} by a neighbour {{math|''i'' ∈ ''I''}} of {{mvar|u}}. Then {{math|1=''C'' = {''S''{{sub|''i''}} : ''i'' ∈ ''X''} }} is a feasible solution of the set cover problem, with {{math|1={{abs|''C''}} = {{abs|''X''}} ≤ {{abs|''D''}}}}.

[[File:Dominating-set-reduction.svg|right]]
::The illustration on the right show the construction for {{math|1=''U'' = {''a'', ''b'', ''c'', ''d'', ''e''}, ''I'' = {1, 2, 3, 4},}} {{math|1=''S''{{sub|1}} = {''a'', ''b'', ''c''},}} {{math|1=''S''{{sub|2}} = {''a'', ''b''},}} {{math|1=''S''{{sub|3}} = {''b'', ''c'', ''d''},}} and {{math|1=''S''{{sub|4}} = {''c'', ''d'', ''e''}.}}

::In this example, {{math|1=''C'' = {''S''{{sub|1}}, ''S''{{sub|4}}} }} is a set cover; this corresponds to the dominating set {{math|1=''D'' = {1, 4}.}}

::{{math|1=''D'' = {''a'', 3, 4} }} is another dominating set for the graph {{mvar|G}}. Given {{mvar|D}}, we can construct a dominating set {{math|1=''X'' = {1, 3, 4} }} which is not larger than {{mvar|D}} and which is a subset of {{mvar|I}}. The dominating set {{mvar|X}} corresponds to the set cover {{math|1=''C'' = {''S''{{sub|1}}, ''S''{{sub|3}}, ''S''{{sub|4}}}.}}

===Special cases===

If the graph has maximum degree Δ, then the greedy approximation algorithm finds an {{math|''O''(log Δ)}}-approximation of a minimum dominating set. Also, let {{mvar|d{{sub|g}}}} be the cardinality of dominating set obtained using greedy approximation then following relation holds, <math> d_g \le N+1 - \sqrt{2M+1}</math>, where {{mvar|N}} is number of nodes and {{mvar|M}} is number of edges in given undirected graph.{{sfnp|Parekh|1991}} For fixed Δ, this qualifies as a dominating set for [[APX]] membership; in fact, it is APX-complete.{{sfnp|Papadimitriou|Yannakakis|1991}}

The problem admits a [[polynomial-time approximation scheme]] (PTAS) for special cases such as [[unit disk graph]]s and [[planar graph]]s.{{sfnp|Crescenzi|Kann|Halldórsson|Karpinski|2000}} A minimum dominating set can be found in linear time in [[series–parallel graph]]s.{{sfnp|Takamizawa|Nishizeki|Saito|1982}}

===Exact algorithms===

A minimum dominating set of an {{mvar|n}}-vertex graph can be found in time {{math|''O''(2{{sup|''n''}}''n'')}} by inspecting all vertex subsets. {{harvtxt|Fomin|Grandoni|Kratsch|2009}} show how to find a minimum dominating set in time {{math|''O''(1.5137{{sup|''n''}})}} and exponential space, and in time {{math|''O''(1.5264{{sup|''n''}})}} and polynomial space. A faster algorithm, using {{math|''O''(1.5048{{sup|''n''}})}} time was found by {{harvtxt|van Rooij|Nederlof|van Dijk|2009}}, 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 {{math|1.7159{{sup|''n''}}}} and all such sets can be listed in time  {{math|''O''(1.7159{{sup|''n''}})}}.{{sfnp|Fomin|Grandoni|Pyatkin|Stepanov|2008}}

===Parameterized complexity===

Finding a dominating set of size {{mvar|k}} 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 {{math|''f''(''k'')''n''{{sup|O(1)}}}} for any function {{mvar|f}} 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 {{mvar|k}},{{sfnp|Alber|Fellows|Niedermeier|2004}} and running times that are exponential in {{radic|''k''}} and cubic in {{mvar|n}} may be obtained by applying [[dynamic programming]] to a [[branch-decomposition]] of the kernel.{{sfnp|Fomin|Thilikos|2006}} 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 graph characterization|forbidden]] [[complete bipartite graph|complete bipartite subgraph]]; that is, the problem is FPT on [[biclique-free graph]]s, a very general class of sparse graphs that includes the planar graphs.{{sfnp|Telle|Villanger|2012}}

The complementary set to a dominating set, a [[nonblocker]], can be found by a fixed-parameter algorithm on any graph.{{sfnp|Dehne|Fellows|Fernau|Prieto|2006}}

== 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.

== Notes ==
{{Reflist}}

== References ==
*{{citation
|last1= Alber | first1= Jochen
|author2-link=Michael Fellows|last2=Fellows|first2=Michael R
|last3=Niedermeier|first3= Rolf|author3-link=Rolf Niedermeier
|title=Polynomial-time data reduction for dominating set
|journal=[[Journal of the ACM]]
|volume= 51|pages= 363–384|year=2004
|doi= 10.1145/990308.990309|issue=3
|arxiv=cs/0207066| s2cid= 488501
}}.
*{{citation
 | last1=Allan | first1 = Robert B.
 | last2=Laskar | first2 = Renu
 | title = On domination and independent domination numbers of a graph
 | journal = Discrete Mathematics
 | year = 1978
 | volume = 23
 | pages = 73–76
 | doi = 10.1016/0012-365X(78)90105-X
 | issue = 2
| doi-access = free
 }}.
*{{citation
 | last1=Crescenzi | first1=Pierluigi
 | last2=Kann | first2=Viggo
 | last3=Halldórsson | first3=Magnús
 | last4=Karpinski | first4=Marek | authorlink4=Marek Karpinski
 | last5=Woeginger | first5=Gerhard | author5-link = Gerhard J. Woeginger
 | title=A Compendium of NP Optimization Problems
 | contribution=Minimum dominating set
 | url=https://www.csc.kth.se/~viggo/wwwcompendium/node11.html
 | year=2000
}}.
*{{citation
 | last1 = Dehne | first1 = Frank
 | last2 = Fellows | first2 = Michael
 | last3 = Fernau | first3 = Henning
 | last4 = Prieto | first4 = Elena | author4-link = Elena Prieto-Rodriguez
 | last5 = Rosamond | first5 = Frances | author5-link = Frances A. Rosamond
 | contribution = Nonblocker: Parameterized algorithmics for minimum dominating set
 | contribution-url = http://www.mrfellows.net/papers/DFFPR06_Nonblocker.pdf
 | doi = 10.1007/11611257_21
 | pages = 237–245
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science, Merin, Czech Republic, January 21-27, 2006, Proceedings
 | volume = 3831
 | year = 2006| isbn = 978-3-540-31198-0
 }}.
*{{citation|last1=Escoffier|first1=Bruno|last2=Paschos|first2=Vangelis Th.|title=Completeness in approximation classes beyond APX|journal=Theoretical Computer Science|date=2006|volume=359|issue=1–3|pages=369–377|doi=10.1016/j.tcs.2006.05.023|doi-access=free|url=https://hal.archives-ouvertes.fr/hal-00958036/file/cahier_225.pdf}}
*{{citation
 | last1 = Faudree | first1 = Ralph | author1-link = Ralph Faudree
 | last2 = Flandrin | first2 = Evelyne
 | last3 = Ryjáček | first3 = Zdeněk
 | doi = 10.1016/S0012-365X(96)00045-3
 | issue = 1–3
 | journal = Discrete Mathematics
 | pages = 87–147
 | title = Claw-free graphs — A survey
 | volume = 164
 | year = 1997
 | mr = 1432221
| doi-access = free
 }}.
*{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Grandoni | first2 = Fabrizio
 | last3 = Kratsch | first3 = Dieter
 | title = A measure & conquer approach for the analysis of exact algorithms
 | journal = [[Journal of the ACM]]
 | volume = 56
 | year = 2009
 | pages = 25:1–32
 | doi = 10.1145/1552285.1552286
 | issue = 5
| s2cid = 1186651
 }}.
*{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Grandoni | first2 = Fabrizio
 | last3 = Pyatkin | first3 = Artem
 | last4 = Stepanov | first4 = Alexey
 | title = Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications
 | journal = ACM Transactions on Algorithms
 | volume = 5
 | year = 2008
 | pages = 9:1–17
 | doi = 10.1145/1435375.1435384
 | issue = 1
| s2cid = 2489447
 }}.
*{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Thilikos | first2 = Dimitrios M.
 | doi = 10.1137/S0097539702419649
 | journal = SIAM Journal on Computing
 | page = 281
 | title = Dominating sets in planar graphs: branch-width and exponential speed-up
 | volume = 36
 | year = 2006
 | issue = 2| s2cid = 5232238
 }}.
*{{citation
 | last1 = Förster | first1 = Klaus-Tycho.
 | year = 2013
 | contribution = Approximating Fault-Tolerant Domination in General Graphs
 | title = Proc. of the Tenth Workshop on Analytic Algorithmics and Combinatorics [[ACM SIGACT#Conferences|ANALCO]]
 | publisher = SIAM
 | pages = 25–32
 | doi = 10.1137/1.9781611973037.4
 | isbn = 978-1-61197-254-2
}}.
*{{Garey-Johnson}}, p.&nbsp;190, problem GT2.
*{{citation
 | last1 = Hedetniemi | first1= S. T.
 | last2 = Laskar | first2= R. C.
 | title = Bibliography on domination in graphs and some basic definitions of domination parameters
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 86
 | issue = 1–3
 | year = 1990
 | pages = 257–277
 | doi = 10.1016/0012-365X(90)90365-O
| doi-access = free
 }}.
*{{citation
 | last = Kann | first = Viggo
 | year = 1992
 | title = On the Approximability of NP-complete Optimization Problems
 | url = https://www.csc.kth.se/~viggo/papers/phdthesis.pdf
 | postscript = . PhD thesis, Department of Numerical Analysis and Computing Science, [[Royal Institute of Technology]], Stockholm
}}.
*{{citation|last1=Klasing|first1=Ralf|last2=Laforest|first2=Christian|title=Hardness results and approximation algorithms of k-tuple domination in graphs|journal=Information Processing Letters|volume=89|issue=2|year=2004|pages=75–83|doi=10.1016/j.ipl.2003.10.004}}.
*{{citation|last1=Papadimitriou|first1=Christos H.|last2=Yannakakis|first2=Mihailis|title=Optimization, Approximation, and Complexity Classes|journal=Journal of Computer and System Sciences|date=1991|volume=43|issue=3|pages=425–440|doi=10.1016/0022-0000(91)90023-X|doi-access=}}
*{{citation|last1=Parekh|first1=Abhay K.|title=Analysis of a greedy heuristic for finding small dominating sets in graphs|journal=Information Processing Letters|date=1991|volume=39|issue=5|pages=237–240|doi=10.1016/0020-0190(91)90021-9|hdl=1721.1/1201|hdl-access=free}}
*{{citation
 | last1 = Raz | first1 = R. | author1-link=Ran Raz
 | last2 = Safra | first2 = S.
 | year = 1997
 | contribution = A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP
 | title = Proc. 29th Annual ACM [[Symposium on Theory of Computing]]
 | publisher = ACM
 | pages = 475–484
 | doi = 10.1145/258533.258641
 | isbn = 0-89791-888-6
| s2cid = 15457604 }}.
*{{citation
 | title = Linear-time computability of combinatorial problems on series–parallel graphs
 | journal = [[Journal of the ACM]]
 | volume = 29
 | issue = 3
 | year = 1982
 | pages = 623–641
 | first1 = K. | last1 = Takamizawa
 | first2 = T. | last2 = Nishizeki | author2-link = Takao Nishizeki
 | first3 = N. | last3 = Saito
 | doi = 10.1145/322326.322328
| s2cid = 16082154
 | doi-access = free
 }}.
*{{citation
 | last1 = Telle | first1 = Jan Arne
 | last2 = Villanger | first2 = Yngve
 | editor1-last = Epstein | editor1-first = Leah
 | editor2-last = Ferragina | editor2-first = Paolo
 | contribution = FPT algorithms for domination in biclique-free graphs
 | doi = 10.1007/978-3-642-33090-2_69
 | pages = 802–812
 | publisher = Springer
 | series = [[Lecture Notes in Computer Science]]
 | title = Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings
 | volume = 7501
 | year = 2012| isbn = 978-3-642-33089-6
 }}.
*{{citation
 | contribution = Inclusion/Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets
 | title = Proc. 17th Annual European Symposium on Algorithms, ESA 2009
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | volume = 5757
 | pages = 554–565
 | year = 2009
 | first1 = J. M. M. | last1 = van Rooij
 | first2 = J. | last2 = Nederlof
 | first3 = T. C. | last3 = van Dijk
 | doi = 10.1007/978-3-642-04128-0_50
 | isbn = 978-3-642-04127-3
}}.

==Further reading==
*{{citation
 | title = A note on the complexity of minimum dominating set
 | last = Grandoni | first = F.
 | journal = Journal of Discrete Algorithms
 | volume = 4
 | pages = 209–214
 | year = 2006
 | doi = 10.1016/j.jda.2005.03.002
 | issue = 2
| citeseerx = 10.1.1.108.3223
 }}.
*{{citation
 | title = Approximation algorithms for connected dominating sets
 | journal = [[Algorithmica]]
 | volume = 20
 | issue = 4
 | year = 1998
 | pages = 374–387
 | first1 = S. | last1 = Guha
 | first2 = S. | last2 = Khuller
 | doi = 10.1007/PL00009201
| hdl = 1903/830
 | s2cid = 1249122
 | url = http://drum.lib.umd.edu/bitstream/1903/830/4/CS-TR-3660.pdf
 | hdl-access = free
 }}.
*{{citation
 | last1 = Haynes
 | first1 = Teresa W.
 | author1-link = Teresa W. Haynes
 | last2 = Hedetniemi
 | first2 = Stephen
 | last3 = Slater
 | first3 = Peter
 | title = Fundamentals of Domination in Graphs
 | publisher = Marcel Dekker
 | year = 1998a
 | isbn = 0-8247-0033-3
 | oclc = 37903553
 | url-access = registration
 | url = https://archive.org/details/fundamentalsofdo0000hayn
 }}.
*{{citation
 | last1 = Haynes | first1 = Teresa W. | author1-link = Teresa W. Haynes
 | last2 = Hedetniemi | first2 = Stephen
 | last3 = Slater | first3 = Peter
 | title = Domination in Graphs: Advanced Topics
 | publisher = Marcel Dekker
 | year = 1998b
 | isbn = 0-8247-0034-1
 | oclc = 38201061
}}.
*{{citation
 | last = West | first = Douglas B. | author1-link = Douglas West (mathematician)
 | title = Introduction to Graph Theory
 | edition = 2
 | publisher = Pearson Education
 | year = 2001
}}.
{{Authority control}}

[[Category:Graph theory objects]]
[[Category:NP-complete problems]]
[[Category:Computational problems in graph theory]]