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

Материал из WEGA
Перейти к навигации Перейти к поиску

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

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


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

Задача заключается в эффективной поддержке информации о связности в динамически меняющемся графе. Динамический алгоритм на графе поддерживает заданное свойство 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; она составляет O(log2 n/ log log log n). Следовательно, разрыв между верхней и нижней границами ограничен дважды логарифмическим множителем.

Применение

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


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

Исследования в области динамической связности оставляют открытые и довольно интересные вопросы. Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами. Заметим, что нижняя граница, обозначенная теоремой 3, говорит о том, что возможны различные соотношения между запросами и обновлениями; можем ли мы разработать структуру данных с временем выполнения одного обновления o(log n) и временем выполнения одного запроса O(poly(log n))? Это должно быть особенно интересно для приложений, в которых число запросов значительно превышает число обновлений. Наконец, возможно ли разработать алгоритм с совпадающими границами для обновлений и запросов O(log n) для графов общего вида? Заметим, что это возможно для специального случая планарных графов [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

Источник — http://pco.iis.nsk.su/wega/index.php?title=Полностью_динамическая_связность:_верхняя_и_нижняя_границы&oldid=10666