Алгоритмы поиска остова во взвешенном графе

Ключевые слова и синонимы: графовые алгоритмы; рандомизированные алгоритмы; кратчайший путь; остов

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

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

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

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

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

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

Алгоритм I

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

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

Из этого следует, что P[math]\displaystyle{ _{t} }[/math](x, y) будет выполняться для каждой дуги E, не входящей в E[math]\displaystyle{ _{S} }[/math], так что в конце концов подграф (v, E[math]\displaystyle{ _{S} }[/math]) будет представлять собой t-остов. Хорошо известное утверждение элементарной теории графов гласит, что граф с более чем [math]\displaystyle{ n^{1+\frac{1}{k}} }[/math] дугами должен содержать цикл длиной не более 2k. Из приведенного выше алгоритма следует, что длина любого цикла в подграфе (V, E[math]\displaystyle{ _{S} }[/math]) должна составлять не менее t + 1. Следовательно, для t = 2k – 1 количество дуг в подграфе (V, E[math]\displaystyle{ _{S} }[/math]) будет менее [math]\displaystyle{ n^{1+\frac{1}{k}} }[/math]. Таким образом, Алгоритм I вычисляет (2k–1)-остов размера [math]\displaystyle{ O(n^{1+\frac{1}{k}}) }[/math], что является оптимальным, с учетом вышеупомянутой нижней границы.

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

Алгоритм II

Алгоритм выполняет оригинальную кластеризацию на основе сверхлокального подхода и устанавливает следующий результат для задачи нахождения остова.

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

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

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

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

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

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

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

(a) Если v не является смежной с какой-либо выбранной вершиной, то каждая дуга, инцидентная v, перемещается в E[math]\displaystyle{ _{S} }[/math]. (b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего к v соседа из числа выбранных вершин (Связи можно разрывать произвольным образом; однако ради удобства можно считать, что все веса различны.). Дуга (v , N(v, R)) и каждая инцидентная v дуга с весом, меньшим, чем у этой дуги, перемещаются в E[math]\displaystyle{ _{S} }[/math]. Затем вершина v добавляется в кластер с центром в N(v, R). На последнем шагу первого этапа все дуги (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются.

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

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

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

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

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

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

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

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

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

Пусть в начале второго этапа (u, v’) [math]\displaystyle{ \in }[/math] E’ будет дугой с наименьшим весом среди всех дуг, инцидентных u, от вершин кластера с центром в x. Таким образом, должно выполняться weight(u, v’) ≤ weight(u, v). Обработка вершины u на втором этапе алгоритма гарантирует, что дуга (u, v’) добавляется в E[math]\displaystyle{ _{S} }[/math]. Следовательно, существует путь Π[math]\displaystyle{ _{uv} }[/math] = u – v’ – x – v между u и v в остове E[math]\displaystyle{ _{S} }[/math], и его вес ограничен weight(Π[math]\displaystyle{ _{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]\displaystyle{ _{S} }[/math]) имеет коэффициент растяжения 3. Кроме того, обе фазы алгоритма могут быть исполнены за время O(m) с использованием элементарных структур данных и блочной сортировки. Алгоритм вычисления (2k–1)-остова исполняет k итераций, причем каждая итерация напоминает первый этап алгоритма нахождения 3-остова. Детали и формальное доказательство можно найти в [6].

Родственные работы

Понятие остова в обобщенном виде исследовалось во многих работах.

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

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

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

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

Литература

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. Comput. Mach. 32(4), 804-823 (1985)

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