Введение
Подмножество узлов графа, такое что все остальные узлы связаны хотя бы с одним доминатором в графах потока управления.
Dominator in control flow graphs
В теории графов, доминирующим множеством для графа G является подмножество D его вершин, такое что любая вершина графа G либо принадлежит D, либо имеет соседа в D. Число доминирования γ(G) – это количество вершин в наименьшем доминирующем множестве для G.
Задача о доминирующем множестве заключается в проверке, выполняется ли условие γ(G) ≤ K для заданного графа G и входного параметра K; это классическая NP-полная задача в теории вычислительной сложности. Поэтому предполагается, что не существует эффективного алгоритма для вычисления γ(G) для всех графов G. Однако существуют эффективные алгоритмы аппроксимации, а также эффективные точные алгоритмы для определенных классов графов. Доминирующие множества представляют практический интерес в различных областях. В беспроводных сетях доминирующие множества используются для поиска эффективных маршрутов в мобильных ad hoc сетях. Они также применяются при создании кратких изложений документов и проектировании защищенных систем для электросетей.
Формальное определение
При ненаправленном графе 1=G = (V, E) подмножество вершин называется доминирующим множеством, если для каждой вершины v существует вершина u из этого подмножества, такая что (v, u) ∈ E.
Любой граф имеет хотя бы одно доминирующее множество: если D – множество всех вершин, то по определению D является доминирующим множеством, поскольку для каждой вершины A найдется вершина из D, удовлетворяющая условию. Более интересной задачей является поиск небольших доминирующих множеств. Число доминирования 1=G определяется как минимальный размер доминирующего множества: γ(G) = min{|D| : D – доминирующее множество}.
Доминирование независимых множеств
Число независимого доминирования iγ(G) графа G — это максимум по всем независимым множествам A графа G минимального множества, доминирующего над A. Доминирующие подмножества вершин могут требовать меньше вершин, чем доминирование всех вершин, поэтому iγ(G) ≤ γ(G) для всех графов G.
Неравенство может быть строгим: существуют графы G, для которых iγ(G) < γ(G). Например, для некоторого целого числа n пусть G — граф, вершины которого соответствуют строкам и столбцам доски размером n × n, и две вершины соединены тогда и только тогда, когда они пересекаются. Единственными независимыми множествами являются множества, состоящие только из строк, или множества, состоящие только из столбцов, и каждое из них может быть доминировано одной вершиной (столбцом или строкой), поэтому iγ(G) = 1. Однако для доминирования всех вершин требуется как минимум одна строка и один столбец, поэтому γ(G) = 2. Более того, отношение γ(G) / iγ(G) может быть сколь угодно большим. Например, если вершины G — это все подмножества клеток доски размером n × n, то все равно iγ(G) = 1, но γ(G) = n.
Бинезависимое число доминирования iγi(G) графа G — это максимум по всем независимым множествам A графа G минимального независимого множества, доминирующего над A. Для любого графа G выполняются следующие соотношения:
История
Проблема доминирования изучалась начиная с 1950-х годов, но интенсивность исследований в области доминирования значительно возросла в середине 1970-х годов. В 1972 году Ричард Карп доказал, что задача о покрытии множества является NP-полной. Это имело немедленные последствия для задачи о доминирующем множестве, поскольку существуют прямые биекции между вершинами и множествами, а также между ребрами и непересекающимися пересечениями для обеих задач. Это доказало, что задача о доминирующем множестве также является NP-полной.
Алгоритмы и вычислительная сложность
Проблема покрытия множества – хорошо известная NP-трудная задача, и задача принятия решения о покрытии множества была одной из 21 NP-полных задач Карпа. Существует пара полиномиальных L-редукций между задачей о минимальном доминирующем множестве и задачей о покрытии множества. Эти редукции (см. ниже) показывают, что эффективный алгоритм для задачи о минимальном доминирующем множестве предоставит эффективный алгоритм для задачи о покрытии множества, и наоборот. Более того, редукции сохраняют коэффициент аппроксимации: для любого α, полиномиальный α-аппроксимационный алгоритм для минимальных доминирующих множеств предоставит полиномиальный α-аппроксимационный алгоритм для задачи о покрытии множества, и наоборот. Обе задачи, на самом деле, Log APX-полны. Аппроксимируемость покрытия множества также хорошо изучена: логарифмический коэффициент аппроксимации может быть найден с помощью простого жадного алгоритма, а поиск сублогарифмического коэффициента аппроксимации является NP-трудным. В частности, жадный алгоритм обеспечивает аппроксимацию коэффициента минимального доминирующего множества, и ни один полиномиальный алгоритм не может достичь коэффициента аппроксимации лучше, чем для некоторого c > 0, если P = NP.
L-уменьшения
Следующие два приведения показывают, что задача о минимальном доминирующем множестве и задача о покрытии множества эквивалентны посредством L-приведений: имея экземпляр одной задачи, можно построить эквивалентный экземпляр другой задачи.
От доминирующего набора к покрытию набора
Если дан граф G = (V, E) с V = {1, 2, ..., n}, постройте экземпляр задачи о покрытии множества (U, S) следующим образом: вселенная U равна V, а семейство подмножеств состоит из вершины v и всех вершин, смежных с v в G.
Now if D is a dominating set for G, then is a feasible solution of the set cover problem, with Conversely, if is a feasible solution of the set cover problem, then D is a dominating set for G, with
Hence the size of a minimum dominating set for G equals the size of a minimum set cover for (U, S). 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 α approximation algorithm for set covering provides an efficient α approximation algorithm for minimum dominating sets. For example, given the graph G shown on the right, we construct a set cover instance with the universe 1=U = {1, 2, , 6} and the subsets and In this example, 1=D = {3, 5} is a dominating set for G – this corresponds to the set cover For example, the vertex 4 ∈ V is dominated by the vertex 3 ∈ D, and the element 4 ∈ U is contained in the set .
Теперь, если D является доминирующим множеством для G, то S является допустимым решением задачи о покрытии множества, с чего следует, что |D| = |S|. И наоборот, если S является допустимым решением задачи о покрытии множества, то D является доминирующим множеством для G, с чего следует, что |D| = |S|.
Now if D is a dominating set for G, then is a feasible solution of the set cover problem, with Conversely, if is a feasible solution of the set cover problem, then D is a dominating set for G, with
Hence the size of a minimum dominating set for G equals the size of a minimum set cover for (U, S). 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 α approximation algorithm for set covering provides an efficient α approximation algorithm for minimum dominating sets. For example, given the graph G shown on the right, we construct a set cover instance with the universe 1=U = {1, 2, , 6} and the subsets and In this example, 1=D = {3, 5} is a dominating set for G – this corresponds to the set cover For example, the vertex 4 ∈ V is dominated by the vertex 3 ∈ D, and the element 4 ∈ U is contained in the set .
Следовательно, размер минимального доминирующего множества для G равен размеру минимального покрытия множества для (U, S). Кроме того, существует простой алгоритм, который отображает доминирующее множество в покрытие множества того же размера и наоборот. В частности, эффективный α-аппроксимационный алгоритм для задачи о покрытии множества предоставляет эффективный α-аппроксимационный алгоритм для поиска минимального доминирующего множества. Например, для графа G, показанного справа, мы строим экземпляр задачи о покрытии множества с вселенной U = {1, 2, ..., 6} и подмножествами S. В этом примере D = {3, 5} является доминирующим множеством для G – это соответствует покрытию множества S. Например, вершина 4 ∈ V доминируется вершиной 3 ∈ D, и элемент 4 ∈ U содержится в множестве из S.
Now if D is a dominating set for G, then is a feasible solution of the set cover problem, with Conversely, if is a feasible solution of the set cover problem, then D is a dominating set for G, with
Hence the size of a minimum dominating set for G equals the size of a minimum set cover for (U, S). 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 α approximation algorithm for set covering provides an efficient α approximation algorithm for minimum dominating sets. For example, given the graph G shown on the right, we construct a set cover instance with the universe 1=U = {1, 2, , 6} and the subsets and In this example, 1=D = {3, 5} is a dominating set for G – this corresponds to the set cover For example, the vertex 4 ∈ V is dominated by the vertex 3 ∈ D, and the element 4 ∈ U is contained in the set .
Особые случаи
Если граф имеет максимальную степень Δ, то жадный алгоритм приближения находит O(log Δ)-приближение минимального доминирующего множества. Кроме того, пусть |D| – кардинальность доминирующего множества, полученного с помощью жадного приближения, тогда выполняется следующее соотношение: |D| ≤ N√(2M), где N – число вершин, а M – число ребер в заданном неориентированном графе. Для фиксированного Δ это соответствует требованиям к доминирующему множеству для включения в класс APX; фактически, задача APX-полна. Для специальных случаев, таких как графы единичных дисков и планарные графы, существует полиномиальная схема аппроксимации времени (PTAS). Минимальное доминирующее множество можно найти за линейное время в графах, являющихся сериями и параллельными соединениями.
Точные алгоритмы
Минимальный доминирующий набор графа с n вершинами может быть найден во времени, просматривая все подмножества вершин. Показано, как найти минимальное доминирующее множество во времени и экспоненциальном пространстве, а также во времени и полиномиальном пространстве. Более быстрый алгоритм, использующий время, был найден И. Ф. Ленноном, который также показал, что количество минимальных доминирующих множеств может быть вычислено за это время. Количество минимальных доминирующих множеств не превышает , и все такие множества могут быть перечислены во времени .
Параметризированная сложность
Поиск доминирующего множества размера k играет центральную роль в теории параметризованной сложности. Это наиболее известная задача, являющаяся полной для класса W[2] и используемая во многих сведенииях для доказательства неразрешимости других задач. В частности, задача не является фиксированно-параметрически разрешимой, то есть не существует алгоритма со временем работы для некоторой функции f, если иерархия W не схлопнется до FPT=W[2]. С другой стороны, если входной граф планарный, задача остаётся NP-трудной, но известен алгоритм с фиксированными параметрами. Фактически, задача имеет ядро линейного размера относительно k, и время работы, экспоненциальное относительно и кубическое относительно n, может быть получено применением динамического программирования к разложению по ветвям этого ядра. В более общем случае, задача о доминирующем множестве и многие её варианты фиксированно-параметрически разрешимы при параметризации как по размеру доминирующего множества, так и по размеру наименьшего запрещённого полного двудольного подграфа; то есть задача является FPT на графах, не содержащих биклики, что представляет собой очень общий класс разреженных графов, включающий в себя планарные графы. Дополнительное множество к доминирующему множеству, неблокирующий набор, может быть найдено алгоритмом с фиксированными параметрами на любом графе.