Доминирующий набор

Доминирующие множества (красные вершины).

В теории графов , A доминирующее множество для графа G = ( V , E ) является подмножество D из V таким образом, что каждая вершина не в D примыкает , по меньшей мере , одного члена D . Число доминирование γ ( G ) есть число вершин в наименьшей доминирующий набор для G .

Проблема доминирующего множества касается проверки того, действительно ли γ ( G ) ≤ K для данного графа G и входа K ; это классическая проблема NP-полного решения в теории сложности вычислений . ^[1] Поэтому считается, что не может быть эффективного алгоритма, который находит наименьшее доминирующее множество для всех графов, хотя существуют эффективные алгоритмы аппроксимации, а также эффективные и точные алгоритмы для определенных классов графов.

На рисунках (a) - (c) справа показаны три примера доминирующих множеств для графа. В каждом примере каждая белая вершина смежна по крайней мере с одной красной вершиной, и говорят, что в белой вершине преобладает красная вершина. Число доминирования этого графа равно 2: примеры (b) и (c) показывают, что существует доминирующее множество с 2 вершинами, и можно проверить, что для этого графа не существует доминирующего множества с одной вершиной.

История [ править ]

Проблема доминирования изучалась с 1950-х годов, но темпы исследований доминирования значительно возросли в середине 1970-х годов. В 1972 году Ричард Карп доказал NP-полноту задачи о покрытии множеств . Это имело непосредственные последствия для проблемы доминирующего множества, так как между двумя задачами есть прямая вершина, которую нужно установить, и ребро к неразъединенному пересечению. Это доказало, что проблема доминирующего множества также является NP-полной . ^[2]

Доминирующие множества представляют практический интерес в нескольких областях. В беспроводных сетях доминирующие наборы используются для поиска эффективных маршрутов в специальных мобильных сетях. Они также использовались при обобщении документов и при проектировании безопасных систем для электрических сетей.

Доминирующие и независимые множества [ править ]

Доминирующие множества тесно связаны с независимыми множествами : независимое множество также является доминирующим множеством тогда и только тогда, когда оно является максимальным независимым множеством , поэтому любое максимальное независимое множество в графе обязательно также является минимальным доминирующим множеством.

Доминирование на независимых множеств [ править ]

Доминирующий набор может быть независимым, а может и не быть. Например, рисунки (a) и (b) выше показывают независимые доминирующие множества, а рисунок (c) иллюстрирует доминирующий набор, который не является независимым набором.

Число независимого доминирования i ( G ) графа G - это размер наименьшего доминирующего множества, которое является независимым множеством. Эквивалентно, это размер наименьшего максимального независимого множества. Минимум в I ( G ) берется меньше элементов (только независимые множества считаются), поэтому у ( G ) ≤ я ( G ) для всех графов G .

Неравенство может быть строгим - существуют графы G, для которых γ ( G ) < i ( G ). Например, пусть G - двойной звездный граф, состоящий из вершин x ₁ , ..., x _p , a , b , y ₁ , ..., y _q , где p , q > 1. Ребра G определены следующим образом: каждый x _i смежен с a , a смежен с b иb примыкает к каждому b _j . Тогда γ ( G ) = 2, поскольку { a , b } - наименьшее доминирующее множество. Если p ≤ q , то i ( G ) = p + 1, поскольку { x ₁ , ..., x _p , b} - наименьшее доминирующее множество, которое также является независимым (это наименьшее максимальное независимое множество).

Существуют семейства графов, в которых γ ( G ) = i ( G ), то есть каждое минимальное максимальное независимое множество является минимальным доминирующим множеством. Например, γ ( G ) = i ( G ), если G - граф без клешней . ^[3]

Граф G называется доминация идеальный график , если γ ( Н ) = я ( Н ) в каждом индуцированный подграф H из G . Поскольку индуцированный подграф графа без клешней не имеет клешней, отсюда следует, что любой граф без клешней также совершенен по доминированию. ^[4]

Для любого графа G его линейный граф L ( G ) не имеет клешней, и, следовательно, минимальное максимальное независимое множество в L ( G ) также является минимальным доминирующим множеством в L ( G ). Независимое множество в L ( G ) соответствует соответствия в G , и множество доминирующих в L ( G ) соответствует краевой доминирующие множества в G . Следовательно, минимальное максимальное соответствие имеет тот же размер, что и минимальное множество с преобладанием ребер.

Доминирование из независимых множеств [ править ]

Число доминации независимости iγ ( G ) граф G является максимальной, по всем независимым множествам А из G , наималейшего множества доминирующего A . ^[5] Доминирующие подмножества вершин требуют потенциально меньше вершин , чем доминирующие все вершины, так iγ ( G ) & le ; & gamma ( G ) для всех графов G .

Неравенство может быть строгим - существуют графы G, для которых iγ ( G ) < γ ( G ). Например, для некоторого целого п , пусть G граф , в котором вершины строки и столбцы в N матрицу с размерностью п плате, и две такие вершины соединены , если и только если они пересекаются. Единственными независимыми наборами являются наборы только строк или наборы только столбцов, и в каждом из них может доминировать одна вершина (столбец или строка), поэтому iγ ( G ) = 1. Однако, чтобы доминировать над всеми вершинами, нам нужны хотя бы одна строка и один столбец, поэтому γ ( G ) = 2. Кроме того, соотношение междуγ ( G ) / iγ ( G ) может быть сколь угодно большим. Например, если вершины G являются все подмножества квадратов давал ˝n˝ матрицу с размерностью п платы, тогда еще iγ ( G ) = 1, а γ ( G ) = п . ^[5]

Би-независимое доминирование номер iγi ( G ) графа G является максимальным, по всем независимых множеств А из G , наименьшего независимого множества доминирующих А . Для любого графа G выполняются следующие соотношения :

{\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{aligned}}

Алгоритмы и вычислительная сложность [ править ]

Задача покрытия множества - это хорошо известная NP-трудная проблема: решающая версия покрытия множества была одной из 21 NP-полных проблем Карпа . Существует пара полиномиальных L-редукций между проблемой минимального доминирующего множества и проблемой покрытия множества . ^[6] Эти сокращения ( см. Ниже ) показывают, что эффективный алгоритм для задачи минимального доминирующего множества обеспечит эффективный алгоритм для задачи покрытия множества, и наоборот. Кроме того, редукции сохраняют отношение аппроксимации: для любого α алгоритм α-аппроксимации с полиномиальным временем для минимальных доминирующих множеств обеспечит алгоритм α-аппроксимации с полиномиальным временем для задачи покрытия множеств и наоборот. Обе проблемы фактически являются Log-APX-complete . ^[7]

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 1 + log |V| approximation of a minimum dominating set, and no polynomial time algorithm can achieve an approximation factor better than c log |V| for some c > 0 unless P = NP.^[8]

L-reductions[edit]

Следующие две редукции показывают, что проблема минимального доминирующего множества и проблема покрытия множества эквивалентны при L-редукциях : по экземпляру одной задачи мы можем построить эквивалентный экземпляр другой задачи. ^[6]

From dominating set to set covering.Given a graph G = (V, E) with V = {1, 2, ..., n}, construct a set cover instance (U, S) as follows: the universe U is V, and the family of subsets is S = {S₁, S₂, ..., S_n} such that S_v consists of the vertex v and all vertices adjacent to v in G.

Now if D is a dominating set for G, then C = {S_v : v ∈ D} is a feasible solution of the set cover problem, with |C| = |D|. Conversely, if C = {S_v : v ∈ D} is a feasible solution of the set cover problem, then D is a dominating set for G, with |D| = |C|.

Следовательно, размер минимального доминирующего множества для G равен размеру минимального покрытия множества для ( U , S ). Кроме того, существует простой алгоритм, который сопоставляет доминирующее множество с множеством обложек того же размера и наоборот. В частности, эффективный алгоритм α-приближения для покрытия множества обеспечивает эффективный алгоритм α-приближения для минимальных доминирующих множеств.

Например, учитывая граф G, показанный справа, мы строим экземпляр покрытия множества с универсумом U = {1, 2, ..., 6} и подмножествами S ₁ = {1, 2, 5}, S ₂ = {1, 2, 3, 5}, S ₃ = {2, 3, 4, 6}, S ₄ = {3, 4}, S ₅ = {1, 2, 5, 6} и S ₆ = {3, 5, 6}. В этом примере D = {3, 5} является доминирующим множеством для G - это соответствует множеству покрытия C = { S ₃ , S ₅ }. Например, вершина 4 ∈ Vдоминирует в вершине 3 ∈ D , а элемент 4 ∈ U содержится в множестве S ₃ ∈ C .

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

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

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

The illustration on the right show the construction for U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S₁ = {a, b, c}, S₂ = {a, b}, S₃ = {b, c, d}, and S₄ = {c, d, e}.

In this example, C = {S₁, S₄} is a set cover; this corresponds to the dominating set D = {1, 4}.

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

Special cases[edit]

If the graph has maximum degree Δ, then the greedy approximation algorithm finds an O(log Δ)-approximation of a minimum dominating set. Also, let d_g be the cardinality of dominating set obtained using greedy approximation then following relation holds, $d_{g}\leq N+1-{\sqrt {2M+1}}$ , where N is number of nodes and M is number of edges in given undirected graph.^[9] For fixed Δ, this qualifies as a dominating set for APX membership; in fact, it is APX-complete.^[10]

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

Exact algorithms[edit]

A minimum dominating set of an n-vertex graph can be found in time O(2ⁿn) by inspecting all vertex subsets. Fomin, Grandoni & Kratsch (2009) show how to find a minimum dominating set in time O(1.5137ⁿ) and exponential space, and in time O(1.5264ⁿ) and polynomial space. A faster algorithm, using O(1.5048ⁿ) time was found by 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 1.7159ⁿ and all such sets can be listed in time O(1.7159ⁿ).^[13]

Parameterized complexity[edit]

Finding a dominating set of size k 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 f(k)n^O(1) for any function 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 k,^[14] and running times that are exponential in √k and cubic in n may be obtained by applying dynamic programming to a branch-decomposition of the kernel.^[15] 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.^[16]

The complementary set to a dominating set, a nonblocker, can be found by a fixed-parameter algorithm on any graph.^[17]

Variants[edit]

An important subclass of the dominating sets is the class of connected dominating sets. 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. 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.

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. An (1+log n)-approximation of a minimum k-tuple dominating set can be found in polynomial time.^[18] Similarly, 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. While every graph admits a k-dominating set, only graphs with minimum degree 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;^[19] An (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 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.^[20]

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.

Notes[edit]

^ Garey & Johnson (1979).
^ Hedetniemi & Laskar (1990).
^ Allan & Laskar (1978).
^ Faudree, Flandrin & Ryjáček (1997).
^ a b Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.
^ a b Kann (1992), pp. 108–109.
^ Escoffier & Paschos (2006).
^ Raz & Safra (1997).
^ Parekh (1991).
^ Papadimitriou & Yannakakis (1991).
^ Crescenzi et al. (2000).
^ Takamizawa, Nishizeki & Saito (1982).
^ Fomin et al. (2008).
^ Alber, Fellows & Niedermeier (2004).
^ Fomin & Thilikos (2006).
^ Telle & Villanger (2012).
^ Dehne et al. (2006).
^ Klasing & Laforest (2004).
^ Förster (2013).
^ Meshulam, Roy (2003-05-01). "Domination numbers and homology". Journal of Combinatorial Theory, Series A. 102 (2): 321–330. doi:10.1016/S0097-3165(03)00045-1. ISSN 0097-3165.

References[edit]

Alber, Jochen; Fellows, Michael R; Niedermeier, Rolf (2004), "Polynomial-time data reduction for dominating set", Journal of the ACM, 51 (3): 363–384, arXiv:cs/0207066, doi:10.1145/990308.990309, S2CID 488501.
Allan, Robert B.; Laskar, Renu (1978), "On domination and independent domination numbers of a graph", Discrete Mathematics, 23 (2): 73–76, doi:10.1016/0012-365X(78)90105-X.
Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum dominating set", A Compendium of NP Optimization Problems CS1 maint: discouraged parameter (link).
Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena; Rosamond, Frances (2006), "Nonblocker: Parameterized algorithmics for minimum dominating set" (PDF), SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science, Merin, Czech Republic, January 21-27, 2006, Proceedings, Lecture Notes in Computer Science, 3831, Springer, pp. 237–245, doi:10.1007/11611257_21.
Escoffier, Bruno; Paschos, Vangelis Th. (2006), "Completeness in approximation classes beyond APX", Theoretical Computer Science, 359 (1–3): 369–377, doi:10.1016/j.tcs.2006.05.023
Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics, 164 (1–3): 87–147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221.
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms", Journal of the ACM, 56 (5): 25:1–32, doi:10.1145/1552285.1552286, S2CID 1186651.
Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), "Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications", ACM Transactions on Algorithms, 5 (1): 9:1–17, doi:10.1145/1435375.1435384, S2CID 2489447.
Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), "Dominating sets in planar graphs: branch-width and exponential speed-up", SIAM Journal on Computing, 36 (2): 281, doi:10.1137/S0097539702419649, S2CID 5232238.
Förster, Klaus-Tycho. (2013), "Approximating Fault-Tolerant Domination in General Graphs", Proc. of the Tenth Workshop on Analytic Algorithmics and Combinatorics ANALCO, SIAM, pp. 25–32, doi:10.1137/1.9781611973037.4, ISBN 978-1-61197-254-2.
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, p. 190, problem GT2.
Hedetniemi, S. T.; Laskar, R. C. (1990), "Bibliography on domination in graphs and some basic definitions of domination parameters", Discrete Mathematics, 86 (1–3): 257–277, doi:10.1016/0012-365X(90)90365-O.
Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF). PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, StockholmCS1 maint: postscript (link).
Klasing, Ralf; Laforest, Christian (2004), "Hardness results and approximation algorithms of k-tuple domination in graphs", Information Processing Letters, 89 (2): 75–83, doi:10.1016/j.ipl.2003.10.004.
Papadimitriou, Christos H.; Yannakakis, Mihailis (1991), "Optimization, Approximation, and Complexity Classes", Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016/0022-0000(91)90023-X
Parekh, Abhay K. (1991), "Analysis of a greedy heuristic for finding small dominating sets in graphs", Information Processing Letters, 39 (5): 237–240, doi:10.1016/0020-0190(91)90021-9
Raz, R.; Safra, S. (1997), "A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP", Proc. 29th Annual ACM Symposium on Theory of Computing, ACM, pp. 475–484, doi:10.1145/258533.258641, ISBN 0-89791-888-6, S2CID 15457604.
Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs", Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328, S2CID 16082154.
Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, Lecture Notes in Computer Science, 7501, Springer, pp. 802–812, doi:10.1007/978-3-642-33090-2_69.
van Rooij, J. M. M.; Nederlof, J.; van Dijk, T. C. (2009), "Inclusion/Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets", Proc. 17th Annual European Symposium on Algorithms, ESA 2009, Lecture Notes in Computer Science, 5757, Springer, pp. 554–565, doi:10.1007/978-3-642-04128-0_50, ISBN 978-3-642-04127-3.