Débit maximal incrémentiel dans les graphiques dynamiques

Je recherche un algorithme rapide pour calculer le débit maximum dans les graphiques dynamiques. c'est-à-dire étant donné un graphe et nous avons le débit maximum dans de au . Ensuite, le nouveau / ancien nœud ajouté / supprimé avec ses bords correspondants pour former un graphique . Qu'est-ce qu'un flux maximal dans un graphique nouvellement créé? Existe-t-il un moyen d'empêcher de recalculer le débit maximal?s , t ∈ V F G s t u G $G=(V,E)$$s,t\in V$$F$$G$$s$$t$$u$$G^1$

Tout prétraitement peu gourmand en temps / mémoire est apprécié.

L'idée la plus simple consiste à recalculer le flux.

Une autre idée simple est la suivante: enregistrer tous les chemins d'augmentation utilisés dans le calcul du débit maximal précédent, pour ajouter un sommet , nous pouvons trouver des chemins simples (dans le graphique de capacité mis à jour par l'étape précédente) qui partent de la source, vont au puis vont à la destination, mais le problème est que ce chemin devrait être simple, je n'ai pas pu trouver mieux que pour ce cas, pour. (Notez également que si ce n'était qu'un chemin, cela pourrait être fait en mais ce n'est pas le cas.)v O ( n ⋅ m ) m = | E | O ( n + m $v$$v$$O(n\cdot m)$$m=|E|$$O(n+m)$

Aussi pour supprimer le nœud ci-dessus l'idée ne fonctionne pas.

J'ai également déjà vu des articles tels que l' approche incrémentale pour les bords , mais il semble qu'ils ne soient pas assez bons dans ce cas, c'est plus de pour chaque bord et semble ne pas être une extension appropriée dans ce cas (nous recalculons juste un flux). Actuellement, j'utilise également l' algorithme de flux maximal de Ford-Fulkerson S'il existe une meilleure option pour les algorithmes en ligne, il est bon de le savoir.$O(m)$

L'approche décrite peut ne pas être théoriquement optimale. C'est juste une solution pratique simple qui peut fonctionner pour l'auteur. Je ne peux pas fournir de références car j'ai toujours pensé que c'était un folklore largement connu, mais étrangement personne ne l'a posté dans la réponse. Alors je le fais.

Supposons que nous ayons un réseau non dirigé . Supposons qu'il soit stocké dans une structure de données qui permet des insertions / suppressions de vertex / arc faciles. Parfois, nous utiliserons le réseau résiduel (c'est-à-dire avec des capacités mises à jour ).G f c f = c - $G=(V,E,c)$$G_f$$c_f = c - f$

La première partie est de savoir comment traiter les insertions / suppressions de sommets. C'est plus ou moins simple pour les insertions:

1. Ajoutez un nouveau sommet avec des arêtes correspondantes au réseau résiduel.
2. Trouvez un débit maximal dans le réseau résiduel mis à jour à l'aide d'un algorithme maxflow de votre choix.

Pour les suppressions, les choses sont devenues plus compliquées. Imaginez que nous divisons le sommet nous sommes sur le point de supprimer en 2 moitiés et sorte que tous les arcs entrants pointent vers , tous les arcs sortants vont de et ces nouveaux sommets sont reliés par un arc de capacité infinie. La suppression de équivaut alors à la suppression de l'arc entre et . Que se passera-t-il dans ce cas? Notons l'écoulement passant par le sommet . Ensuite, connaîtra un excès de unités de débit etv i n v o u t v i n v o u t v v i n v o u t f v v v i n f v v o u t f v ~ f v v i n v o u t v i n v o u t f v f v v Δ $v$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$v$$v_{in}$$v_{out}$$f^v$$v$$v_{in}$$f^v$$v_{out}$connaîtra une pénurie d' unités de flux juste après la suppression (les contraintes de flux seront évidemment brisées). Pour que les contraintes de débit soient à nouveau maintenues, nous devons réorganiser les débits, mais nous voulons également maintenir la valeur de débit d'origine aussi élevée que possible. Voyons d'abord si nous pouvons faire un réarrangement sans diminuer le débit total. Pour vérifier cela, trouver un maxflow de à dans le réseau résiduel "coupé" (c'est-à-dire sans l'arc reliant et ). Il faut évidemment le délimiter par . S'il se trouve être égal à alors nous avons de la chance: nous avons réaffecté le flux qui passait par$f^v$$\tilde{f^v}$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$f^v$$f^v$$v$de telle manière que le débit total n'a pas été modifié. Dans l'autre cas, le débit total doit être diminué d'un excès "inutile" d' unités . Pour ce faire, connectez temporairement et par un arc de capacité infinie et réexécutez l'algorithme maxflow de à (nous devons délimiter le flux par ). Cela corrigera le réseau résiduel et fera en sorte que les contraintes de débit soient maintenues, diminuant automatiquement le débit total de .$\Delta = f^v - \tilde{f^v}$$s$$t$$v_{in}$$v_{out}$$\Delta$$\Delta$

La complexité temporelle de ces mises à jour peut dépendre de l'algorithme maxflow que nous utilisons. Les pires cas peuvent être assez mauvais, cependant, mais c'est toujours mieux que le recalcul total.

La deuxième partie est quel algorithme maxflow utiliser. Autant que je sache, l'auteur n'a pas besoin d'un algorithme très complexe (mais toujours efficace) avec une petite constante cachée pour l'exécuter sur une plate-forme mobile. Son premier choix de Ford-Fulkerson (je m'attends à ce que ce soit Edmonds-Karp ) ne semble pas très mal de ce point de vue. Mais il existe d'autres possibilités. Celui que je recommanderais d'essayer en premier est la variante de l'algorithme de Dinic car elle est assez rapide en pratique et peut être implémentée de manière très simple. D'autres options peuvent inclure la mise à l'échelle de la capacité de Ford-Fulkerson en$O(|V|^2|E|)$$O(|E|^2 \log C_{max})$et, après tout, différentes versions de push-relabel avec heuristique. Quoi qu'il en soit, la performance dépendra d'un cas d'utilisation, de sorte que l'auteur devrait trouver le meilleur empiriquement.

ok en tenant compte des nouvelles informations et en évitant certaines références difficiles de faux départ / hareng rouge (mea culpa), voici de nouvelles références à ce sujet.

Résolution rapide d'une séquence en ligne de problèmes de débit maximum avec des extensions de calcul de coupes minimales robustes Doug Altner et Özlem Ergun

cette référence prend en compte les séquences en ligne de MFP et les "démarrages à chaud", c'est-à-dire en s'appuyant sur les modifications incrémentielles d'un MFP précédent. «Nous démontrons que nos algorithmes réduisent le temps d'exécution d'un ordre de grandeur par rapport à des codes similaires qui utilisent un solveur MFP à boîte noire. En particulier, nous montrons que notre algorithme pour des coupes minimales robustes peut résoudre des instances en quelques secondes qui nécessiteraient plus de quatre heures en utilisant un solveur à débit maximal de boîte noire. "

progrès sur les problèmes impliquant des débits maximaux Altner, Douglas S., georgia tech

dans cette thèse de 2008 (pdf téléchargeable), l'auteur considère le problème de l'ajout incrémentiel d'arcs qui semble être "assez proche" du problème de l'ajout de nouveaux sommets (avec plusieurs nouveaux arcs).

une grande partie de cette référence concerne la suppression de parties du réseau (coupures / "interdiction") comme indiqué dans la 1ère partie du résumé

voir esp "IV RÉSOLUTION DES SÉQUENCES EN LIGNE DE FLUX MAXIMUM....... p63".

p 63 "Le but de ce chapitre, cependant, est de convaincre le lecteur que l'utilisation itérative d'un résolveur de flux maximum de boîte noire pour résoudre une grande séquence de MFP peut conduire à un nombre énorme de calculs inutiles."

p66 "Dans les applications susmentionnées, les MFP sont généralement similaires sur le plan topologique. En d'autres termes, le MFP suivant dans la séquence diffère du précédent en ajoutant ou en supprimant un petit nombre d'arcs ou en modifiant de manière prévisible les capacités d'un jeu d'arc localisé. , lors de la résolution de ces cas, le temps et l'espace nécessaires pour stocker quoi que ce soit au-delà de la solution au problème précédent sont généralement injustifiés. "

L'auteur de p67 utilise également ici l'approche du «démarrage à chaud». "Une stratégie efficace pour résoudre rapidement toute une séquence en ligne de problèmes d'optimisation consiste à développer des heuristiques de réoptimisation efficaces. À cette fin, nous développons un algorithme de débit maximal modifié qui est conçu pour des démarrages à chaud efficaces." "

voir esp p71 qui a le problème spécifique du nouvel arc incrémentiel:

Nouveau problème de réoptimisation de l'écoulement maximal de l'arc (NAMFRP)

l'auteur considère les problèmes plus généraux p67

Problème de réoptimisation de débit maximal (MFROP)
Problème de réoptimisation d'arc unique à débit maximal (MFSAROP)

à partir d'une recherche rapide, il semble que la version en ligne soit un domaine de recherche active. vous ne mentionnez pas le domaine d'application qui pourrait aider à affiner la recherche documentaire. une option consiste à rechercher un domaine d'application où il y a le plus ou la dernière innovation. par conséquent, il existe une certaine application du débit max incrémental dans les systèmes de vision et certains algorithmes pour cela; essayez Maximum Flows par Incremental Breadth-First Search dans les laboratoires de recherche Microsoft. en paraphrasant l'intro de cet article, apparemment pour les instances de vision, l'algorithme de Boykov et Kolmogorov fait bien & il n'y a pas de contre-exemples de temps exponentiels connus bien qu'en dehors des applications de vision il puisse mal fonctionner. il peut donc être utile d'essayer l'algorithme B&K sur vos données et de voir comment elles fonctionnent et

vous semblez dire qu'un algorithme incrémental qui est linéaire dans le nombre d'arêtes du graphique n'est pas une vitesse suffisante? mais n'est-ce pas une efficacité assez élevée? avec combien d'arêtes traitez-vous? peut-être que l'approche pourrait être de réduire le coût de la traversée du graphe si cela est cher ou un facteur significatif (par exemple graphe stocké en db vs graphe stocké en mémoire)

voici un article intéressant qui soutient que si l'algorithme non incrémental pour le débit max est en P, la version incrémentale est NP complète. "A notre connaissance, nos résultats sont les premiers à trouver un problème de temps P dont la version incrémentale est NP complète."

Débit incrémental par Hartline, Sharp

une autre possibilité / direction est l' algorithme de débit maximal push-relabel qui est "l'un des algorithmes les plus efficaces pour un débit maximal" et peut avoir de meilleurs profils de complexité en fonction de vos données. par exemple, comme l'indique la page wikipedia

l'implémentation avec la règle de sélection de sommet FIFO a , la règle de sélection de sommet active la plus élevée fournit la complexité ), et l'implémentation avec la structure de données d'arborescence dynamique de Sleator et Tarjan s'exécute en heure. asymptotiquement plus efficace qu'Edmonds-KarpO ( V 2 $O(V^3)$ O(V⋅E⋅log(V2/E)$O(V^2 \sqrt E$$O(V \cdot E \cdot log(V^2 / E))$