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

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

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

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

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

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

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

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

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

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

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

Основные результаты

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

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

Квадраты [math]\displaystyle{ Q \; }[/math] и [math]\displaystyle{ \bar{Q} }[/math]

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

Пусть дан исходный связный граф единичных дисков G = (V, E), располагающийся в квадрате Q = f(x, y) j 0 < x < q; 0 < y < qg, где q < jVj. Для построения приближенного решения с коэффициентом эффективности 1 + " для " > 0 выберем целое число m = O((1/")ln(1/")). Пусть p = bq/mc + 1. Рассмотрим квадрат Q = f(x, y) \ — m < x < mp; —m < y < mpg. Разобьем Q на (p + 1) x (p + 1) решеток таким образом, что каждая ячейка представляет собой квадрат m x m, за исключением верхней и правой границ; следовательно, никакие две ячейки не перекрываются друг с другом. Обозначим это разбиение квадрата Q как P(0) (рис. 1). В общем случае разбиение P(a) получается из P(0) в результате сдвига нижнего левого угла Q из точки (—m,—m) в точку (—m + a,—m+ a). Заметим, что в результате сдвига из P(0) в P(a) для 0 < a < m квадрат Q оказывается покрыт разбиением.

Для каждой ячейки e (представляющей собой квадрат m x m) Ce(d) обозначает множество точек в e, удаленных от границы на расстояние не менее d; Ce(0) представляет саму ячейку e. Обозначим Be(d) = Ce(0) - Ce(d). Зафиксируем положительное целое число h = 7 + 3[log2(4m2/7r)J. Назовем Ce(h) центральной областью ячейки e, а Be(h + 1) – граничной областью ячейки e. Таким образом, центральная и граничная области каждой ячейки перекрываются на полосу единичной ширины.

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

Пусть Ge(d) обозначает часть исходного графа G, лежащую в области Ce(d). Точнее говоря, Ge(h) представляет собой часть графа G, лежащую в центральной области e. Ge(h) может состоять из нескольких связных компонентов. Пусть Ke обозначает подмножество вершин Ge(0) с минимальной мощностью, таких, что для каждого связного компонента H области Ge(h) Ke содержит связную компоненту, являющуюся доминатором H. Иными словами, Ke представляет собой минимальное объединение связных доминирующих множеств в G(0) для связных компонент Ge(h). Теперь обозначим за K(a) объединение Ke для e по всем ячейкам разбиения P(a). K(a) обладает двумя важными свойствами.

Лемма 1. K(a) можно вычислить за время nO(m 2

Лемма 2. jKaj < opt для 0 < a < m - 1.

Справедливость леммы 1 показать несложно. Заметим, что вершины квадрата со сторонами длины p2/2 порождают полный подграф, в котором каждая вершина доминирует все остальные вершины. Из этого следует, что минимальное доминирующее множество для вершин Ge(0) имеет размер не более (dp2me)2. Следовательно, размер Ke составляет не более 3(d p2me)2, поскольку любое доминирующее множество в связном графе имеет остовное дерево с дугами длиной не более 3. Предположим, что Ge(0) имеет ne вершин. Тогда количество кандидатов для Ke составляет не более £ V) ■

Следовательно, K(a) можно вычислить за время O(m2) e e e Доказательство истинности леммы 2 намного сложнее; его можно найти в [5].

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

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

Лемма 3. Положим h = 7 + 3\}og2(4m2/n)\ и bm/(h + 1)c > 32/". В таком случае имеется по меньшей мере половина i = 0; 1, ... , bm/(h+ 1)J – 1, таких, что jF(i(h + 1))j < " • opt.

Доказательство. Обозначим за FH(A) (FV(a)) подмножество вершин F(a) с расстоянием менее h + 1 от горизонтальной (вертикальной) границы некоторой ячейки в P(a). Тогда

F(a) = FH(a) [ FV(a). Более того, все FH(i(h+1)) i = 0;1,..., bm/(h + 1)J — 1 являются непересекающимися. Следовательно, E i=0 jFH(i(h

< \F\ < 8opt.

для

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

Теорема 1. Существует (1 + ")-аппроксимация для построения минимального связного доминирующего множества в связных графах единичных дисков, время исполнения которой составляет 2

Подобным же образом, все FV(i(h + 1)) for i = 0;1,..., bm/(h + 1)J - 1 являются непересекающимися и jFV(i(h + 1))| < Fj < 8opt : i=0

Таким образом, i=0 i=0 < 16opt : 1

Это значит, что \mlQi

l))\<(e/2)opt.

i=0

Это означает, что по меньшей мере половина F(i(h + 1)) для i = 0; 1; bm/(h + 1)J - 1 удовлетворяют соотношению \F(i(h+l))\<s-opt. □

Окончательный результат

Теперь рассмотрим K(a) и F(a). Согласно леммам 2 и 3, существуют 2 f0;h+ 1, ... , (bm/(h + 1)J - 1)(h + 1)g, такие, что jK(a)[F(a)j < (1 + ")opt:

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

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

Применение

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

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

В общем случае топология беспроводной сенсорной сети представляет собой граф дисков; иначе говоря, каждая вершина ассоциируется с диском. Разные диски могут иметь различный размер. Дуга из вершины 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)