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

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

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

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

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

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

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

Есть несколько компромиссов между временем обновления и временем запроса. Пусть будет количеством ребер, а количеством вершин. Для групп обеспечения доступности баз данных Деметреску и Итальяно (FOCS'00) дали рандомизированную структуру данных, которая поддерживает обновления (вставку или удаление ребер) за O ( ) запросов времени и достижимости за O ( ) времени (узел) вставки / удаления также поддерживаются, в O (1) раз); этот результат был расширен Санковским (FOCS'04) для работы с общими ориентированными графами. Также для DAG Родитти (SODA'03) показал, что вы можете поддерживать матрицу переходного замыкания за общее время O ( ), где - количество вставок,$m$$n$$n^{1.58}$$n^{0.58}$$mn+I·n^2+D$$I$$D$количество удалений и, конечно, время запроса 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) ,$n^2$$m\sqrt{n}$$O(\sqrt{n}$$m+n\log n$$n$$n^{1.58}$$n^{0.58}$$n^{1.495}$$n^{1.495}$

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

Я думаю, что лучшие результаты на данный момент обсуждаются в разделе «Управление динамическими матрицами для полностью динамического транзитивного замыкания» . В этой статье обсуждается случайный алгоритм с временем запроса и временем обновления.$O(n^{0.58})$$O(n^{1.58})$

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