Просмотр кода страницы Связное доминирующее множество

Связное доминирующее множество ([[Connected_dominating_set]])

Ключевые слова и синонимы: [[техники разбиения]]

== Постановка задачи ==

Рассмотрим граф 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].

Единичным диском называется диск с радиусом, равным единице. [[Граф единичных кругов]] ассоциирован с множеством единичных кругов на евклидовой плоскости. Каждая вершина является центром единичного диска. Между двумя вершинами u и v существует ребро в том и только том случае, если <math>|uv| \le 1</math>, где <math>|uv| \; </math> – евклидово расстояние между u и v. Это означает, что две вершины u и v связаны ребром в том и только том случае, если диск вершины u покрывает v, а диск v покрывает u.

Вычисление МСДМ для графа единичных кругов также является NP-полной задачей; однако можно построить неплохую аппроксимацию для ее решения; Чен и коллеги [5] представили для нее аппроксимационную схему с полиномиальным временем выполнения.

== История вопроса ==

Задача нахождения связного доминирующего множества исследовалась в теории графов много лет [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 для распределенного реализации алгоритма.

В этом построении главным образом используются техники неадаптивного разбиения и сдвига. В общем случае ход действий примерно таков: вначале квадрат, содержащий все вершины исходного графа единичных кругов, разделяется на решетку из небольших ячеек. Каждая из этих ячеек далее разбивается на две области – центральную и граничную. Центральная область состоит из точек, находящихся на расстоянии h от границы ячейки. Граничная область состоит из точек, расстояние от которых до границы ячейки составляет не более h + 1. Таким образом, эти области перекрываются. После этого минимальное объединение связных доминирующих множеств вычисляется в каждой ячейке для связных компонент центральной области ячейки. Основная задача состоит в том, чтобы доказать, что объединение всех таких минимальных объединений не превышает минимального связного доминирующего множества для всего графа. Для вершин, не принадлежащих к центральным областям, для вычисления доминирующего множества используется часть 8-аппроксимации, лежащая в граничных областях. Вместе с упоминавшимся ранее объединением она образует связное доминирующее множество для всего исходного графа единичных кругов. Перемещая решетку для получения разбиения по разным координатам, можно получить разбиение с граничной областью, имеющей очень малую верхнюю границу.

Приведем более детальное описание процесса построения.

Пусть дан исходный связный граф единичных кругов G = (V, E), располагающийся в квадрате <math>Q = \big\{ (x, y) | 0 \le x \le q, 0 \le y \le q \big\}\ </math>, где <math>q \le |V|</math>. Для построения приближенного решения с коэффициентом эффективности <math>1 + \varepsilon\ </math> для <math>\varepsilon\ > 0</math> выберем целое число <math>m = O((1/ \varepsilon\ )ln(1/ \varepsilon\ ))</math>. Пусть <math>p = \mathcal{b} q/m \mathcal{c} + 1</math>. Рассмотрим квадрат <math>\bar{Q} = \big\{ (x, y) | - m \le x \le mp, - m \le y \le mp \big\} </math>. Разобьем <math>\bar{Q}</math> на <math>(p + 1) \times (p + 1)</math> решеток таким образом, что каждая ячейка представляет собой квадрат <math>m \times m</math>, за исключением верхней и правой границ; следовательно, никакие две ячейки не перекрываются друг с другом. Обозначим это разбиение квадрата <math>\bar{Q}</math> как P(0) (см. рис.). В общем случае разбиение P(a) получается из P(0) в результате сдвига нижнего левого угла Q из точки (—m,—m) в точку (—m + a,—m+ a). Заметим, что в результате сдвига из P(0) в P(a) для <math>0 \le a \le m</math> квадрат Q оказывается покрыт разбиением.

[[Файл:CDS_1.jpg]]

Квадраты <math>Q \; </math> и <math>\bar{Q}</math>


Для каждой ячейки e (представляющей собой квадрат <math>m \times m</math>) <math>C_e(d) \; </math> обозначает множество точек в e, удаленных от границы на расстояние не менее d; <math>C_e(0) \; </math> представляет саму ячейку e. Обозначим <math>B_e(d) = C_e(0) - C_e(d) \; </math>. Зафиксируем положительное целое число <math>h = 7 + 3 \mathcal{b} log_2(4m^2/ \pi\ ) \mathcal{c} </math>. Назовем <math>C_e(h) \; </math> ''центральной областью'' ячейки e, а <math>B_e(h + 1) \; </math> – ''граничной областью'' ячейки e. Таким образом, центральная и граничная области каждой ячейки перекрываются на полосу единичной ширины.
 

Центральная область

Пусть <math>G_e(d) \; </math> обозначает часть исходного графа G, лежащую в области <math>C_e(d) \; </math>. Точнее говоря, <math>G_e(h) \; </math> представляет собой часть графа G, лежащую в центральной области e. <math>G_e(h) \; </math> может состоять из нескольких связных компонентов. Пусть <math>K_e \; </math> обозначает подмножество вершин <math>G_e(0) \; </math> с минимальной мощностью, таких, что для каждого связного компонента H области <math>G_e(h) \, </math> подмножество <math>K_e \; </math> содержит связную компоненту, являющуюся [[доминатор|доминатором]] H. Иными словами, <math>K_e \; </math> представляет собой минимальное объединение связных доминирующих множеств в <math>G(0) \; </math> для связных компонент <math>G_e(h) \; </math>.

Теперь обозначим за K(a) объединение <math>K_e \; </math> для e по всем ячейкам разбиения P(a). K(a) обладает двумя важными свойствами.


'''Лемма 1.''' K(a) можно вычислить за время <math>n^{O(m^2)} \; </math>.

'''Лемма 2.''' <math>|K^a| \le opt</math> для <math>0 \le a \le m - 1</math>.


Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины <math>\sqrt{2}/2</math> порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин <math>G_e(0) \; </math> имеет размер не более <math>( \mathcal{d} \sqrt{2m} \mathcal{e} )^2</math>. Следовательно, размер <math>K_e \; </math> составляет не более <math>3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2</math>, поскольку любое доминирующее множество в связном графе имеет остовное дерево с ребрами длиной не более 3. Предположим, что <math>G_e(0) \; </math> имеет <math>n_e \; </math> вершин. Тогда количество кандидатов для <math>K_e \; </math> составляет не более

<math>\sum_{k=0}^{3( \mathcal{d} \sqrt{2m} \mathcal{e} )^2} \binom{n_e}{k} = n_e^{O(m^2)}</math>


Следовательно, K(a) можно вычислить за время

<math>\sum_e n_e^{O(m^2)} \le \bigg( \sum_e n_e \bigg) ^{O(m^2)} = n^{O(m^2)}</math>


Доказательство истинности леммы 2 намного сложнее; его можно найти в [5].


Граничная область

Пусть F – связное доминирующее множество G, удовлетворяющее неравенству <math>|F| \le 8opt + 1</math>. Обозначим за F(a) подмножество F, лежащее в граничной области <math>B_a(h + 1) \; </math>. Поскольку построение F занимает полиномиальное время, необходимо рассмотреть только размер F(a).


'''Лемма 3.''' Положим <math>h = 7 + 3 \mathcal{b} log_2(4m^2/ \pi\ ) \mathcal{c} </math> и <math>\mathcal{b} m/(h + 1)\mathcal{c} \ge 32/ \varepsilon\ </math>. В таком случае имеется по меньшей мере половина <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math>, таких, что <math>|F(i(h + 1))| \le \varepsilon\ \cdot opt</math>.


Доказательство. Обозначим за <math>F_H(a) \; </math> подмножество вершин F(a) с расстоянием менее h + 1 от горизонтальной (и за <math>F_V(a) \; </math> - соответственно, от вертикальной) границы некоторой ячейки в P(a). Тогда <math>F(a) = F_H(a) \cup F_V(a)</math>. Более того, все <math>F_H(i(h+1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> являются непересекающимися. Следовательно,

<math>\sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F_H(i(h+1))| \le |F| \le 8opt</math>


Подобным же образом, все <math>F_V(i(h+1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> являются непересекающимися и 

<math>\sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F_V(i(h+1))| \le |F| \le 8opt</math>

Следовательно,

<math>\sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F(i(h+1))| \le \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} (|F_H(i(h+1))| + |F_V(i(h+1))|) \le 16opt</math>

Иначе говоря,

<math>\frac {1} {{\mathcal{b} m/(h + 1)\mathcal{c}}} \sum_{i=0}^{\mathcal{b} m/(h + 1)\mathcal{c} - 1} |F(i(h+1))| \le ( \varepsilon\ /2)opt</math>

Это означает, что по меньшей мере половина <math>F(i(h + 1)) \; </math> для <math>i = 0; 1, ... , \mathcal{b} m/(h + 1)\mathcal{c} - 1</math> удовлетворяет соотношению<math>|F(i(h + 1))| \le \varepsilon\ \cdot opt</math>. □


Окончательный результат
Теперь рассмотрим K(a) и F(a). Согласно леммам 2 и 3, существуют <math>a \in \big\{ 0, h + 1, ... , (\mathcal{b} m/(h + 1)\mathcal{c} - 1)(h + 1) \big\} </math>, такие, что
<math>|K(a) \cup F(a)| \le (1 + \varepsilon\ )opt</math>.


'''Лемма 4.''' Для <math>0 \le a \le m — 1</math>, <math>K(a) \cup F(a)</math> представляет собой связное доминирующее множество для исходного связного графа G.

Доказательство. Очевидно, что <math>K(a) \cup F(a)</math> является доминирующим множеством для исходного графа G. Его связность можно показать следующим образом. Заметим, что центральная и граничная области перекрываются на область шириной 1. Таким образом, для любого связного компонента H подграфа <math>G_e(h) \; </math>, у F(a) имеется вершина в H. Следовательно, F(a) должен иметь связь с любым связным доминирующим множеством для H, особенно с <math>D_H \; </math> в K(a). Это означает, что <math>D_H \; </math> восстанавливает связи с F, потерянные в результате отрезания части в H. Следовательно, связность <math>K(a) \cup F(a)</math> следует из связности F. □



Суммируя вышеприведенные положения, получаем следующий результат:


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

== Применение ==

Важной областью применения связных доминирующих множеств является построение виртуальных магистралей для беспроводных сетей, особенно для беспроводных сенсорных сетей [4]. Топология беспроводной сенсорной сети часто представляет собой граф единичных кругов.

== Открытые вопросы ==

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

== См. также ==
* ''[[Доминирующее множество]]
* ''[[Точные алгоритмы построения доминирующего множества]]
* ''[[Жадные алгоритмы покрытия множества]]
* ''[[Остовное дерево с максимальным количеством листьев]]

== Литература ==

1.	Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: ACM MOBIHOC, Lausanne, Switzerland, 09-11 June 2002

2.	Alzoubi, K.M., P.-J.Wan, Frieder, O.: New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks. In: HICSS35, Hawaii, January 2002

3.	Ambuhl, C., Erlebach, T., Mihalak, M., Nunkesser, M.: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs. In: LNCS, vol.4110, pp 3-14. Springer, Berlin (2006)

4.	Blum, J., Ding, M., Thaeler, A., Cheng, X.: Applications of Connected Dominating Sets in Wireless Networks. In: Du, D.-Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 329-369. Kluwer Academic (2004)

5.	Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42,202-208 (2003)
 
6.	Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.-J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 167-175. January 2008

7.	Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons. In: SODA, 2003, pp. 717-724

8.	Feige, U.: A Threshold of lnn for Approximating Set Cover. J.ACM 45(4) 634-652 (1998)

9.	Gfeller, B., Vicari, E.: A Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth-Bounded Graphs. In: PODC 2007

10.	Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374-387 (1998)

11.	Jia, L., Rajaraman, R., Suel, R.:An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In: PODC, Newport, Rhode Island, USA, August 2001

12.	Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast De terministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In: DISC, Cracow, Poland, September 2005

13.	Kuhn, F., Moscibroda, T., Nieberg,T., Wattenhofer, R.: Local Approximation Schemes for Ad Hoc and Sensor Networks. In: DIALM-POMC, Cologne, Germany, September 2005

14.	Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the Locality of Bounded Growth. In: PODC, Las Vegas, Nevada, USA, July 2005

15.	Kuhn, F., Wattenhofer, R.: Constant-Time Distributed Dominating Set Approximation. In: PODC, Boston, Massachusetts, USA, July 2003

16.	Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193-201 (1992)

17.	Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15,1036-1053 (1986)

18.	Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59-68(1995)

19.	Min, M., Du, H., Jia, X., Huang, X., Huang, C.-H., Wu, W.: Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J. Glob. Optim. 35, 111-119 (2006)

20.	Nieberg, T., Hurink, J.L.: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. LNCS, vol. 3879, pp. 296-306. Springer, Berlin (2006)

21.	Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325-330 (2004)

22.	Sampathkumar, E., Walikar, H.B.: The Connected Domination Number of a Graph. J. Math. Phys. Sci. 13,607-613 (1979)

23.	Thai, M.T., Wang F., Liu, D., Zhu, S., Du, D.-Z.: Connected Dominating Sets in Wireless Networks with Different Transmission Range. IEEE Trans. Mob. Comput. 6(7), 721-730 (2007)

24.	Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks. In: IEEE INFOCOM 2002

25.	Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H.: Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs. Theor. Comput. Sci. 352,1 -7 (2006)

[[Категория: Совместное определение связанных терминов]]