Компромиссы при решении динамических графовых задач
Ключевые слова и синонимы
Поиск оптимального соотношения между временем обновления и временем выполнения запроса при решении динамических графовых задач
Постановка задачи
Динамический алгоритм на графе поддерживает заданное свойство 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].