Полностью динамическая связность: верхняя и нижняя границы

Ключевые слова и синонимы

динамически связные компоненты; динамические остовные леса

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

Задача заключается в эффективной поддержке информации о связности в динамически меняющемся графе. Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким, как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление.

В задаче полностью динамической связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке:

Connected(u, v): возвращает значение «истинно», если вершины u и v принадлежат к одной и той же связной компоненте графа, в противном случае возвращает значение «ложно».

Insert(x, y): вставляет новое ребро между вершинами x и y.

Delete(x, y): удаляет ребро между вершинами x и y.

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

Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [11]: алгоритм, разработанный Холмом, де Лихтенбергом и Торупом, отвечает на вопрос о связности за время [math]\displaystyle{ O(log \; n/log \; log \; n) }[/math] в наихудшем случае и поддерживает вставку и удаление ребер за амортизированное время [math]\displaystyle{ O(log^2 n \; ) }[/math].

Алгоритм поддерживает остовный лес F на динамически меняющемся графе G. Ребра в F называются древесными ребрами. Пусть e – древесное ребро леса F; пусть T – дерево из F, содержащее это ребро. При удалении ребра e деревья [math]\displaystyle{ T_1 }[/math] и [math]\displaystyle{ T_2 }[/math], полученные из T в результате удаления e, могут быть связаны вновь в том и только том случае, если существует недревесное ребро в G, одна конечная точка которого располагается в [math]\displaystyle{ T_1 }[/math], а другая – в [math]\displaystyle{ T_2 }[/math]. Такое ребро называется ребром замены для e. Иными словами, если имеется ребро замены для e, T восстанавливает связность при помощи этого ребра замены; в противном случае удаление e создает новую компоненту связности в графе G.

Для выполнения систематического поиска ребер замены алгоритм присваивает каждому ребру e уровень [math]\displaystyle{ \ell (e) \; }[/math] и на основе этих уровней поддерживает множество под-лесов остовного дерева F: для каждого уровня i лес [math]\displaystyle{ F_i \; }[/math] является под-лесом, порожденным древесными ребрами уровня выше или равного i. Обозначив за L максимальный уровень ребра, получаем следующее:

[math]\displaystyle{ F = F_0 \supseteq F_1 \supseteq F_2 \supseteq ... \supseteq F_L. }[/math]

Вначале все ребра имеют уровень 0; затем уровни прогрессивно увеличиваются, но никогда не уменьшаются. Изменения уровней ребер выполняются таким образом, чтобы поддерживать следующие инварианты, которые очевидным образом выполняются в начале процесса.

Инвариант (1): F – максимальный остовный лес графа G, если уровни ребер интерпретировать как их веса.

Инвариант (2): Число вершин каждого дерева [math]\displaystyle{ F_i }[/math] не превышает [math]\displaystyle{ n/2^i \; }[/math].

Инвариант (1) следует интерпретировать следующим образом. Пусть [math]\displaystyle{ (u, v) \; }[/math] – недревесное ребро уровня [math]\displaystyle{ \ell (u, v) \; }[/math]; пусть [math]\displaystyle{ u \cdot \cdot \cdot v \; }[/math] – уникальный путь между u и v в F (такой путь существует, поскольку F является остовным лесом графа G). Пусть e – любое ребро из пути [math]\displaystyle{ u \cdot \cdot \cdot v \; }[/math], а [math]\displaystyle{ \ell (e) \; }[/math] – уровень этого ребра. В силу инварианта (1), [math]\displaystyle{ \ell (e) \ge \ell (u, v) \; }[/math]. Поскольку это выполняется для каждого ребра пути, а по построению [math]\displaystyle{ F_{\ell(u, v)} }[/math] содержит все древесные ребра уровня более или равного [math]\displaystyle{ \ell (u, v) \; }[/math], то весь путь содержится в [math]\displaystyle{ F_{\ell(u, v)} }[/math]; иначе говоря, u и v являются связанными в [math]\displaystyle{ F_{\ell(u, v)} }[/math].

Из инварианта (2) следует, что максимальное число уровней равно [math]\displaystyle{ L \le \mathcal {b} log_2 \; n \mathcal {c} }[/math].

Заметим, что при вставке нового ребра ему присваивается уровень 0. Затем его уровень может быть увеличен не более [math]\displaystyle{ \mathcal {b} log_2 \; n \mathcal {c} }[/math] раз вследствие последовательности удалений ребер. Когда удаляется ребро e = (v, w) уровня [math]\displaystyle{ \ell (e) \; }[/math], алгоритм ищет ребро замены с максимально высоким уровнем, если такое существует. В силу инварианта (1) такое ребро замены имеет уровень [math]\displaystyle{ \ell \le \ell (e) \; }[/math]. Следовательно, процедура замены [math]\displaystyle{ Replace((u, w), \ell (e)) }[/math] вызывается с параметрами [math]\displaystyle{ e \; }[/math] и [math]\displaystyle{ \ell (e) }[/math]. Далее будут вкратце описаны операции, выполняемые этой процедурой.

[math]\displaystyle{ Replace((u, w), \ell ) \; }[/math] находит ребро замены самого высокого уровня, не превышающего [math]\displaystyle{ \ell \; }[/math], если такая существует. Если на уровне [math]\displaystyle{ \ell \; }[/math] такого ребра не существует, имеет место один из двух вариантов: если [math]\displaystyle{ \ell \gt 0 \; }[/math], алгоритм рекурсивно переходит на уровень [math]\displaystyle{ \ell - 1 \; }[/math]; в противном случае [math]\displaystyle{ \ell = 0 \; }[/math], и удаление ребра (v, w) разделяет деревья v и w в графе G.

Во время поиска на уровне [math]\displaystyle{ \ell \; }[/math] подходящим образом выбранные древесные и недревесные ребра могут быть перемещены на более высокий уровень следующим образом. Пусть [math]\displaystyle{ T_v }[/math] и [math]\displaystyle{ T_w }[/math] – деревья в лесу [math]\displaystyle{ F_{\ell } }[/math], полученные после удаления ребра (v, w), и пусть, без ограничения общности, [math]\displaystyle{ T_v }[/math] меньше [math]\displaystyle{ T_w }[/math]. Тогда [math]\displaystyle{ T_v }[/math] содержит не более [math]\displaystyle{ n/2^{\ell + 1} }[/math] вершин, поскольку [math]\displaystyle{ T_v \cup T_w \cup \{ (v, w) \} }[/math] было деревом на уровне [math]\displaystyle{ \ell \; }[/math] и выполняется инвариант (2). Следовательно, ребра уровня [math]\displaystyle{ \ell \; }[/math] в [math]\displaystyle{ T_v }[/math] могут быть перемещены на уровень [math]\displaystyle{ \ell + 1\; }[/math] с сохранением инвариантов. Наконец, одна за ребром посещаются недревесные ребра, инцидентные [math]\displaystyle{ T_v }[/math]: если ребро соединяет [math]\displaystyle{ T_v }[/math] и [math]\displaystyle{ T_w }[/math], то ребро замены найдено и поиск останавливается; в противном случае его уровень увеличивается на 1.

Деревья каждого леса поддерживаются таким образом, что базовые операции, необходимые для реализации вставки и удаления ребер, могут быть выполнены за время O(log n). Имеются несколько вариантов базовых структур данных, которые могут выполнить такую задачу; например, для этой цели можно использовать деревья Эйлерова пути (ET-деревья), впервые предложенные в [17].

Помимо вставки и удаления ребер из леса, ET-деревья также могут поддерживать такие операции, как нахождение в лесу дерева, содержащего заданную вершину, вычисление размера дерева и, что еще более важно, нахождение древесных ребер уровня [math]\displaystyle{ \ell \; }[/math] в дереве [math]\displaystyle{ T_v }[/math] и недревесных ребер уровня [math]\displaystyle{ \ell \; }[/math], инцидентных [math]\displaystyle{ T_v }[/math]. Это можно сделать за счет дополнения ET-деревьев константным количеством информации для каждой вершины; подробнее об этом – в [11].

Используя идею амортизации на базе изменений уровня, можно доказать заявленную границу времени обновления в размере [math]\displaystyle{ O(log^2 n) \; }[/math]. В частности, вставка ребра и повышение его уровня требуют времени [math]\displaystyle{ O(log \; n) }[/math]. Поскольку это может случиться [math]\displaystyle{ O(log \; n) }[/math] раз, полная амортизированная стоимость вставки, включающая повышение уровня, составляет [math]\displaystyle{ O(log^2 n) \; }[/math]. Что касается удалений ребер, полная стоимость операций обрезания и связывания [math]\displaystyle{ O(log \; n) }[/math] лесов составляет [math]\displaystyle{ O(log^2 n) \; }[/math]; кроме того, имеется [math]\displaystyle{ O(log \; n) }[/math] рекурсивных вызовов процедуры Replace, каждый из них стоимостью [math]\displaystyle{ O(log \; n) }[/math], плюс амортизированная стоимость операций повышений уровня. ET-деревья над [math]\displaystyle{ F_0 = F \; }[/math] позволяют получать ответы на запросы о связности за время [math]\displaystyle{ O(log \; n) }[/math] в наихудшем случае. Как было показано в [11], это время может быть уменьшено до [math]\displaystyle{ O(log \; n/log \; log \; n) }[/math] в случае использования [math]\displaystyle{ \Theta (log \; n) }[/math]-арной версии ET-деревьев.

Теорема 1. Динамический граф G с n вершинами может поддерживать вставку и удаление ребер за амортизированное время [math]\displaystyle{ O(log^2 \; n) }[/math] на одно обновление и отвечать на запросы о связности за время [math]\displaystyle{ O(log \; n/ log \; log \; n) }[/math] в наихудшем случае.

Позднее Торуп [18] предложил еще одну структуру данных, которая позволяет обеспечить несколько иные временные границы:

Теорема 2. Динамический граф G с n вершинами может поддерживать вставку и удаление ребер за амортизированное время [math]\displaystyle{ O(log \; n • (log \; log \; n)^3) }[/math] на одно обновление и отвечать на запросы о связности за время [math]\displaystyle{ O(log \; n/log \; log \; log \; n) }[/math].

Границы, приведенные в теоремах 1 и 2, не могут сравниваться непосредственно, поскольку каждая из них жертвует оптимальностью времени выполнения одной операции (либо запроса, либо обновления) ради улучшения времени выполнения другой.

Наилучшая известная нижняя граница для задачи динамической связности имеет место при использовании вычислительной модели битового зонда (bit-probe model); ее предложили Патраку и Тарнифа [16]. Модель битового зонда представляет собой вариант модели клеточного зонда (cell-probe model) с однобитными клетками. В этой модели память организована в виде клеток, и алгоритм может производить чтение из клетки или запись в нее за константное время. Количество клеточных зондов рассматривается в качестве меры сложности. Формальное определение этой модели можно найти в [13].

Теорема 3. Рассмотрим реализацию битового зонда для задачи динамической связности, в которой операции обновления выполняются за ожидаемое амортизированное время [math]\displaystyle{ t_u }[/math], а запросы – за ожидаемое время [math]\displaystyle{ t_q }[/math]. Тогда для среднего случая распределения входных данных [math]\displaystyle{ t_u = \Omega (log^2 \; n/ log^2 \; (t_u + t_q)) }[/math]. В частности,

[math]\displaystyle{ max \{ t_u, t_q \} = \Omega \left ( \left ( \frac{log \; n}{log \; log \; n} \right ) ^2 \right ) \; }[/math]

Для модели битового зонда наилучшая верхняя граница на одну операцию достигается при использовании алгоритма теоремы 2; она составляет [math]\displaystyle{ O(log^2 \; n/ log \; log \; log \; n) }[/math]. Следовательно, разрыв между верхней и нижней границами ограничен дважды логарифмическим множителем.

Применение

Задача динамической связности является базовой подзадачей множества других важных задач – таких как динамическая поддержка минимальных остовных деревьев и динамическая задача связности ребер и вершин. Кроме того, существуют различные варианты применения задачи динамической связности графа в других дисциплинах – от вычислительной биологии, в которой задача динамической связности графа оказывается полезной для динамического сопровождения поверхности молекул белка в ходе того, как молекулы претерпевают конформационные изменения [6], до обработки изображений, в которой требуется поддерживать связные компоненты растрового изображения [3].

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

Исследования в области динамической связности оставляют открытые и довольно интересные вопросы. Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами. Заметим, что нижняя граница, обозначенная теоремой 3, говорит о том, что возможны различные соотношения между запросами и обновлениями; можем ли мы разработать структуру данных с временем выполнения одного обновления [math]\displaystyle{ o(log \; n) }[/math] и временем выполнения одного запроса [math]\displaystyle{ O(poly(log \; n)) }[/math]? Это должно быть особенно интересно для приложений, в которых число запросов значительно превышает число обновлений.

Наконец, возможно ли разработать алгоритм с совпадающими границами для обновлений и запросов [math]\displaystyle{ O(log \; n) }[/math] для графов общего вида? Заметим, что это возможно для специального случая планарных графов [5].

Экспериментальные результаты

Обстоятельное эмпирическое исследование динамических алгоритмов связности было проведено в работах [1,12].

См. также

• Динамические деревья
• Полностью динамический алгоритм нахождения кратчайших путей между всеми парами
• Полностью динамическая связность высоких степеней
• Полностью динамическая связность высоких степеней в планарных графах
• Полностью динамические минимальные остовные деревья
• Полностью динамическая проверка на планарность
• Полностью динамический алгоритм транзитивного замыкания

Литература

1. Alberts, D., Cattaneo, G., Italiano, G.F.: An empirical study of dynamic graph algorithms. ACM J. Exp. Algorithmics 2 (1997)

2. Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comp. Syst. Sci. 65(1), 38-72 (2002)

3. Eppstein, D.: Dynamic Connectivity in Digital Images. Inf. Process. Lett. 62(3), 121-126 (1997)

4. Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. Assoc. Comp. Mach. 44(5), 669-696 (1997)

5. Eppstein, D., Italiano, G.F., Tamassia, R.,Tarjan, R.E., Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic planegraph. J. Algorithms 13, 33-54 (1992)

6. Eyal, E., Halperin, D.: Improved Maintenance of Molecular Surfaces Using Dynamic Graph Connectivity. in: Proc. 5th International Workshop on Algorithms in Bioinformatics (WABI 2005), Mallorca, Spain, 2005, pp.401-413

7. Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees. SIAM J. Comp. 14, 781-798 (1985)

8. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In: Proc. 32nd Symp. Foundations of Computer Science, 1991, pp. 632-641

9. Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351-362(1998)

10. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4),502-516(1999)

11. Holm, J., de Lichtenberg, K.,Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48, 723-760 (2001)

12. Iyer, R., Karger, D., Rahul, H.,Thorup, M.: An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms. ACM J. Exp. Algorithmics 6 (2001)

13. Miltersen, P.B.: Cell probe complexity-a survey. In: 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Advances in Data Structures Workshop, 1999

14. Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity models for incremental computation. In: Ausiello, G., Italiano, G.F. (eds.) Special Issue on Dynamic and On-line Algorithms. Theor. Comp. Sci. 130(1), 203-236 (1994)

15. Patrascu, M., Demain, E.D.: Lower Bounds for Dynamic Connectivity. In: Proc. 36th ACM Symposium on Theory of Computing (STOC), 2004, pp. 546-553

16. Patrascu, M., Tarnija, C.: On Dynamic Bit-Probe Complexity, Theoretical Computer Science, Special Issue on ICALP'05. In: Italiano, G.F., Palamidessi, С (eds.) vol. 380, pp. 127-142 (2007)

A preliminary version in Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), 2005, pp. 969-981

17. Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM J. Comp. 14,862-874 (1985)

18. Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343-350