Доминирующее множество

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

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

Задача о доминирующем множестве заключается в проверке, верно ли неравенство γ(G) ≤ K для заданного графа G и числа K. Задача является классической NP-полной проблемой разрешимости в теории вычислительной сложности. Таким образом полагают, что не существует эффективного алгоритма для нахождения наименьшего доминирующего множества для заданного графа.

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

История

Как заметили Хедееними и Ласкар, задача доминирования изучалась с 1950-х годов, но число исследований по доминированию существенно возросло в середине 1970-х. Их библиография включает более 300 статей, связанных с доминированием на графах.

Границы

Пусть G — граф с n ≥ 1 вершинами, и пусть Δ — максимальная степень графа. Известны следующие границы γ(G):

• Одна вершина может доминировать максимум Δ других вершин, поэтому γ(G) ≥ n/(1 + Δ).
• Множество всех вершин является доминирующим множеством в любом множестве, поэтому γ(G) ≤ n.
• Если в графе G нет изолированных вершин, то имеется два раздельных доминирующих множества в G. См. доматическое разложение для деталей. Таким образом, для графов без изолированных вершин выполняется γ(G) ≤ n/2.

Независимая доминация

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

Минимальное доминирующее множество в графе не обязательно будет независимым, но размер минимального доминирующего множества всегда меньше либо равен размеру минимального наибольшего независимого множества, то есть γ(G) ≤ i(G).

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

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

Примеры

Фигуры (a) и (b) демонстрируют независимые доминантные множества, в то время как фигура (c) демонстрирует множество, не являющееся независимым.

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

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

Существует пара L-приведений полиномиального времени между задачей минимального доминирующего множества и задачей о покрытии множества. Эти редукции (см. ниже) показывают, что эффективный алгоритм для задачи о минимальном доминирующем множестве дал бы эффективный алгоритм для задачи о покрытии множества, и наоборот. Более того, приведения сохраняют аппроксимационный коэффициент — для любого α, α-аппроксимирующий алгоритм полиномиального времени нахождения минимального доминирующих множеств обеспечил бы α-аппроксимирующий алгоритм полиномиального времени для задачи о покрытии множества, и наоборот. Обе задачи, фактически, являются Log-APX-полными.

Задача о покрытии множества является хорошо известной NP-трудной задачей — задача о покрытии множества в варианте проблемы разрешимости была одной из 21 NP-полных задач Карпа, для которой была доказана NP-полнота уже в 1972. Возможность приведения показывает, что задача о доминирующем множестве является также NP-трудной.

Аппроксимируемость задачи о покрытии множества также хорошо понятна — логарифмический множитель аппроксимации может быть найден с использованием простого жадного алгоритма, а нахождение сублогарифмического и логарифмического множителя является NP-трудной задачей. Конкретнее — жадный алгоритм даёт аппроксимирующий множитель 1 + log |V| для минимального доминирующего множества, а Раз и Сафра показали, что никакой алгоритм не даст аппроксимирующий множитель лучше C*log |V| для некоторого C > 0, если только не P = NP.

L-приведения

Следующая пара приведений показывает, что задача о минимальном доминирующего множества и задача о покрытии множества эквивалентны по L-приведению — если дана одна задача, мы можем построить эквивалентную постановку другой задачи.

От доминирующего множества к покрытию множества. Если задан граф G = (V, E) с V = {1, 2, …, n}, строим покрытие множества (U, S) следующим образом: Множество U равно V, а семейство подмножеств равно S = {S₁, S₂, …, S_n}, где S_vсостоит из вершины v и всех вершин, смежных v вершин из G.

Теперь, если D является доминирующим множеством в G, то C = {S_v : v ∈ D} является допустимым решением для задачи покрытия с |C| = |D|. Обратно, если C = {S_v : v ∈ D} является допустимым решением для задачи покрытия, то D является доминирующим множеством для G с |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.

Из покрытия множества к доминирующему множеству. Пусть (S, U) — решение задачи покрытия множества с совокупностью U и семейством подмножеств S = {S_i : i ∈ I}. Мы предполагаем, что U и множество индексов I не пересекаются. Строим граф G = (V, E) следующим образом. В качестве множества вершин возьмём V = I ∪ U. Определяем ребро {i, j} ∈ E между каждой парой i, j ∈ I, а также ребро {i, u} для каждого i ∈ I и u ∈ S_i. То есть G является расщепляемым графом — I является кликой и U является независимым множеством.

Теперь, если C = {S_i : i ∈ D} является допустимым решением задачи покрытия множества для некоторого подмножества D ⊆ I, тогда D является доминирующим множеством для G с |D| = |C|: Первое, для любой вершины u ∈ U существует i ∈ D, такой, что u ∈ S_i, и, по построению, u и i смежны в G. Отсюда — u доминируется вершиной i. Второе, поскольку D должен быть непустым, любая i ∈ I смежна вершине в D.

Обратно — пусть D является доминирующим множеством для G. Тогда можно построить другое доминирующее множество X, такое, что |X| ≤ |D| и X ⊆ I — просто заменяет каждую вершину u ∈ D ∩ U соседней к u вершиной i ∈ I. Тогда C = {S_i : i ∈ X} является допустимым решением задачи покрытия с |C| = |X| ≤ |D|.

Рисунок справа показывает построение для 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}.

В этом примере C = {S₁, S₄} является покрытием множества. Оно соответствует доминирующему множеству D = {1, 4}.

D = {a, 3, 4} — другое доминирующее множество для графа G. Ели D задано, мы можем построить доминирующее множество X = {1, 3, 4}, которое не превосходит D и которое является подмножеством I. Доминирующее множество X соответствует покрытию множества C = {S₁, S₃, S₄}.

Специальные случаи

Если граф имеет максимальную степень Δ, то жадный аппроксимационный алгоритм находит O(log Δ)-аппроксимацию минимального доминирующего множества. Также пусть d_g является мощностью доминирующего множества, полученного с помощью жадного аппроксимационного алгоритма, тогда выполняется следующее отношение: d_g ≤ N+1 — ${\sqrt {2M+1}}$, где N — число узлов, а M — число рёбер в заданном неориентированном графе . Для фиксированного Δ это означает принадлежность задачи поиска доминирующего множества классу APX. Фактически задача является APX-полной.

Алгоритм допускает PTAS для специальных случаев, таких как графы единичных кругов и планарные графы. Минимальное доминирующее множество может быть найдено за линейное время в параллельно-последовательных графах.

Точные алгоритмы

Минимальное доминирующее множество графа с n вершинами может быть найдено за время O(2ⁿn) путём просмотра всех подмножеств вершин. Фомин, Грандони и Кратч показали, как найти минимальное доминирующее множество за время O(1.5137ⁿ), при использовании экспоненциальной памяти, и за время O(1.5264ⁿ), при использовании полиномиальной памяти. Более быстрый алгоритм, работающий за время O(1.5048ⁿ), был найден фон Роем, Недерлофом и фон Дейком , которые показали, что число минимальных доминирующих множеств может быть вычислено за указанное время. Число минимальных доминирующих множеств не превосходит 1.7159ⁿ и все такие множества могут быть перечислены за время O(1.7159ⁿ) .

Параметрическая сложность

Поиск доминирующего множества размера k играет центральную роль в теории параметрической сложности. Задача является наиболее известной W[2]-полной задачей и используется во многих случаях для показа трудноразрешимости задачи путём приведения её к задаче поиска доминирующего множества. В частности, задача не является фиксированно-параметрически разрешимой (ФПР) в том смысле, что не существует алгоритма со временем работы f(k)n^O(1) для любой функции f, разве только W-иерархия не сворачивается в FPT=W[2].

С другой стороны, если входной граф планарен, задача остаётся NP-трудной, но алгоритм с фиксированным параметром известен. Фактически задача имеет ядро с размером, линейным по k, а время работы, экспоненциальное по √k и кубическое по n, может быть достигнуто при применении динамического программирования к разбиению на ветви ядра. Более обще, задача доминирующего множества и многие варианты задачи являются фиксированно-параметрически разрешимыми, если параметризация проводится как по размеру доминирующего множества, так и по размеру наименьшего запрещённого полного двудольного подграфа. То есть задача является ФПР на графах без биклик, достаточно общего класса разреженных графов, в который входят планарные графы.

Варианты

Гипотеза Визинга связывает число доминирования прямого произведения графов с числами доминирования его множителей.

Имеется множество статей о связном доминирующем множестве. Если S является связным доминирующим множеством, можно образовать остовное дерево графа G, в котором S образует множество нелистовых вершин дерева. Обратно, если T является остовным деревом графа с более чем двумя вершинами, нелистовые вершины T образуют связное доминирующее множество. Таким образом, поиск минимальных связных доминирующих множеств эквивалентен поиску остовных деревьев с максимальным возможным числом листьев.

Полное доминирующее множество — это множество вершин, таких, что все вершины графа (включая вершины самого доминирующего множества) имеют соседей в доминирующем множестве. Рисунок (c) выше показывает доминирующее множество, являющееся связным доминирующим множеством и полным доминирующим множеством одновременно. На рисунках (a) и (b) доминирующие множества не являются ни теми, ни другими.

k-кортежное доминирующее множество — это множество вершин, таких, что каждая вершина в графе имеет по меньшей мере k соседей в множестве. (1+log n)-аппроксимация минимального k-кортежного доминирующего множества может быть найден за полиномиальное время . Подобно этому, k-доминирующее множество — это множество вершин, такое, что каждая вершина, не принадлежащая множеству, имеет по меньшей мере k соседей в множестве. В то время как любой граф допускает k-доминирующее множество, только графы с минимальной степенью k-1 допускают k-кортежное доминирующее множество. Однако, даже если граф допускает k-кортежное доминирующее множество, минимальное k-кортежное доминирующее множество может быть почти в k раз больше минимального k-доминирующего множества для того же графа . (1.7+log Δ)-аппроксимация минимального k-доминирующего множества может быть найдена также в полиномиальное время.

Доматическое разложение — это разложение вершин на непересекающиеся доминирующие множества. Доматическое число — это максимальный размер доматического разложения.

Вечное доминирующее множество — это динамическая версия доминирования, в которой вершина v в доминирующем множестве D выбирается и заменяется соседней u (u не из D) таким образом, что модифицированное множество D также является доминирующим и этот процесс может быть повторён для любой конечной последовательности выборов вершин v.

См. также

• Задача о покрытии множества
• Число зависимости

Литература

• Bruno Escoffier, Vangelis Th. Paschos. Completeness in approximation classes beyond APX // Theoretical Computer Science. — 2006. — Т. 359, вып. 1-3. — С. 369–377. — doi:10.1016/j.tcs.2006.05.023.
• Abhay K. Parekh. Analysis of a greedy heuristic for finding small dominating sets in graphs // Information Processing Letters. — 1991. — Т. 39, вып. 5. — С. 237-240. — doi:10.1016/0020-0190(91)90021-9.

• Christos H. Papadimitriou, Mihailis Yannakakis. Optimization, Approximation, and Complexity Classes // Journal of Computer and Systems Sciences. — 1991. — Т. 43, вып. 3. — С. 425–440. — doi:10.1016/0022-0000(91)90023-X.
• Jochen Alber, Michael R Fellows, Rolf Niedermeier. Polynomial-time data reduction for dominating set // Journal of the ACM. — 2004. — Т. 51, вып. 3. — С. 363–384. — doi:10.1145/990308.990309..
• Robert B. Allan, Renu Laskar. On domination and independent domination numbers of a graph // Discrete Mathematics. — 1978. — Т. 23, вып. 2. — С. 73–76. — doi:10.1016/0012-365X(78)90105-X..
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger. A Compendium of NP Optimization Problems. — 2000..
• Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček. Claw-free graphs — A survey // Discrete Mathematics. — 1997. — Т. 164, вып. 1–3. — С. 87–147. — doi:10.1016/S0012-365X(96)00045-3..
• Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch. A measure & conquer approach for the analysis of exact algorithms // Journal of the ACM. — 2009. — Т. 56, вып. 5. — С. 25:1–32. — doi:10.1145/1552285.1552286..
• Fedor V. Fomin, Fabrizio Grandoni, Artem Pyatkin, Alexey Stepanov. Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications // ACM Transactions on Algorithms. — 2008. — Т. 5, вып. 1. — С. 9:1–17. — doi:10.1145/1435375.1435384..
• Fedor V. Fomin, Dimitrios M. Thilikos. Dominating sets in planar graphs: branch-width and exponential speed-up // SIAM Journal on Computing. — 2006. — Т. 36, вып. 2. — С. 281. — doi:10.1137/S0097539702419649..
• Klaus-Tycho Förster. Proc. of the Tenth Workshop on Analytic Algorithmics and Combinatorics ANALCO. — SIAM, 2013. — С. 25–32. — ISBN 978-1-61197-254-2. — doi:10.1137/1.9781611973037.4..
• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — Москва: «Мир», 1982. — С. 235, Задача ТГ2.
• F. Grandoni. A note on the complexity of minimum dominating set // Journal of Discrete Algorithms. — 2006. — Т. 4, вып. 2. — С. 209–214. — doi:10.1016/j.jda.2005.03.002..
• S. Guha, S. Khuller. Approximation algorithms for connected dominating sets // Algorithmica. — 1998. — Т. 20, вып. 4. — С. 374–387. — doi:10.1007/PL00009201..
• Teresa W. Haynes, Stephen Hedetniemi, Peter Slater. Fundamentals of Domination in Graphs. — Marcel Dekker, 1998a. — ISBN 0-8247-0033-3..
• Teresa W. Haynes, Stephen Hedetniemi, Peter Slater. Domination in Graphs: Advanced Topics. — Marcel Dekker, 1998b. — ISBN 0-8247-0034-1..
• S. T. Hedetniemi, R. C. Laskar. Bibliography on domination in graphs and some basic definitions of domination parameters // Discrete Mathematics. — 1990. — Т. 86, вып. 1–3. — С. 257–277. — doi:10.1016/0012-365X(90)90365-O..
• Ralf Klasing, Christian Laforest. Hardness results and approximation algorithms of k-tuple domination in graphs // Information Processing Letters. — 2004. — Т. 89, вып. 2. — С. 75–83. — doi:10.1016/j.ipl.2003.10.004..
• Viggo Kann. On the Approximability of NP-complete Optimization Problems // . PhD thesis. — Stockholm: Department of Numerical Analysis and Computing Science, Royal Institute of Technology, 1992..
• R. Raz, S. Safra. Proc. 29th Annual ACM Symposium on Theory of Computing. — ACM, 1997. — С. 475–484. — ISBN 0-89791-888-6. — doi:10.1145/258533.258641..
• K. Takamizawa, T. Nishizeki, N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs // Journal of the ACM. — 1982. — Т. 29, вып. 3. — С. 623–641. — doi:10.1145/322326.322328..
• Jan Arne Telle, Yngve Villanger. Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings / Leah Epstein, Paolo Ferragina. — Springer, 2012. — Т. 7501. — С. 802–812. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-33090-2_69..
• J. M. M. van Rooij, J. Nederlof, T. C. van Dijk. Proc. 17th Annual European Symposium on Algorithms, ESA 2009. — Springer, 2009. — Т. 5757. — С. 554–565. — (Lecture Notes in Computer Science). — ISBN 978-3-642-04127-3. — doi:10.1007/978-3-642-04128-0_50..