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

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

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

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

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

История

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

Границы

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

Например, если задан граф G, показанный справа, мы строим покрытие множества с множеством U = {1, 2, …, 6} и подмножествами S1 = {1, 2, 5}, S2 = {1, 2, 3, 5}, S3 = {2, 3, 4, 6}, S4 = {3, 4}, S5 = {1, 2, 5, 6} и S6 = {3, 5, 6}. В этом примере D = {3, 5} является доминирующим множеством для G — оно соответствует покрытию C = {S3, S5}. Например, вершина 4 ∈ V доминируется вершиной 3 ∈ D, а элемент 4 ∈ U содержится во множестве S3 ∈ C.

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

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

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

Рисунок справа показывает построение для U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S1 = {a, b, c}, S2 = {a, b}, S3 = {b, c, d}, and S4 = {c, d, e}.
В этом примере C = {S1, S4} является покрытием множества. Оно соответствует доминирующему множеству D = {1, 4}.
D = {a, 3, 4} — другое доминирующее множество для графа G. Ели D задано, мы можем построить доминирующее множество X = {1, 3, 4}, которое не превосходит D и которое является подмножеством I. Доминирующее множество X соответствует покрытию множества C = {S1, S3, S4}.

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

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

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

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

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

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

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

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

Варианты

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

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

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

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

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

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

Программное обеспечение для поиска минимального доминирующего множества
Название Лицензия Пользовательский язык Краткая информация
OpenOptBSDPythonИспользует графы NetworkX. Может использовать свободно распространяемые и коммерческие пакеты. См. dominating set страницу для подробностей и примеров

См. также

Примечания
  1. Гэри, Джонсон, 1982, с. 235, Задача ТГ2.
  2. Hedetniemi, Laskar, 1990.
  3. Haynes, Hedetniemi, Slater, 1998a, с. Chapter 2.
  4. Часто встречается путаница с терминами наибольшее множество и максимальное множество. В данной статье под наибольшим множеством понимается множество, которое нельзя расширить, сохраняя его свойство. Под максимальным множеством понимается множество с данным свойством, имеющее максимальный размер.
  5. Allan, Laskar, 1978.
  6. Faudree, Flandrin, Ryjáček, 1997.
  7. Kann, 1992, с. 108–109.
  8. Escoffier, Paschos, 2006, с. 369–377.
  9. Raz, Safra, 1997.
  10. Parekh, 1991, с. 237-240.
  11. Papadimitriou, Yannakakis, 1991, с. 425–440.
  12. Crescenzi, Kann, Halldórsson, Karpinski, 2000.
  13. Takamizawa, Nishizeki, Saito, 1982.
  14. Fomin, Grandoni, Kratsch, 2009.
  15. van Rooij, Nederlof, van Dijk, 2009.
  16. Fomin, Grandoni, Pyatkin, Stepanov, 2008.
  17. Alber, Fellows, Niedermeier, 2004.
  18. Fomin, Thilikos, 2006.
  19. Telle, Villanger, 2012.
  20. Klasing, Laforest, 2004.
  21. Förster, 2013.

Литература
  • 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..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.