Английская Википедия: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 Шаблон:Math is a subset Шаблон:Math of its vertices, such that any vertex of Шаблон:Math is in Шаблон:Math, or has a neighbor in Шаблон:Math. The domination number Шаблон:Math is the number of vertices in a smallest dominating set for Шаблон:Mvar.

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

Formal definition

Given an undirected graph Шаблон:Math, 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 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. 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 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 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 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-approximation of a minimum k-tuple dominating set can be found in polynomial time.Шаблон:Sfnp Every graph admits a k-dominating set (for example, the set of all vertices); but only graphs with minimum degree Шаблон:Math 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 An Шаблон:Math-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 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.^[1]

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.

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, 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 of a graph Шаблон:Mvar 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 is taken over less elements (only the independent sets are considered), so Шаблон:Math for all graphs Шаблон:Mvar.

The inequality can be strict - there are graphs Шаблон:Mvar for which Шаблон:Math. For example, let Шаблон:Mvar be the double star graph consisting of vertices Шаблон:Tmath, where Шаблон:Math. The edges of Шаблон:Mvar are defined as follows: each Шаблон:Mvar is adjacent to Шаблон:Mvar, Шаблон:Mvar is adjacent to Шаблон:Mvar, and Шаблон:Mvar is adjacent to each Шаблон:Mvar. Then Шаблон:Math since Шаблон:Math is a smallest dominating set. If Шаблон:Math, then Шаблон:Math since Шаблон:Tmath is a smallest dominating set that is also independent (it is a smallest maximal independent set).

There are graph families in which Шаблон:Math, that is, every minimum maximal independent set is a minimum dominating set. For example, Шаблон:Math if Шаблон:Mvar is a claw-free graph.Шаблон:Sfnp

A graph Шаблон:Mvar is called a domination-perfect graph if Шаблон:Math in every induced subgraph Шаблон:Mvar of Шаблон:Mvar. Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graphs is also domination-perfect.Шаблон:Sfnp

For any graph Шаблон:Mvar, its line graph Шаблон:Math is claw-free, and hence a minimum maximal independent set in Шаблон:Math is also a minimum dominating set in Шаблон:Math. An independent set in Шаблон:Math corresponds to a matching in Шаблон:Mvar, and a dominating set in Шаблон:Math corresponds to an edge dominating set in Шаблон:Mvar. Therefore a minimum maximal matching has the same size as a minimum edge dominating set.

Domination of independent sets

The independence domination number Шаблон:Math of a graph Шаблон:Mvar is the maximum, over all independent sets Шаблон:Mvar of Шаблон:Mvar, of the smallest set dominating Шаблон:Mvar.^[2] Dominating subsets of vertices requires potentially less vertices than dominating all vertices, so Шаблон:Math for all graphs Шаблон:Mvar.

The inequality can be strict - there are graphs Шаблон:Mvar for which Шаблон:Math. For example, for some integer Шаблон:Mvar, let Шаблон:Mvar be a graph in which the vertices are the rows and columns of an Шаблон:Mvar-by-Шаблон:Mvar 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. However, to dominate all vertices we need at least one row and one column, so Шаблон:Math. Moreover, the ratio between Шаблон:Math can be arbitrarily large. For example, if the vertices of Шаблон:Mvar are all the subsets of squares of an Шаблон:Mvar-by-Шаблон:Mvar board, then still Шаблон:Math, but Шаблон:Math.^[2]

The bi-independent domination number Шаблон:Math of a graph Шаблон:Mvar is the maximum, over all independent sets Шаблон:Mvar of Шаблон:Mvar, of the smallest independent set dominating Шаблон:Mvar. The following relations hold for any graph Шаблон:Mvar: <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

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.Шаблон: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 Шаблон:Nowrap algorithm for minimum dominating sets would provide a polynomial-time Шаблон:Nowrap algorithm for the set cover problem and vice versa. Both problems are in fact Log-APX-complete.Шаблон: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 Шаблон:Math approximation of a minimum dominating set, and no polynomial time algorithm can achieve an approximation factor better than Шаблон:Math for some Шаблон:Math unless P = NP.Шаблон: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.Шаблон:Sfnp

From dominating set to set covering

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

Now if Шаблон:Mvar is a dominating set for Шаблон:Mvar, then Шаблон:Math is a feasible solution of the set cover problem, with Шаблон:Math. Conversely, if Шаблон:Math is a feasible solution of the set cover problem, then Шаблон:Mvar is a dominating set for Шаблон:Mvar, with Шаблон:Math.

Hence the size of a minimum dominating set for Шаблон:Mvar equals the size of a minimum set cover for Шаблон: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 Шаблон:Nowrap algorithm for set covering provides an efficient Шаблон:Nowrap algorithm for minimum dominating sets.

Файл:Dominating-set-2.svg

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

From set covering to dominating set

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

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

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

Файл:Dominating-set-reduction.svg

The illustration on the right show the construction for Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math and Шаблон:Math

In this example, Шаблон:Math is a set cover; this corresponds to the dominating set Шаблон:Math

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

Special cases

If the graph has maximum degree Δ, then the greedy approximation algorithm finds an Шаблон:Math-approximation of a minimum dominating set. Also, let Шаблон:Mvar 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 is number of nodes and Шаблон:Mvar is number of edges in given undirected graph.Шаблон:Sfnp For fixed Δ, this qualifies as a dominating set for APX membership; in fact, it is APX-complete.Шаблон:Sfnp

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

Exact algorithms

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

Parameterized complexity

Finding a dominating set of size Шаблон: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 Шаблон:Math for any function Шаблон: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 Шаблон:Mvar,Шаблон:Sfnp and running times that are exponential in Шаблон:Radic and cubic in Шаблон:Mvar may be obtained by applying dynamic programming to a branch-decomposition of the kernel.Шаблон: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.Шаблон:Sfnp

The complementary set to a dominating set, a nonblocker, can be found by a fixed-parameter algorithm on any graph.Шаблон:Sfnp

Notes

Шаблон:Reflist

References

Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Garey-Johnson, p. 190, problem GT2.
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation
Шаблон:Citation
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation.
Шаблон:Citation.

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Dominating set

Содержание