Компромиссы при решении динамических графовых задач

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

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

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

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

Определение 1 (Динамический алгоритм на графе). Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке:

insert(u, v): вставка дуги (u, v) в граф;

delete(u, v): удаление дуги (u, v) из графа;

query(..): ответ на запрос о выполнении свойства P графа.

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

Динамическим алгоритмам на графе посвящено множество работ. В числе графовых задач, для которых разработаны эффективные динамические алгоритмы, можно упомянуть задачи о связности графа, о минимальном разрезе, минимальном остовном дереве, транзитивном замыкании и нахождении кратчайших путей (см., например, [3] и ссылки в этой работе). Многие из них выполняют явное обновление свойства P после каждого обновления графа, чтобы отвечать на запросы за оптимальное время. Этот вариант подходит для случаев, когда обновлений мало, а запросов – много. В приложениях со сравнимым числом обновлений и запросов более эффективным подходом будет попытка уменьшить время обновления – возможно, ценой увеличения времени выполнения запроса. Это обычно достигается при помощи ослабления предположения о том, что свойство P следует поддерживать явным образом.

Далее будут рассмотрены алгоритмы для решения динамических графовых задач, неявно поддерживающие свойство графа и потому требующие неконстантного времени на выполнение запроса при более высокой скорости обновлений. В частности, будут рассмотрены две задачи: о динамическом транзитивном замыкании (также называемая динамической задачей достижимости) и динамическая задача нахождения кратчайших путей между всеми парами, определенная ниже.

Определение 2 (Полностью динамическая задача о транзитивном замыкании). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:

insert(u, v): вставка дуги (u, v) в граф;

delete(u, v): удаление дуги (u, v) из графа;

query(x, y): возвращает true, если существует ориентированный путь между вершинами x и y, и false в противном случае.

Определение 3 (Полностью динамическая задача нахождения кратчайших путей между всеми парами). Задача заключается в поддержке взвешенного ориентированного графа и выполнении последовательности следующих операций в различном порядке:

insert(u, v, w): вставка дуги (u, v) с весом w в граф;

delete(u, v): удаление дуги (u, v) из графа;

query(x, y): возвращает расстояние между x и y в графе либо значение [math]\displaystyle{ + \infty }[/math] в случае, если не существует ориентированного пути из x в y.

Вспомним, что расстояние между вершинами x и y равно весу пути из x в y с минимальным весом, где вес пути определяется как сумма весов входящих в него ребер.

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

В данной главе представлен обзор соотношений времени выполнения запросов и обновлений для динамических алгоритмов транзитивного замыкания и нахождения кратчайших путей между всеми парами.

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

Первое соотношение времени выполнения запросов и обновлений для этой задачи предложили Хензингер и Кинг [6], доказавшие следующий результат:

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

Первый алгоритм решения этой задачи с временем выполнения ниже квадратичного был разработан Деметреску и Итальяно для ориентированных ациклических графов [4, 5]:

Теорема 2 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время [math]\displaystyle{ O(n^{\epsilon}) }[/math] и операции вставки и удаления – за время [math]\displaystyle{ O(n^{\omega(1, \epsilon, 1) - \epsilon} + n^{1 + \epsilon}) }[/math] для любого [math]\displaystyle{ \epsilon \in [0, 1] \; }[/math], где [math]\displaystyle{ \omega(1, \epsilon, 1) \; }[/math] – показатель степени при умножении матрицы [math]\displaystyle{ n \times n^{\epsilon} }[/math] на матрицу [math]\displaystyle{ n^{\epsilon} \times n }[/math].

Заметим, что зависимость границ от параметра [math]\displaystyle{ \epsilon \; }[/math] обеспечивает весь диапазон выбора компромиссов между временем запроса и обновления. Для сбалансированного сочетания двух термов в границе обновления теоремы 2 необходимо, чтобы [math]\displaystyle{ \epsilon \; }[/math] удовлетворяло равенству [math]\displaystyle{ \omega(1, \epsilon, 1) = 1 + 2 \epsilon \; }[/math]. Из наилучшей известной границы на [math]\displaystyle{ \omega(1, \epsilon, 1) \; }[/math] [2, 7] следует, что [math]\displaystyle{ \epsilon \lt 0,575 \; }[/math]. Таким образом, наименьшее время обновления составляет [math]\displaystyle{ O(n^{1,575}) \; }[/math], из чего следует время запроса [math]\displaystyle{ O(n^{0,575}) \; }[/math].

Следствие 1 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время [math]\displaystyle{ O(n^{0,575}) \; }[/math], а операции вставки и удаления – за время [math]\displaystyle{ O(n^{1,575}) \; }[/math].

Санковски обобщил этот результат на случай ориентированных графов общего вида [13]:

Теорема 3 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n) и операции вставки и удаления – за время [math]\displaystyle{ O(n^{\omega(1, \epsilon, 1) - \epsilon} + n^{1 + \epsilon}) }[/math] для любого [math]\displaystyle{ \epsilon \in [0, 1] \; }[/math], где [math]\displaystyle{ \omega(1, \epsilon, 1) \; }[/math] – показатель степени при умножении матрицы [math]\displaystyle{ n \times n^{\epsilon} }[/math] на матрицу [math]\displaystyle{ n^{\epsilon} \times n }[/math].

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

Санковски также показал, как получить еще более быстрое время обновления [math]\displaystyle{ O(n^{1,495}) \; }[/math] за счет увеличения времени выполнения запросов [math]\displaystyle{ O(n^{1,495}) \; }[/math]:

Теорема 4 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы и операции вставки и удаления за время [math]\displaystyle{ O(n^{1,495}) \; }[/math].

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

Теорема 5 (Родитти и Цвик 2002 [10]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время [math]\displaystyle{ O(m \sqrt{n}) }[/math], а запросы – за время [math]\displaystyle{ O(\sqrt{n}) }[/math] в наихудшем случае.

Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m+ n log n), а запросы – за время O(n) в наихудшем случае.

Заметим, что результаты теорем 5 и 6 являются субквадратичными для [math]\displaystyle{ m = o(n^{1,5}) \; }[/math] и [math]\displaystyle{ m = o(n^2) \; }[/math], соответственно. Более того, они не основываются на быстром перемножении матриц, которое является теоретически эффективным, но непрактичным.

Динамический алгоритм нахождения кратчайших путей

Первыми эффективный компромиссный алгоритм для динамического поиска кратчайших путей предложили Родитти и Цвик для специального случая разреженных графов с единичными весами ребер [12]:

Теорема 7 (Родитти и Цвик 2004 [12]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами с единичными весами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время [math]\displaystyle{ O(t + \frac{n \; log \; n}{k}) }[/math] в наихудшем случае, а операции вставки и удаления – за амортизированное время [math]\displaystyle{ O(\frac{m \; n^2 log \; n}{t^2} + km + \frac{m \; n \; log \; n}{k}) }[/math]

Положив [math]\displaystyle{ k = (n \; log \; n)^{1/2} }[/math] и [math]\displaystyle{ (n \; log \; n)^{1/2} \le t \le n^{3/4} \; (log \; n)^{1/4} }[/math] в теореме 7, можно получить амортизированное время обновления [math]\displaystyle{ O(\frac{m \; n^2 \; log \; n}{t^2}) }[/math] и время выполнения запросов в наихудшем случае [math]\displaystyle{ O(t) \; }[/math]. Самое быстрое время обновления, [math]\displaystyle{ O(m \sqrt{n \; log n}) }[/math], можно получить, если выбрать [math]\displaystyle{ t = n^{3/4}(log \; n)^{1/4} }[/math].

Позднее Санковски разработал первый алгоритм с временем выполнения ниже квадратичного для плотных графов, основанный на быстром умножении матриц [14]:

Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время [math]\displaystyle{ O(n^{1,288}) \; }[/math], а операции вставки и удаления – за время [math]\displaystyle{ O(n^{1,932}) \; }[/math].

Тип графа	Тип алгоритма	Время обновления	Время выполнения запроса	Источник
Граф общего вида	Монте-Карло	[math]\displaystyle{ O(m \sqrt{n} \; log^2 n) }[/math] аморт.	O(n /log n)	Хензингер и Кинг [6]
Ориентированный ациклический граф	Монте-Карло	[math]\displaystyle{ O(n^{1,575}) \; }[/math]	[math]\displaystyle{ O(n^{0,575}) \; }[/math]	Деметреску, Итальяно [4]
Граф общего вида	Монте-Карло	[math]\displaystyle{ O(n^{1,575}) \; }[/math]	[math]\displaystyle{ O(n^{0,575}) \; }[/math]	Санковски [13]
Граф общего вида	Монте-Карло	[math]\displaystyle{ O(n^{1,495}) \; }[/math]	[math]\displaystyle{ O(n^{1,495}) \; }[/math]	Санковски [13]
Граф общего вида	Детерминированный	[math]\displaystyle{ O(m \sqrt{n}) }[/math] аморт.	[math]\displaystyle{ O(\sqrt{n)} }[/math]	Родитти, Цвик [10]
Граф общего вида	Детерминированный	O(m + n log n) аморт.	O(n)	Родитти, Цвик [11]

Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения

Применение

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

В число сценариев применения динамических алгоритмов нахождения кратчайших путей входят оптимизация сетей [1], форматирование документов [8], маршрутизация в системах коммуникации, робототехника, инкрементная компиляция, системы управления информацией о дорожном движении [15] и анализ потоков данных. Полный обзор реальных областей применения динамических алгоритмов нахождения кратчайших путей приведен в [9].

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

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

См. также

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

Литература

1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993)

2. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251-280 (1990)

3. Demetrescu, C., Finocchi, I., Italiano, G.: Dynamic Graphs. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications (CRC Press Series, in Computer and Information Science), chap. 36. CRC Press, Boca Raton (2005)

4. Demetrescu, C., Italiano, G.: Fully dynamic transitive closure: Breaking through the O(n2) barrier. In: Proc. of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS'00), Redondo Beach (2000), pp. 381-389

5. Demetrescu, C., Italiano, G.: Trade-offs for fully dynamic reachability on dags: Breaking through the O(n2) barrier. J. ACM 52, 147-156(2005)

6. Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95), Milwaukee (1995), pp. 664-672

7. Huang, X., Pan, V.: Fast rectangular matrix multiplication and applications. J. Complex. 14, 257-299(1998)

8. Knuth, D., Plass, M.: Breaking paragraphs into lines. Software-practice Exp. 11,1119-1184 (1981)

9. Ramalingam, G.: Bounded incremental computation. In: Lecture Notes in Computer Science, vol. 1089. Springer, New York (1996)

10. Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proceedings of 43th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Vancouver (2002), pp. 679-688

11. Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), Chicago (2004), pp. 184-191

12. Roditty, L., Zwick, U.: On Dynamic Shortest Paths Problems. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA), Bergen (2004), pp. 580-591

13. Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: FOCS '04: Proceedings of the45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 509-517. IEEE Computer Society, Washington, DC (2004)

14. Sankowski, P.: Subquadratic algorithm for dynamic shortest distances. In: 11th Annual International Conference on Computing and Combinatorics (COCOON'05), Kunming (2005), pp. 461-470

15. Schulz, F., Wagner, D., Weihe, K.: Dijkstra's algorithm on-line: an empirical case study from public railroad transport. In: Proc. 3rd Workshop on Algorithm Engineering (WAE'99), London (1999), pp. 110-123

16. Yannakakis, M.: Graph-theoretic methods in database theory. In: Proc. 9-th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville (1990). pp. 230-242