Problème de flot maximum

Un exemple de graphe de flot avec un flot maximum. la source est ${\displaystyle s}$, et le puits ${\displaystyle t}$. Les nombres indiquent le flot et la capacité.

Le problème de flot maximum consiste à trouver, dans un réseau de flot, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum[1]. Quelquefois^[Quand ?], on ne s'intéresse qu'à la valeur de ce flot. Le s-t flot maximum (depuis la source s vers le puits t) est égal à la s-t coupe minimum du graphe, comme l'indique le théorème flot-max/coupe-min.

Applications

Ce type de problème est proche de ce qui est rencontré dans le remplissage optimisé de boîtes. On peut également utiliser des approches de flot maximum pour résoudre des problèmes de gestion d'écoulements dans des réseaux (égouts, conduites d'eau, trafic routier...).
Durant la Guerre froide, le problème de flot maximum est utilisé par l'US Air Force afin d'impacter au maximum le réseau ferré de l'Union Soviétique[2].

Algorithmes

Étant donné un graphe orienté ${\displaystyle G=(V,E)}$, où chaque arc ${\displaystyle u,v}$ a une capacité ${\displaystyle c(u,v)}$, on cherche un flot maximum ${\displaystyle f}$ depuis la source ${\displaystyle s}$ vers le puits ${\displaystyle t}$, sous contrainte de capacité. Différents algorithmes ont été développés pour résoudre ce problème de complexités différentes. On utilise, dans la description des complexités, la notation simplifiée qui remplace le cardinal d'un ensemble par l'ensemble lui-même : on écrit ${\displaystyle O(VE^{2})}$ au lieu de ${\displaystyle O(|V||E|^{2})}$.

Algorithme	Complexité	Description
Programmation linéaire		Les contraintes sont données par flot admissible, où on considère comme admissible un flot qui n'excède pas la capacité d'un arc. On maximise ${\displaystyle \sum _{v\in V}f(s,v)}$
Algorithme de Ford-Fulkerson	${\displaystyle O(E\cdot {\mathit {flotmax}})}$ dans le cas entier	Tant qu'il existe un chemin entre la source et le puits dans le graphe résiduel, envoyer le minimum des capacités résiduelles sur ce chemin.
Algorithme d'Edmonds-Karp	${\displaystyle O(VE^{2})}$	Spécialisation de l'algorithme de Ford-Fulkerson, où les chemins augmentants sont des plus courts chemins (en nombre d'arcs) dans le graphe résiduel (on utilise un parcours en largeur)
Algorithme de flot bloquant de Dinitz	${\displaystyle O(V^{2}E)}$	À chaque phase l'algorithme construit un graphe en couches avec une recherche en profondeur d'abord sur le graphe résiduel. Le flot maximum dans le graphe en couche peut être calcule en temps ${\displaystyle O(VE)}$, et le nombre maximum de phase est de ${\displaystyle |V|-1}$.
Algorithme de flot maximum par poussage/réétiquetage	${\displaystyle O(V^{2}E)}$	Cet algorithme maintient un préflot, i.e. une fonction de flot avec une possibilité d'excès dans les sommets. L'algorithme fonctionne tant qu'il existe un sommet avec un excès strictement positif, appelé sommet actif du graphe. L'opération de poussage augmente le flot sur une arête résiduelle, et une fonction de hauteur contrôle sur les sommets contrôle quelles arêtes résiduelles doivent être poussées. Cette fonction est changée avec la fonction d'étiquetage. Les définitions de ces opérations garantissent que le flot résultant est un flot maximum.
Poussage/réétiquetage avec règle de sélection des sommets par FIFO	${\displaystyle O(V^{3})}$	Variante qui sélectionne toujours le sommet le plus actif formellement, et fait les opérations jusqu'à ce que l'excès soit positif ou qu'il existe des arêtes résiduelles admissibles depuis ce sommet.
Algorithme de flot bloquant de Dinitz avec arbre dynamique[3]	${\displaystyle O(VE\log(V))}$	La structure d'arbre dynamique accélère le calcul de flot maximum dans le graphe en couche pour obtenir ${\displaystyle O(E\log(V))}$ par phase.
Poussage/re-étiquetage avec usage des arbres dynamiques[4]	${\displaystyle O(VE\log(V^{2}/E))}$	L'algorithme construit des arbres de taille limitée sur le graphe résiduel en considérant la fonction de hauteur, ces arbres fournissent des opérations de poussage multi-niveau.
Algorithme de flot bloquant binaire[5]	${\displaystyle O\left(E\cdot \min(V^{\frac {2}{3}},{\sqrt {E}})\cdot \log {\frac {V^{2}}{E}}\log {U}\right)}$	La valeur ${\displaystyle U}$ correspond à la capacité maximum du réseau.
KRT : Algorithme de King, Rao et Tarjan[6]	${\displaystyle O(EV\log _{\frac {E}{V\log V}}V)}$
Algorithme de James B Orlin + KRT[7]	${\displaystyle O(VE)}$	L'algorithme d'Orlin calcule le flot maximum en temps O(VE) pour ${\displaystyle E\leq O(V^{{16 \over 15}-\epsilon })}$ et KRT résout le problème en O(VE) pour ${\displaystyle E>V^{1+\epsilon }}$.
Algorithme de Chen, Kyng, Liu, Peng, Gutenberg et Sachdeva [8]	${\displaystyle O(E^{1+o(1)})}$	L'algorithme de Chen, Kyng, Liu, Peng, Gutenberg et Sachdeva' résout le problème de flot maximum et cout minimum en temps presque linéaire en construisant le flot par une série de ${\displaystyle E^{1+o(1)}}$ cycles non-orientés de ratios minimums approchés, chacun calculé et utilisé en temps amorti ${\displaystyle E^{o(1)}}$ avec une structure de donnée dynamique.

Une liste plus complète figure dans le livre de Cormen, Leiserson, Rivest et Stein[1]. Le problème du flot maximal est complet pour la classe P[9].

Extensions

Le problème du flot maximum peut être vu comme un cas particulier de plusieurs autres problèmes de flots dans les réseaux, comme le flot multi-commodités.

Références bibliographiques

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Maximum flow problem » (voir la liste des auteurs).

1. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Cambridge, MIT Press and McGraw-Hill, 2001, 2^e éd., 1180 p., relié (ISBN 978-0-262-53196-2, LCCN 2001031277), « Chap. 26. Maximum Flow », p. 643–700.
2. (en) Alexander Schrijver, « On the history of the transportation and maximum flow problems », Mathematical programming,‎ 2023 (lire en ligne)
3. (en) Daniel D. Sleator and Robert E. Tarjan, « A data structure for dynamic trees », Journal of Computer and System Sciences, vol. 26, n^o 3,‎ 1983, p. 362–391 (ISSN 0022-0000, DOI 10.1016/0022-0000(83)90006-5, lire en ligne).
4. (en) Andrew V. Goldberg and Robert E. Tarjan, « A new approach to the maximum-flow problem », Journal of the ACM, New York, NY, USA, ACM Press, vol. 35, n^o 4,‎ 1988, p. 921–940 (ISSN 0004-5411, DOI 10.1145/48014.61051).
5. (en) Andrew V. Goldberg and S. Rao, « Beyond the flow decomposition barrier », J. Assoc. Comput. Mach., vol. 45,‎ 1998, p. 753–782 (DOI 10.1145/290179.290181).
6. V. King, S. Rao et R. Tarjan, « A Faster Deterministic Maximum Flow Algorithm », Journal of Algorithms, vol. 17, n^o 3,‎ 1994, p. 447–474 (DOI 10.1006/jagm.1994.1044)
7. James B. Orlin, « Max flows in O(nm) time, or better », STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing,‎ 2013, p. 765–774 (DOI 10.1145/2488608.2488705)
8. L. Chen, R. Kyng, Y.P. Liu, M.P. Gutenberg et S. Sachdeva, « Maximum Flow and Minimum-Cost Flow in Almost-Linear Time », preprint ArXiv,‎ 2022
9. (en) « The maximum flow problem is log space complete for P », Theoretical Computer Science, vol. 21, n^o 1,‎ 1^er octobre 1982, p. 105–111 (ISSN 0304-3975, DOI 10.1016/0304-3975(82)90092-5, lire en ligne, consulté le 8 novembre 2018)

Articles connexes

• Problème du flot de coût minimum

Lien externe

• (en) Bibliothèque C++ Lemon avec plusieurs implémentations du flot maximum