Réduction transitive du DAG

Je recherche l'algorithme O (V + E) pour trouver la réduction transitive avec un DAG.

C'est-à-dire supprimer autant d'arêtes que possible de sorte que si vous pouviez atteindre v à partir de u, pour v et u arbitraires, vous puissiez toujours atteindre après suppression des bords.

S'il s'agit d'un problème standard, veuillez me signaler une solution de modèle.

Nous pouvons résoudre ce problème simplement en faisant DFS à partir de chaque sommet.

1. Pour chaque sommet , démarrer le DFS à partir de chaque sommet v de telle sorte que v soit le descendant direct de u , c'est-à-dire. ( u , v ) est un bord.$u \in G$$v$$v$$u$$(u,v)$
2. Pour chaque sommet accessible par le DFS à partir de v , supprimez l'arête ( u , v ' ) .$v'$$v$$(u, v')$

La complexité globale de ce qui précède est la complexité de l'exécution de DFS ', qui est O ( N ( N + M ) ) .$N$$O(N(N+M))$

Pas ce que vous cherchez. Mais juste dans le but de partager des connaissances, vous pouvez le faire avec des messages si vous supposez que chaque sommet agit comme un processeur . Notez que chaque sommet a une valeur comparable. Par conséquent, il existe des sommets tels qu'ils sont plus grands que tous leurs voisins. Ces sommets font ce qui suit:$O(|E|)$

1. Soit le plus petit voisin maximum de v ,$u$$v$
2. envoyer un message à et inclure le bord ( v , u ) dans la sortie.$u$$(v,u)$
3. Pour chaque voisin de u et v (et plus petit que les deux), n'incluez pas ( v , w ) dans la sortie.$w$$u$$v$$(v,w)$
4. Répétez les étapes jusqu'à ce que toutes les arêtes pour un plus petit voisin v ' du sommet v soient incluses ou non incluses dans la sortie.$(v,v')$$v'$$v$

Maintenant, si un nœud reçu un message de chaque plus grand voisin (c'est-à-dire que tous les bords ( v ′ , v ) sont inclus ou non inclus, alors le nœud v agit comme s'il était le plus grand de son voisinage. mentionné précédemment 4 étapes.$v$$(v',v)$$v$

Cet algorithme se termine par des messages dans un environnement distribué. Je sais que ce n'est pas ce que vous demandez.$O(|E|)$

Lemme: S'il y a un bord V -> Y et Y est également un successeur indirect de V, (par exemple, V -> W -> + Y) alors le bord V -> Y est transitif et ne fait pas partie de la racine transitive.

Méthode: Gardez une trace de la fermeture transitive de chaque sommet, en passant du sommet aux sommets initiaux dans l'ordre topologique inverse. L'ensemble des successeurs indirects de V est l'union des fermetures transitives des successeurs immédiats de V. La fermeture transitive de V est l'union de ses successeurs indirects et de ses successeurs immédiats.

Algorithme:

    Initialise Visited as the empty set.
    For each vertex V of G, 
        Invoke Visit(V).

    Visit(V):
        If V is not in Visited,
            Add V to Visited, 
            Initialise Indirect as the empty set,
            For each edge V -> W in G,
                Invoke Visit(W),
                Add Closure(W) to Indirect.
            Set Closure(V) to Indirect.
            For each edge V -> W in G,
                Add W to Closure(V),
                If W is in the set Indirect,
                    Delete the edge V -> W from G.

Cela suppose que vous disposez d'un moyen efficace de suivre les ensembles de sommets (par exemple, les mappages de bits), mais je pense que cette hypothèse est également faite dans d'autres algorithmes O (V + E).

Un effet secondaire potentiellement utile est qu'il trouve la fermeture transitive de chaque sommet de G.

J'ai résolu le même problème, mais ce n'était pas exactement le même: il a demandé le nombre minimal d'arêtes dans le graphique après réduction de sorte que les sommets connectés à l'origine soient toujours connectés et qu'aucune nouvelle connexion ne soit établie. Comme c'est clair, il ne dit pas de trouver le graphe réduit mais combien d'arêtes redondantes sont présentes. Ce problème peut être résolu en O (V + E). Le lien vers l'explication est https://codeforces.com/blog/entry/56326 . Mais je pense que pour faire le graphe en fait, il aura une grande complexité que O (N)