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

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

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

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

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

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

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

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

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

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

Динамическим алгоритмам на графе посвящено множество работ. В числе графовых задач, для которых разработаны эффективные динамические алгоритмы, можно упомянуть задачи о связности графа, о минимальном разрезе, минимальном остовном дереве, транзитивном замыкании и нахождении кратчайших путей (см., например, [ ] и ссылки в этой работе). Многие из них выполняют явное обновление свойства 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 в графе либо значение +1 в случае, если не существует ориентированного пути из x в y.

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

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

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

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

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

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

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

Теорема 2 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n€) и операции вставки и удаления – за время о(и'°'1'е'1' е + n1+€) для любого e 2 [0;1], где <w(l,e, 1) – показатель степени при умножении матрицы n x n€ на матрицу n€ x n.