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

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

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

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

Динамический алгоритм на графе поддерживает заданное свойство [math]\displaystyle{ \mathcal{P} }[/math] графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве [math]\displaystyle{ \mathcal{P} }[/math], а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление, и частично динамическим, если поддерживает либо вставку, либо удаление ребер.

Пусть дан граф, имеющий n вершин и m ребер. Задача поиска транзитивного замыкания (или задача достижимости) заключается в построении булевой матрицы M размера n x n, такой, что M[x, y] = 1 в том и только том случае, если существует ориентированный путь в графе из вершины x в вершину y. Полностью динамическую версию этой задачи можно определить следующим образом.

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

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

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

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

Далее будет исследована версия полностью динамической задачи достижимости для случая с единственным источником, в которой нас интересуют только запросы с фиксированной вершиной-источником s. Эта версия определяется следующим образом.

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

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

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

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

Подходы к решению

Простое решение этой задачи заключается в хранении явной информации о достижимости любой вершины из источника и обновлении этой информации при помощи любого алгоритма обхода графа из вершины s после каждой операции вставки или удаления. Такой подход требует O(m + n) времени на операцию, а последующие запросы о достижимости могут быть выполнены за константное время.

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

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

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

Простая редукция, предложенная в [1], позволяет сохранять актуальность информации о достижимости из единственного источника, за время ниже квадратичного на одну операцию в ориентированном графе, при выполнении последовательности операций вставки и удаления ребра в различном порядке. Упомянутые границы были впервые приведены для случая ориентированных ациклических графов, однако их можно распространить на ориентированные графы общего вида при помощи следующей теоремы [2]:

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

В [1] была предложена идея поддержки информации о достижимости из вершины-источника s до всех остальных вершин явным образом за счет поддержки булева массива R размера n, такого, что R[y] = 1 в том и только том случае, если существует ориентированный путь из s в y. Также поддерживается экземпляр D структуры данных для полностью динамической задачи достижимости из Теоремы 1. После каждой операции вставки или удаления можно обновить структуру D за время [math]\displaystyle{ O(n^{1,575}) \; }[/math] и затем перестроить R за время [math]\displaystyle{ O(n \cdot n^{0,575}) = O(n^{1,575}) \; }[/math], положив R[y] <— D.reachable (s, y) для каждой вершины y. Это позволяет получить следующие границы для полностью динамической задачи достижимости с единственным источником.

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

Применение

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

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

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

См. также

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

Литература

1. Demetrescu, C., Italiano, G.: Trade-offs for fully dynamic reachability on dags: Breaking through the O(n2) barrier. J. Assoc. Com-put. Machin. (JACM) 52,147-156 (2005)

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

3. 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