Алгоритмы поиска остова во взвешенном графе: различия между версиями

[[Остов]] – это ''разреженный'' [[подграф]] данного [[неориентированный граф|неориентированного графа]], сохраняющий приближенные расстояния между каждой парой вершин. Более точно, t-остов графа <math>G = (V, E)\, </math> представляет собой подграф <math>(V, E_{s}), E_{s} \subseteq E \, </math>, такой, что для любой пары вершин расстояние между ними в подграфе не более чем в t раз больше расстояния между ними в исходном графе; при этом t называется [[коэффициент растяжения|коэффициентом растяжения]]. Формальное определение остовам дали Пелег и Шеффер [14], хотя связанные с ними понятия неявно использовал Авербух [3] в контексте сетевых синхронизаторов.

Вычисление t-остова наименьшего размера для заданного графа представляет собой важную комбинаторную задачу с множеством вариантов применения. Однако вычисление t-остова наименьшего размера для графа является NP-полной задачей. Фактически (для значений t > 2) NP-полной [10] является даже задача аппроксимации минимального размера t-остова для графа с коэффициентом O(2<math>^{(1-\mu ) ln \; n)}\, </math>) для любого <math>\mu</math> > 0. Осознав этот факт, исследователи предпочли двинуться в другом направлении, которое оказалось интересным и полезным. Пусть <math>S_{G}^{t}\, </math> – размер наиболее разреженного t-остова графа G, а <math>S_{n}^{t}\, </math> – максимальное значение <math>S_{G}^{t}\, </math> среди всех возможных графов с n вершинами. Существует ли алгоритм с полиномиальным временем выполнения, который для любого взвешенного графа и параметра t вычисляет его t-остов размера <math>O(S_{G}^{t})\, </math>? Такой алгоритм был бы лучшим из того, на что мы могли бы надеяться, учитывая сложность исходной задачи t-остова. Возникает естественный вопрос: насколько велико может быть значение <math>S_{G}^{t}\, </math>? Из высказанной Эрдосом [12] 43 года назад гипотезы о нижней границе обхвата следует, что существуют графы с n вершинами, для которых 2k-остов и (2k–1)-остов состоят из <math>\Omega (n^{1+\frac{1}{k}}) \, </math> ребер. Эта гипотеза была доказана для k = 1, 2, 3 и 5. Заметим, что (2k–1)-остов является также и 2k-остовом, а нижняя граница размера одинакова для 2k-остова и (2k–1)-остова. Таким образом, задача заключается в разработке алгоритма, который для любого взвешенного графа с n вершинами вычисляет (2k–1)-остов размера <math>O(n^{1+\frac{1}{k}}) \, </math>. Разумеется, хотелось бы найти самый быстрый алгоритм решения этой задачи, а наиболее амбициозная цель заключается в нахождении алгоритма линейной сложности.

В данной статье представлены два простейших алгоритма, вычисляющих (2k–1)-остов заданного взвешенного графа G = (V, E). Пусть n и m – число вершин и ребер графа G, соответственно. Первый алгоритм, разработанный Альтхофером и коллегами [2], основан на [[жадный алгоритм|жадной стратегии]] и выполняется за время <math>O(mn^{1+\frac{1}{k}})</math>. Второй алгоритм [6] основан на сверхлокальном подходе, он выполняется за время O(km). Для начала рассмотрим следующее простое наблюдение. Предположим, что имеется подмножество <math>E_{s} \in E</math>, такое, что для каждого ребра <math>(x, y) \in E \setminus E_{s}</math> выполняется следующее утверждение.

P<math>_{t}</math>(x, y): вершины x и y связаны в подграфе (V, E<math>_{S}</math>) путем, состоящим из не более чем t ребер, причем вес каждого ребра на этом пути не превышает вес ребра (x, y).

Этот алгоритм выбирает ребра для остова по принципу жадности; он напоминает алгоритм Крускала для вычисления минимального остовного дерева. Ребра графа обрабатываются в порядке возрастания их весов. Начиная с остова <math>E_{S} = \varnothing</math>, алгоритм последовательно добавляет ребра. Решение о том, добавлять ли некоторое ребро (скажем, <math>(u, v) \, </math>) к <math>E_{S} \, </math> или нет, принимается на основе следующего соображения:

''Если расстояние между u и v в подграфе, индуцированном текущими ребрами остова <math>E_{S} \, </math>, больше, чем t-weight(M, v), то ребро (u, v) следует добавить к to <math>E_{S} \, </math>, в противном случае отбросить.''

 

 

Простая реализация Алгоритма I размера <math>O(mn^{1+\frac{1}{k}})</math> разработана на базе алгоритма Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем выполнения – <math>O(kmn^{\frac{1}{k}})</math>. Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени выполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени выполнения.

Пусть даны взвешенный граф G = (V, E) и целое число k > 1. Остов с коэффициентом растяжения (2k–1) и размером <math>O(kn^{1+\frac{1}{k}})</math> может быть вычислен за время O(km).

Алгоритм выполняется в O(k) этапов; на каждом этапе он вычисляет список смежности для каждой вершины с целью отсечения необязательных ребер. Для доказательства простоты алгоритма далее приводятся его полная версия для нахождения 3-остова и анализ алгоритма. Алгоритм может быть легко адаптирован к другим вычислительным моделям (с параллельной, внешней или распределенной памятью) с сохранением почти оптимальной производительности (подробнее см. в [6]).

Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> ребер. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их ребра могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на [[доминирующее множество|доминирующих множествах]].

 

Вначале имеется множество ребер E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает ребра E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа.

 

 

На последнем шагу первого этапа все ребра (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются.

Пусть V’ – множество вершин, соответствующих конечным точкам ребер E’, оставшимся после завершения первого этапа. Из этого следует, что каждая вершина из V’ является либо вершиной из выборки, либо смежной с одной из таких вершин, и этап 1(b) разбивает V' на непересекающиеся кластеры, в центре каждого из которых находится некоторая вершина из выборки. Заметим, что вследствие последнего этапа каждое ребро в множестве E’ является внутрикластерным ребром. Граф (V’, E’) т соответствующее разбиение V’ на кластеры передается на вход следующего (второго) этапа.

 

'''2. Соединение вершин с соседними кластерами:'''

Пусть E’(v, c) – ребра из множества E’, инцидентные v, из кластера c. Для каждого кластера c, являющегося соседом v, ребро из E’(v, c) с наименьшим весом перемещается в E<math>_{S}</math>; остальные ребра отбрасываются.

Количество ребер, добавленных к остову E<math>_{S}</math> за время выполнения описанных этапов алгоритма, можно ограничить следующим образом. Заметим, что множество выборки R формируется путем случайного и независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Из элементарной вероятности следует, что для каждой вершины <math>v \in V</math> ожидаемое количество инцидентных ей ребер с весами меньше, чем у (v, N (v, R)), не превосходит <math>\sqrt{n}</math>. Таким образом, ожидаемое количество ребер, вносимых в остов каждой вершиной на первом этапе алгоритма, не превосходит <math>\sqrt{n}</math>. Количество ребер, добавленных к остову на второй фазе, составляет O(n<math>\mid</math>R<math>\mid</math>). Поскольку ожидаемый размер выборки R равен <math>\sqrt{n}</math>, следовательно, ожидаемое количество ребер, добавленных к остову на второй фазе, составляет не более n<math>^{3/2}</math>. Следовательно, ожидаемый размер остова E<math>_{S}</math> по окончании работы Алгоритма II в вышеописанном виде не превосходит 2n<math>^{3/2}</math>. Алгоритм выполняется повторно, если размер остова превосходит 3n<math>^{3/2}</math>. Из неравенства Маркова следует, что ожидаемое количество таких повторений будет составлять O(1).

Установим теперь, что E<math>_{S}</math> является 3-остовом. Заметим, что для каждого ребра edge (u, v) <math>\notin</math> E<math>_{S}</math>, вершины u и v на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев.

''Случай 1: (u и v принадлежат к одному кластеру)''

 

 

 

Пусть в начале второго этапа (u, v’) <math>\in</math> E’ будет ребром с наименьшим весом среди всех ребер, инцидентных u, от вершин кластера с центром в x. Таким образом, должно выполняться weight(u, v’) ≤ weight(u, v). Обработка вершины u на втором этапе алгоритма гарантирует, что ребро (u, v’) добавляется в E<math>_{S}</math>. Следовательно, существует путь Π<math>_{uv}</math> = u – v’ – x – v между u и v в остове E<math>_{S}</math>, и его вес ограничен weight(Π<math>_{uv}</math>) = weight(u, v’) + weight(v’, x) + weight(x, v). Поскольку (v’, x) и (v, x) были выбраны на первом этапе, должно выполняться weight(v’, x) ≤ weight(u, v’) и weight(x, v) ≤ weight(u, v). Отсюда следует, что остов (v, E<math>_{S}</math>) имеет коэффициент растяжения 3. Кроме того, обе фазы алгоритма могут быть выполнены за время O(m) с использованием элементарных структур данных и блочной сортировки.

 

Алгоритм вычисления (2k–1)-остова выполняет k итераций, причем каждая итерация напоминает первый этап алгоритма нахождения 3-остова. Детали и формальное доказательство можно найти в [6].

 

''Аддитивные остовы'': описанный выше t-остов аппроксимирует попарные расстояния с мультипликативной ошибкой; его мы будем называть ''мультипликативным остовом''. Аналогичным образом можно определить остов, аппроксимирующий попарные расстояния с аддитивной ошибкой. Такой остов называется аддитивным остовом, а соответствующая ошибка носит название ''избытка''. Эйнгворт и коллеги [1] представили первый аддитивный остов размера O(n<math>^{3/2 log n}</math>) с избытком 2. Босуана и коллеги [7] представили алгоритм построения аддитивного остова размера O(n<math>^{4/3}</math>) с избытком 6. До сих пор остается открытым вопрос, существуют ли более разреженные аддитивные остовы.

 

 

''(α,β)-остов'': Элкин и Пелег [11] ввели понятие ''(α,β)-остова'' для невзвешенных графов, который можно рассматривать как гибрид мультипликативного и аддитивного остовов. (α,β)-остов представляет собой подграф, такой, что расстояние между любыми двумя вершинами u, v <math>\in</math> V в этом подграфе ограничено αδ(u, v) + β, где δ(u, v) – расстояние между вершинами u и v в исходном графе. Элкин и Пелег показали, что (1+ε, β)-остов размера O(βn<math>^{1+ \delta}</math>) для произвольно малых ε, δ > 0 может быть вычислен за счет достаточно большого значения избытка β. Недавно Торуп и Цвик [19] разработали остов с аддитивной ошибкой, сублинейной относительно аппроксимируемого расстояния.

 

 

Среди других интересных вариантов остовов – ''остов с сохранением расстояния'', предложенный Боллобасом и коллегами [8], и ''легковесный остов'', предложенный Авербухом и коллегами [4]. Подграф называется d-хранителем, если он сохраняет точные расстояния между каждой парой вершин, разделенных расстоянием не менее d. Легковесный остов стремится минимизировать количество ребер и полный вес ребер. Параметр «''легкость''» определяется для подграфа как отношение полного веса всех его ребер к весу минимального остовного дерева графа. Авербух и коллеги [4] показали, что для любого взвешенного графа и целого числа k > 1 существует O(k)-остов с <math>O(k \rho n^{l+\frac{1}{k}})</math> ребрами и легкостью <math>O(k \rho n^{\frac{1}{k}})</math>, где <math>\rho\ </math> = log(Diameter), который можно построить за полиномиальное время.

 

 

В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера <math>O(n^{\frac{3}{2}})</math> и 3-остов размера O(n log n). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем выполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время <math>O(n log n + \frac{n}{\epsilon^{d}})</math>. Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.

Остовы исключительно полезны для многих приложений в таких областях, как распределенные системы и коммуникационные сети. В этих приложениях остовы являются основной графовой структурой. Для построения компактных таблиц маршрутизации [16] многие существующие алгоритмы маршрутизации используют ребра разреженного остова для маршрутизации сообщений. В распределенных системах остовы играют важную роль при разработке ''синхронизаторов''. Авербух [3] и Пелег и Ульман [15] показали, что качество остова (выражаемое в терминах коэффициента растяжения и количества ребер остова) тесно связано с временем и коммуникационной сложностью любого синхронизатора сети. Остовы также могут неявно использоваться во множестве алгоритмов для вычисления всех пар аппроксимированных кратчайших путей [5, 9, 18]. Примеры других приложений можно найти в работах [2, 3, 14, 16].

Время выполнения и размер (2k–1)-остова, вычисляемого Алгоритмом II, отличаются в k раз от соответствующих нижних границ для худшего случая. Для любого константного значения k оба эти параметра являются оптимальными. Однако для экстремального значения k, а именно – для k = log n, имеется отклонение с коэффициентом log n. Возможно ли избавиться от этого мультипликативного множителя k ко времени выполнения алгоритма и/или размеру вычисляемого (2k–1)-остова? Представляется, что для решения этой задачи могут быть полезны более тщательный анализ и передовые теоретико-вероятностные инструменты.

 

2. Althofer, I., Das, G., Dobkin, D.P.,Joseph, D., Soares J.:On sparse  spanners of weighted graphs. Discret. Comput. Geom. 9, 81-100(1993)

 

3. Awerbuch, B.: Complexity of network synchronization. J. Assoc.

 

4. Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and lightweight spanners. Tech. Report CS92-22, Weizmann Institute of Science (1992)

 

5. Awerbuch, B., Berger, B., Cowen, L., Peleg D.: Near-linear time construction of sparse neighborhood covers. SIAM J. Comput. 28,263-277(1998)

 

6. Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30, 532-563 (2007)

 

7. Baswana, S., Telikepalli, K., Mehlhorn, K., Pettie, S.: New construction of (a, /J)-spanners and purely additive spanners. In: Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 672-681

 

8. Bollobas, B., Coppersmith, D., Elkin M.: Sparse distance preserves and additive spanners. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 414-423

 

9. Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput. 28,210-236 (1998)

 

10. Elkin, M., Peleg, D.: Strong inapproximability of the basic k-spanner problem. In: Proc. of 27th International Colloquim on Automata, Languages and Programming, 2000, pp. 636-648

 

11. Elkin, M., Peleg, D.: (1 + e,/J)-spanner construction for general graphs. SIAM J. Comput. 33,608-631 (2004)

 

12. Erdos, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pp. 29-36. Publ. House Czechoslovak Acad. Sci., Prague (1964)

 

13. Halperin, S., Zwick, U.: Linear time deterministic algorithm for computing spanners for unweighted graphs. Unpublished manuscript (1996)

 

14. Peleg, D., Schaffer, A.A.: Graph spanners. J. Graph Theory 13, 99-116(1989)

 

15. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18, 740-747 (1989)

 

16. Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. Assoc. Comput Mach. 36(3), 510-530 (1989)

 

17. Salowe,  J.D.:  Construction  of  multidimensional  spanner graphs, with application to minimum spanning trees. In: ACM Symposium on Computational Geometry, 1991, pp. 256-261

 

18. Thorup, M., Zwick, U.: Approximate distance oracles. J. Assoc. Comput. Mach. 52,1-24 (2005)

 

19. Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 802-809