¿Existe un algoritmo para mantener eficientemente la información de conectividad para un DAG en presencia de inserciones / eliminaciones?

Dado un gráfico acíclico dirigido, , ¿es posible soportar eficientemente las siguientes operaciones?$G(V,E)$

• : determina si hay una ruta en G del nodo a al nodo$isConnected(G,a,b)$$G$$a$$b$
• : Agrega una arista de a a b en el gráfico$link(G,a,b)$$a$$b$$G$
• : elimina el borde de a a b en$unlink(G,a,b)$$a$$b$$G$
• : Agrega un vértice a G$add(G,a)$
• : elimina un vértice de G$remove(G,a)$

Algunas notas

• Si nosotros no permitidos , parece que sería fácil para mantener la información de conexión, utilizando una estructura de tipo de datos inconexos-set.$unlink$
• Obviamente, podría implementarse utilizando la búsqueda de profundidad o amplitud, utilizando la ingenua representación del gráfico basada en punteros. Pero esto es ineficiente.$isConnected$

Espero un tiempo logarítmico o constante amortizado para las tres operaciones. es posible?

El problema que ha descrito es el alcance de DAG totalmente dinámico (también denominado cierre transitivo completamente dinámico en DAG). Se llama totalmente dinámico, ya que las personas también estudian las versiones donde solo son posibles las eliminaciones (luego se llama accesibilidad decreciente), y donde solo son posibles las inserciones (llamadas accesibilidad incremental).

Hay algunas compensaciones entre el tiempo de actualización y el tiempo de consulta. Sea el número de aristas yn el número de vértices. Para los DAG, Demetrescu e Italiano (FOCS'00) proporcionaron una estructura de datos aleatoria que admite actualizaciones (inserciones de borde o eliminaciones) en tiempo O ( n 1.58 ) y consultas de accesibilidad en tiempo O ( n 0.58 ) (también se admiten inserciones / eliminaciones de nodo , en O (1) tiempo); Sankowski (FOCS'04) amplió este resultado para trabajar con gráficos dirigidos en general. También para DAG, Roditty (SODA'03) demostró que puede mantener la matriz de cierre transitivo en el tiempo total O ( m n + I · n 2 + D ), donde$m$$n$$n^{1.58}$$n^{0.58}$$mn+I·n^2+D$ es el número de inserciones, D el número de eliminaciones y, por supuesto, el tiempo de consulta es O ( 1 ).$I$$D$$1$

Para los gráficos generales dirigidos, se conocen los siguientes tiempos (actualización, consulta): (O ( ), O (1)) (Demetrescu e Italiano FOCS'00 (amortizado), Sankowski FOCS'04 (peor de los casos)), ( O ( m $n^2$ ),O($m\sqrt{n}$ )) (Roditty, Zwick FOCS'02), (O (m+nlogn), O (n)) (Roditty, Zwick STOC'04), (O (n 1.58 ), O (n 0.58 )) y (O (n 1.495 ), O (n 1.495 )) por Sankowski (FOCS'04).$O(\sqrt{n}$$m+n\log n$$n$$n^{1.58}$$n^{0.58}$$n^{1.495}$$n^{1.495}$

Obtener un tiempo de consulta pollogarítmica, sin aumentar demasiado el tiempo de actualización, es un gran problema abierto, incluso para los DAG.

Creo que los mejores resultados hasta ahora se discuten en "Mantenimiento de matrices dinámicas para el cierre transitivo completamente dinámico" . Ese documento discute un algoritmo aleatorio con tiempo de consulta y un tiempo de actualización O ( n 1.58 ) .$O(n^{0.58})$$O(n^{1.58})$

(Esto solo cubre la primera versión de su pregunta, con linky unlinkpero sin addy remove).