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

[[Остов]] – это ''разреженный'' [[подграф]] данного [[неориентированный граф|неориентированного графа]], сохраняющий приближенные расстояния между каждой парой вершин. Более точно, 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).

Из этого напрямую следует, что подграф (V, E<math>_{S}</math>) будет t-остовом для G. Два алгоритма вычисления (2k–1)-остова способны вычислить множество E<math>_{S}</math> при помощи двух совершенно разных подходов.

== Алгоритм I ==

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

 

 

 

 

 

== Алгоритм II ==

 

 

== Вычисление 3-остова за линейное время ==

 

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

 

'''1. Формирование кластеров:'''

 

Выборка <math>R \subset V</math> выполняется посредством независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Кластеры будут сформированы вокруг этих выбранных вершин. Вначале кластеры представляют собой {{u}<math>\mid</math>u <math>\in </math>R}. Каждая вершина <math>u \in R</math> называется центром своего кластера. Каждая невыбранная вершина <math>v \in V - R</math> обрабатывается следующим образом:

 

(a) Если v не является смежной с какой-либо выбранной вершиной, то каждое ребро, инцидентное v, перемещается в E<math>_{S}</math>.

(b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего к v соседа из числа выбранных вершин (связи можно разрывать произвольным образом; однако ради удобства можно считать, что все веса различны.). Ребро (v , N(v, R)) и каждое инцидентное v ребро с весом, меньшим, чем у этого ребра, перемещаются в E<math>_{S}</math>. Затем вершина v добавляется в кластер с центром в N(v, R).

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

 

 

 

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

 

 

 

 

 

Пусть u и v принадлежат к одному кластеру с центром x <math>\in</math> R. Из первой фазы алгоритма следует, что существует путь из двух ребер u – x – v в остове, причем каждое из этих ребер не тяжелее ребра (u, v). (Этот факт дает обоснование для отбрасывания всех внутрикластерных ребер в конце первого этапа).

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

Очевидно, что ребро (u, v) была удалена из E’ на этапе 2; предположим, что она была удалена при обработке вершины u. Пусть вершина v входит в кластер с центром x <math>\in</math> R.

Пусть в начале второго этапа (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>. Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.

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

 

 

 

 

1. Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28,1167-1181 (1999)

 

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