В теории графов доминирующее множество для графа 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 — ${\displaystyle {\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 играет центральную роль в теории параметрической сложности. Задача является наиболее известной задачей и используется во многих случаях для показа трудноразрешимости задачи путём приведения её к задаче поиска доминирующего множества. В частности, задача не является (ФПР) в том смысле, что не существует алгоритма со временем работы 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 : .
• Abhay K. Parekh. Analysis of a greedy heuristic for finding small dominating sets in graphs // Information Processing Letters. — 1991. — Т. 39 , вып. 5 . — С. 237-240 . — doi : .

• Christos H. Papadimitriou, Mihailis Yannakakis. Optimization, Approximation, and Complexity Classes // Journal of Computer and Systems Sciences. — 1991. — Т. 43 , вып. 3 . — С. 425–440 . — doi : .
• Jochen Alber, Michael R Fellows, Rolf Niedermeier. Polynomial-time data reduction for dominating set // Journal of the ACM . — 2004. — Т. 51 , вып. 3 . — С. 363–384 . — doi : . .
• Robert B. Allan, Renu Laskar. On domination and independent domination numbers of a graph // Discrete Mathematics. — 1978. — Т. 23 , вып. 2 . — С. 73–76 . — doi : . .
• 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 : . .
• 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 : . .
• 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 : . .
• 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 : . .
• 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 : . .
• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — Москва: «Мир», 1982. — С. 235, Задача ТГ2.
• F. Grandoni. A note on the complexity of minimum dominating set // Journal of Discrete Algorithms. — 2006. — Т. 4 , вып. 2 . — С. 209–214 . — doi : . .
• S. Guha, S. Khuller. Approximation algorithms for connected dominating sets // . — 1998. — Т. 20 , вып. 4 . — С. 374–387 . — doi : . .
• 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 : . .
• Ralf Klasing, Christian Laforest. Hardness results and approximation algorithms of k-tuple domination in graphs // Information Processing Letters. — 2004. — Т. 89 , вып. 2 . — С. 75–83 . — doi : . .
• Viggo Kann. On the Approximability of NP-complete Optimization Problems // . PhD thesis. — Stockholm: Department of Numerical Analysis and Computing Science, , 1992. .
• R. Raz, S. Safra. Proc. 29th Annual ACM . — ACM, 1997. — С. –484. — ISBN 0-89791-888-6 . — doi : . .
• 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 : . .
• 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. — ( ). — doi : . .
• 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 : . .