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

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

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

Остов – это разреженный подграф данного неориентированного графа, сохраняющий приближенные расстояния между каждой парой вершин. Более точно, t-остов графа [math]\displaystyle{ G = (V, E)\, }[/math] представляет собой подграф [math]\displaystyle{ (V, E_{s}), 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], алгоритм последовательно добавляет ребра. Решение о том, добавлять ли некоторое ребро (скажем, [math]\displaystyle{ (u, v) \, }[/math]) к [math]\displaystyle{ E_{S} \, }[/math] или нет, принимается на основе следующего соображения:

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

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