Существует ли алгоритм для эффективного сохранения информации о связности для DAG при наличии вставок / удалений?

17

Можно ли эффективно задавать ациклический ориентированный граф для следующих операций?G(V,E)

  • isConnected(G,a,b) : определяет, существует ли путь в от узла до узлаGab
  • link(G,a,b) : добавляет ребро из в в графеabG
  • unlink(G,a,b) : удаляет ребро от до вabG
  • add(G,a) : добавляет вершину к G
  • remove(G,a) : удаляет вершину из G

Несколько заметок:

  • Если бы мы запретили , кажется, было бы легко поддерживать информацию о связности, используя структуру данных типа disjoint-set.unlink
  • Очевидно, что может быть реализован с использованием поиска по глубине или ширине, используя наивное представление графа на основе указателей. Но это неэффективно.isConnected

Я надеюсь на амортизированное постоянное или логарифмическое время для всех трех операций. Это возможно?

Джастин Килпатрик
источник
3
Связанный: версия ненаправленного графа была запрошена ранее. Существует ли онлайн-алгоритм для отслеживания компонентов в изменяющемся неориентированном графе?
Цуёси Ито
1
Не могли бы вы объяснить, как решить более простой случай (без отмены связи), используя структуру данных типа несвязанного множества?
Jbapple
@ Tsuyoshi - ссылки на этот вопрос выглядят интересно, сейчас я на них смотрю.
Джастин Килпатрик
(1) Вы ищете алгоритм динамического графа для направленной достижимости с ограничением, что граф является DAG. Если я не ошибаюсь, динамическая направленная достижимость намного сложнее, чем ненаправленный аналог, но здесь может помочь свойство DAG. (2) removeтакже удаляет падающие края? Если это так, требовать, чтобы эта операция была O (log n) времени, может быть слишком много, чтобы надеяться….
Цуёси Ито

Ответы:

19

Проблема, которую вы описали, - это полностью динамическая достижимость DAG (также называемая полностью динамическим транзитивным замыканием в DAG). Он называется полностью динамическим, поскольку люди также изучают версии, в которых возможны только удаления (тогда это называется декрементальной достижимостью), и где возможны только вставки (называемые инкрементной достижимостью).

Есть несколько компромиссов между временем обновления и временем запроса. Пусть будет количеством ребер, а количеством вершин. Для групп обеспечения доступности баз данных Деметреску и Итальяно (FOCS'00) дали рандомизированную структуру данных, которая поддерживает обновления (вставку или удаление ребер) за O ( ) запросов времени и достижимости за O ( ) времени (узел) вставки / удаления также поддерживаются, в O (1) раз); этот результат был расширен Санковским (FOCS'04) для работы с общими ориентированными графами. Также для DAG Родитти (SODA'03) показал, что вы можете поддерживать матрицу переходного замыкания за общее время O ( ), где - количество вставок,mnn1.58n0.58mn+I·n2+DIDколичество удалений и, конечно, время запроса O ( ).1

Для общих ориентированных графов известны следующие времена (обновление, запрос): (O ( ), O (1)) (Demetrescu и Italiano FOCS'00 (амортизированный), Sankowski FOCS'04 (наихудший случай)), (O ( ), )) (Родитти, Цвик FOCS'02), (O ( ), O ( )) (Родитти, Цвик STOC '04), (O ( ), O ( )) и (O ( ), O ( )) от Sankowski (FOCS'04) ,n2mnO(nm+nlognnn1.58n0.58n1.495n1.495

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

Virgi
источник
1
Спасибо за ваш ответ. Хотя я должен сказать, что разочарован тем, насколько бедны эти границы. :(
Джастин Килпатрик
1
Смежный вопрос: не могли бы вы указать мне какие-либо ссылки на более простые проблемы, возрастающую достижимость и понижающую достижимость для групп доступности баз данных?
Джастин Килпатрик
Это не намного лучше, чем наивный подход DFS (O(1),O(n^2))или (O(m),O(n+m)).
Томас Але
4

Я думаю, что лучшие результаты на данный момент обсуждаются в разделе «Управление динамическими матрицами для полностью динамического транзитивного замыкания» . В этой статье обсуждается случайный алгоритм с временем запроса и временем обновления.O(n0.58)O(n1.58)

(Это касается только первой версии вашего вопроса, с linkи, unlinkно без addи remove.)

jbapple
источник
Границы построены на алгоритме Штрассена, поэтому константа огромна.
Томас Ахле