Existe-t-il un algorithme pour maintenir efficacement les informations de connectivité d'un DAG en présence d'insertions / suppressions?

Étant donné un graphe acyclique dirigé, , est-il possible de supporter efficacement les opérations suivantes?$G(V,E)$

• : détermine s'il existe un chemin dans G du noeud a au noeud$isConnected(G,a,b)$$G$$a$$b$
• : Ajoute une arête de a à b dans le graphe$link(G,a,b)$$a$$b$$G$
• : supprime le bord de a à b dans$unlink(G,a,b)$$a$$b$$G$
• : ajoute un sommet à G$add(G,a)$
• : Supprime un sommet de G$remove(G,a)$

Quelques notes:

• Si nous refusions , il semble qu'il serait facile de maintenir les informations de connectivité, en utilisant une structure de données de type ensemble disjoint.$unlink$
• De toute évidence, pourrait être implémenté en utilisant une recherche en profondeur ou en largeur, en utilisant la représentation naïve basée sur un pointeur du graphique. Mais c'est inefficace.$isConnected$

J'espère un temps constant ou logarithmique amorti pour les trois opérations. Est-ce possible?

Le problème que vous avez décrit est l'accessibilité DAG entièrement dynamique (également appelée fermeture transitive entièrement dynamique sur les DAG). On l'appelle entièrement dynamique car les gens étudient également les versions où seules les suppressions sont possibles (alors cela s'appelle l'accessibilité décrémentielle), et où seules les insertions sont possibles (appelées l'accessibilité incrémentielle).

Il existe quelques compromis entre l'heure de mise à jour et l'heure de la requête. Soit le nombre d'arêtes et n le nombre de sommets. Pour les DAG, Demetrescu et Italiano (FOCS'00) ont donné une structure de données randomisée qui prend en charge les mises à jour (insertions ou suppressions de bords) en O ( n 1,58 ) et les requêtes d'accessibilité en O ( n 0,58 ) (les insertions / suppressions de nœuds sont également prises en charge , en temps O (1)); ce résultat a été étendu par Sankowski (FOCS'04) pour travailler sur des graphiques orientés généraux. Aussi pour les DAG, Roditty (SODA'03) a montré que vous pouvez maintenir la matrice de fermeture transitive dans le temps total O ( m n + I · n 2 + D ), où$m$$n$$n^{1.58}$$n^{0.58}$$mn+I·n^2+D$ est le nombre d'insertions, D le nombre de suppressions et bien sûr le temps de requête est O ( 1 ).$I$$D$$1$

Pour les graphiques orientés généraux, les heures suivantes (mise à jour, requête) sont connues: (O ( ), O (1)) (Demetrescu et Italiano FOCS'00 (amorti), Sankowski FOCS'04 (pire cas)), ( 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 )) et (O (n 1.495 ), O (n 1.495 )) par Sankowski (FOCS'04).$O(\sqrt{n}$$m+n\log n$$n$$n^{1.58}$$n^{0.58}$$n^{1.495}$$n^{1.495}$

L'obtention d'un temps de requête polylogarithmique, sans augmenter trop le temps de mise à jour est un problème majeur, même pour les DAG.

$O(n^{0.58})$$O(n^{1.58})$

(Cela ne couvre que la première version de votre question, avec linket unlinkmais sans addet remove.)