Avec un poids pondéré, existe-t-il un algorithme O (V + E) pour remplacer chaque poids par la somme des poids de ses ancêtres?

34

Le problème, bien sûr, est le double comptage. Il est assez facile à faire pour certaines classes de DAG = un arbre, voire un arbre parallèle-série. Le seul algorithme que j'ai trouvé qui fonctionne sur les DAG généraux en un temps raisonnable est approximatif (Synopsis diffusion), mais augmenter sa précision est exponentiel en nombre de bits (et j'ai besoin de beaucoup de bits).

Contexte: cette tâche est effectuée (plusieurs fois avec des «poids» différents) dans le cadre des calculs de probabilité dans BBChop (http://github.com/ealdwulf/bbchop), un programme permettant de rechercher des bogues intermittents (c'est-à-dire une version bayésienne de ' git bisect '). Le DAG en question est donc un historique de révision. Cela signifie qu'il est peu probable que le nombre d'arêtes se rapproche du carré du nombre de nœuds, il sera probablement inférieur à k fois le nombre de nœuds pour certains k plus petits. Malheureusement, je n'ai trouvé aucune autre propriété utile des DAG de révision. Par exemple, j'espérais que le composant triconnecté le plus important ne deviendrait la racine carrée du nombre de nœuds, mais malheureusement (du moins dans l'histoire du noyau Linux), il croît de manière linéaire.

Ealdwulf
la source
Juste pour clarifier: seuls les nœuds ont des poids, pas les bords?
Heinrich Apfelmus
Oui, juste les nœuds.
Ealdwulf
4
Cela semble être un quasi-double de cstheory.stackexchange.com/questions/553/… ?
Jukka Suomela
cela semble en fait plus général, puisque l’attribution de poids unitaires à tous les sommets réduit ce problème au problème de l’atteignabilité.
Suresh Venkat
Il semble que l'approximation ne soit pas difficile à faire avec certains facteurs polylogiques supplémentaires ...
Sariel Har-Peled

Réponses:

17

Nous supposons que les poids de sommet peuvent être des entiers positifs arbitraires ou, plus précisément, ils peuvent être des entiers positifs au plus 2 n . Ensuite, la tâche en cours ne peut pas être exécutée même dans un intervalle de temps légèrement plus faible, O ( n 2 ), à moins que la fermeture transitive d'un graphe dirigé arbitraire ne puisse être calculée en temps O ( n 2 ), où n indique le nombre de sommets. (Notez qu'un algorithme de temps O ( n 2 ) pour la fermeture transitive sera une percée.) Ceci est la contrapositive de la revendication suivante:

Revendication . Si la tâche en cours peut être exécutée dans le temps O ( n 2 ), la fermeture transitive d'un graphe dirigé arbitraire donné sous forme de matrice d'adjacence peut être calculée en O ( n 2 ) temps (en supposant un modèle de calcul raisonnable).

Preuve . En prétraitement, nous calculons la décomposition en composantes fortement connectées du graphe orienté donné G en temps O ( n 2 ) pour obtenir un DAG G '. Notez que si l' on peut calculer la fermeture transitive de G ', nous pouvons reconstruire la fermeture transitive de G .

Attribuez maintenant le poids 2 i à chaque sommet i du DAG G 'et utilisez l'algorithme pour le problème actuel. Ensuite, la représentation binaire de la somme affectée à chaque sommet i décrit exactement l'ensemble des ancêtres de i ; en d'autres termes, nous avons calculé la fermeture transitive de G '. QED .

L'inverse de la revendication est également vrai: si vous pouvez calculer la fermeture transitive d'un DAG donné, il est facile de calculer les sommes requises par le travail supplémentaire dans le temps O ( n 2 ). Par conséquent, en théorie, vous pouvez réaliser la tâche en cours dans le temps O ( n 2.376 ) en utilisant l'algorithme de fermeture transitive basé sur l' algorithme de multiplication matricielle Coppersmith-Winograd .

Edit : La révision 2 et les versions antérieures n'énonçaient pas explicitement l'hypothèse concernant la plage de poids des sommets. Per Vognsen a souligné dans un commentaire que cette hypothèse implicite pourrait ne pas être raisonnable (merci!), Et je suis d'accord. Même si des poids arbitraires ne sont pas nécessaires dans les applications, je suppose que cette réponse pourrait exclure certaines approches du raisonnement suivant: la fermeture peut être calculée en temps O ( n 2 ). ”

Edit : La révision 4 et antérieure indiquait de manière incorrecte la direction des bords.

Tsuyoshi Ito
la source
4
Je pensais à cela même hier soir puisqu’une solution pratique utilise des vecteurs binaires pour le comptage des exclusions. Je suppose que la seule question est de savoir s’il est raisonnable de supposer que les poids peuvent avoir une longueur de bits proportionnelle à n. En pratique, je peux imaginer que les poids sont limités par quelques k, de sorte que la somme maximale possible est kn, ce qui n’a pas assez de bits pour tirer cette astuce.
Per Vognsen
@ Per: Je conviens que l'hypothèse selon laquelle les poids de sommet peuvent être des entiers à n bits peut être discutable. J'ai édité la réponse pour rendre cette hypothèse explicite. Merci!
Tsuyoshi Ito
1
@Per: J'ai réalisé que si les poids des sommets sont des entiers limités par O (1), le problème se réduit au cas où tous les sommets ont le poids 1 en dupliquant les sommets de manière appropriée.
Tsuyoshi Ito le
Malheureusement, je ne vois pas de réponse dans ce fil au problème de comptage. Les chiffres contiennent logarithmiquement moins d'informations que la liste de la fermeture transitive, O (n log n) vs O (n ^ 2), donc je ne vois pas comment une réduction simple pourrait fonctionner.
Per Vognsen le
Soit dit en passant, une version intéressante de ce problème est lorsque nous avons une limite sur le facteur de branche et des informations sur la croissance en taille des générations (à la topologique) du DAG. Si la croissance est exponentielle, le motif est essentiellement semblable à un arbre. Que se passe-t-il si c'est linéaire, log-linéaire, quadratique, etc.?
Per Vognsen le
2

Ceci est une extension de mon commentaire sur la réponse de Tsuyoshi. Je pense que la réponse négative à la question peut être rendue inconditionnelle.

ω(n)O(n)

Gr,cr×crrc

r=(log n)/2c=2n/log n

nω(log n)

ω(n)2c(r1)=O(n)

Le point semble être que l’ordre partiel sous-jacent est dense, mais le DAG représente sa réduction transitive, qui peut être rare.

András Salamon
la source
Cet argument est intéressant, mais je ne suis pas sûr de pouvoir en faire une preuve de déclaration intéressante. Compte tenu de la difficulté omniprésente à prouver les limites inférieures des problèmes, cet argument me semble un atout.
Tsuyoshi Ito
@Tsuyoshi: Je pense que l'existence devrait fonctionner via un argument probabiliste et que la borne inférieure est faible, de sorte qu'il semble y avoir suffisamment d'espace pour que cela fonctionne. Mais vous avez raison, c’est de la main à la main, cette phrase "ajouts non réutilisables en moyenne" nécessite une meilleure base.
András Salamon
-2

Ceci est faux et est basé sur un malentendu sur la question. Merci à Tsuyoshi pour avoir patiemment signalé mon erreur. Laissant au cas où d'autres font la même erreur.

k

kO(k|V|)

O(|V|+|E|)

Cette approche devrait également bien fonctionner s'il existe des nœuds avec de nombreux prédécesseurs immédiats, pour autant qu'ils soient relativement peu fréquents.

András Salamon
la source
4
Je ne comprends pas. Comment éviter le double comptage lorsque le DAG n'est pas un arbre? En fait, si je ne me trompe pas, le cas général peut être réduit au cas où chaque sommet a au plus deux prédécesseurs, et tout algorithme à temps linéaire pour ce dernier cas donne un algorithme à temps de ligne pour le cas général.
Tsuyoshi Ito
O(|V|+|E|)k
Je crains que vous ayez mal compris mon commentaire. Je m'interroge sur l'exactitude de votre algorithme, pas sur le temps d'exécution. Supposons un DAG avec quatre sommets A, B, C, D avec des arêtes A → B → D et A → C → D avec un poids donné à chaque sommet. Après avoir calculé les sommes partielles pour B et C, vous ne pouvez pas simplement ajouter les sommes partielles pour B et C afin de calculer la somme pour D car cela ajouterait le poids du sommet A deux fois.
Tsuyoshi Ito
Σvous<vw(vous)
1
Oui. Et maintenant, je me souviens que la première fois que j'ai vu cette question, je l’avais mal interprétée de la même manière et je pensais que ce serait évident. Mais non, la vraie question est plus difficile que cela. Il est temps de penser…
Tsuyoshi Ito