Связное доминирующее множество: различия между версиями

Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется ''связным доминирующим множеством''. Связное доминирующее множество минимальной мощности называется ''минимальным связным доминирующим множеством'' (МСДМ). Вычисление МСДМ представляет собой NP-полную задачу, не имеющую аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ H(\Delta\ )</math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>, где H – гармоническая функция, а <math>\Delta\ </math> – максимальная степень исходного графа [10].

Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [22]. В последнее время ее актуальность значительно выросла в связи с применением в области беспроводных сетей, а именно – для построения виртуальных магистралей [4]. Гуха и Хуллер [10] предложили двухступенчатую схему «жадной» аппроксимации для нахождения минимального связного доминирующего множества в графах общего вида и показали, что ее коэффициент эффективности равен <math>3 + ln \Delta\ </math>, где <math>\Delta\ </math> – максимальная степень вершины в графе. Построению одноступенчатого жадного алгоритма подобной эффективности мешает трудность нахождения субмодулярной гармонической функции. Руан и коллеги [21] успешно разработали одноступенчатый алгоритм жадной аппроксимации с лучшим коэффициентом эффективности, <math>c + ln \Delta\ </math>, для любого c > 2. Дю и коллеги [6] показали, что существует аппроксимация с полиномиальным временем исполнения и коэффициентом эффективности <math>a(1 + ln \Delta\ )</math> для любого <math>a > 1 \; </math>. Важность этих работ заключается в том, что используемые в жадном алгоритме гармонические функции не являются субмодулярными.

Гуха и Хуллер [10] привели доказательство отрицательного результата, заключающегося в следующем: не существует аппроксимации с полиномиальным временем исполнения и коэффициентом эффективности <math>\rho\ ln \Delta\ </math> для <math>\rho\ < 1</math>, за исключением случая <math>NP \subseteq DTIME(n^{O(lnln n)})</math>. Как показано в [8], доминирующие множества не поддаются произвольно качественной аппроксимации, за исключением случаев, когда P почти равно NP. Эти результаты переносят фокус внимания с графов общего вида на графы единичных кругов, поскольку граф единичных кругов представляет собой базовую модель для беспроводных сенсорных сетей, и для графов единичных кругов построение МСДМ имеет аппроксимацию с полиномиальным временем исполнения и константным коэффициентом эффективности. Хотя этот константный коэффициент время от времени удается улучшить [1, 2, 19, 24], Чен и коллеги [5] поставили точку в этом вопросе, доказав существование аппроксимационной схемы с полиномиальным временем выполнения (PTAS) для графов единичных кругов. Это значит, что теоретически коэффициент эффективности для аппроксимационного алгоритма с полиномиальным временем выполнения может оказаться не выше <math>1 + \varepsilon\ </math> для любого положительного <math>\varepsilon\ </math>.

Дубхаши и коллеги [7] показали, что после построения доминирующего множества можно легко вычислить связное доминирующее множество при помощи распределенного алгоритма. Самое полное изложение результатов вычисления доминирующих множеств приведено в [18]. В частности, в этой работе простая константная аппроксимация доминирующих множеств графами единичных кругов. Аппроксимация с константным коэффициентом (связных) доминирующих множеств с минимальными весами для графов единичных кругов была исследована в [3]. Аппроксимационная схема с полиномиальным временем выполнения для задачи вычисления минимального доминирующего множества для графов единичных кругов была предложена в [20]. Кун и коллеги [14] доказали, что максимальное независимое множество (и, следовательно, доминирующее множество) можно вычислить за асимптотически оптимальное время O(log n) для графов единичных кругов и крупного класса ограниченных графов независимости. Люби [17] предложил элегантный локальный алгоритм для вычисления максимального независимого множества для графов общего вида с временем исполнения O(log n). Джиа и коллеги [11] предложили быструю распределенную аппроксимационную схему для вычисления доминирующего множества для графов общего вида с временем исполнения O(log n). Первый распределенный алгоритм для вычисления доминирующих множеств за константное время с нетривиальным коэффициентом аппроксимации для графов общего вида был приведен в [15]. Соответствующая нижняя граница <math>\Omega\ (log n) \; </math> считается классическим результатом для распределенного вычисления [16]. Получить аппроксимационную схему с полиномиальным временем выполнения для графов единичных кругов можно при помощи распределенного алгоритма [13]. Самый быстрый детерминистский распределенный алгоритм для вычисления доминирующих множеств на графах единичных кругов был приведен в [12], а самый быстрый рандомизированный распределенный алгоритм для них же – в [9].

Построение аппроксимационной схемы с полиномиальным временем выполнения для минимального связного доминирующего множества (МСДМ) базируется на факте существования схемы с полиномиальным временем исполнения и константным коэффициентом эффективности. Этот факт довольно легко обнаружить. Прежде всего, заметим, что единичный диск содержит не более пяти независимых вершин [2]. Из этого следует, что любое максимальное независимое множество имеет размер не более 1 + 4opt, где opt – размер МСДМ. Кроме того, каждое максимальное независимое множество является доминирующим множеством, и можно легко построить максимальное независимое множество с остовным деревом, состоящим из всех ребер длины 2. Все вершины этого остовного дерева образуют связное доминирующее множество размером не более 1 + 8opt. Благодаря улучшению верхней границы размера максимального независимого множества [25] и возможности соединения максимальных независимых множеств [19] значение константного коэффициента было улучшено до 6,8 для распределенного реализации алгоритма.

'''Теорема 1.''' Существует <math>(1 + \varepsilon\ )</math>-аппроксимация для построения минимального связного доминирующего множества в связных графах единичных кругов, время исполнения которой составляет <math>n^{O((1/ \varepsilon\ )log(1/ \varepsilon\ )^2)}</math>.

В общем случае топология беспроводной сенсорной сети представляет собой [[граф кругов]]; иначе говоря, каждая вершина ассоциируется с диском. Разные диски могут иметь различный размер. Ребро из вершины u в вершину v существует в том и только том случае, если диск u покрывает v. Виртуальная магистраль в графах кругов представляет собой подмножество вершин, порождающее [[сильно связный подграф]], такой, что каждая вершина, не принадлежащая к подмножеству, имеет входящее ребро из вершины подмножества, а также исходящее ребро, ведущее к вершине подмножества. Такая виртуальная магистраль может рассматриваться как связное доминирующее множество в графе кругов. Вопрос о том, существует ли аппроксимация с полиномиальным временем исполнения и константным коэффициентом эффективности, до сих пор остается открытым. Тай и коллеги [23] достигли в этом отношении определенных успехов.