Débit maximal avec Ford-Fulkerson et DFS

22

Cette question concerne la complexité temporelle de l' algorithme de flux maximal de Ford-Fulkerson lors de l'utilisation de DFS pour trouver des chemins d'augmentation.

Il existe un exemple bien connu montrant qu'en utilisant DFS, on peut avoir besoin d'un nombre linéaire d'itérations dans le flux maximal, voir par exemple la page Wikipedia liée à ci-dessus.

Cependant, je ne suis pas vraiment convaincu par cet exemple: une implémentation DFS standard ne présenterait pas le comportement d'alternance entre B et C comme premier nœud du chemin (en utilisant les noms de vertex de la page Wikipedia).

Donc, imposons la condition très naturelle que chaque fois que le DFS visite un nœud , il examine toujours les voisins de dans le même ordre. Existe-t-il encore des exemples pour lesquels FF avec DFS utilise un grand nombre d'itérations?uu

En variante, supposons que nous ayons la propriété supplémentaire que les différents ordres de voisins soient cohérents avec un ordre global arbitraire mais fixe des sommets. Cela fait-il une différence?

Cela me semble être une question assez basique; Je m'excuse à l'avance si la réponse est bien connue mais je ne suis pas un expert des flux et certains googleurs n'ont rien trouvé.

Edit: La réponse s'avère être oui, il y a encore des exemples. Voir la figure 2 de ce document . Dans ces exemples, FF avec DFS prend un nombre exponentiel (en nombre de sommets) d'itérations. Il semble facile de prouver que c'est serré, c'est-à-dire que le nombre d'itérations est toujours limité par (quelles que soient les valeurs des capacités).2O(n)

ds.algorithms reference-request max-flow Per Austrin
la source
4
Je me suis interrogé sur la même question.
Luca Trevisan
1
(1) Belle question. (2) Je pense que l'exemple du mauvais cas (comme celui de Wikipedia) est généralement présenté comme une raison pour laquelle une certaine réflexion sur l'ordre de visite est nécessaire, et non comme une raison contre l'utilisation de la recherche en profondeur d'abord.
Tsuyoshi Ito
6
Je ne pense pas que je puisse maintenant enseigner la FF sans réponse à cette question. Agréable !!
Suresh Venkat
N'est-ce pas trouver le débit maximum dans un nombre minimal d'itérations NP-Complete?
user834

Réponses:

13

Si les listes d'adjacence sont fixées à l'avance, DFS se termine toujours (même s'il existe des capacités irrationnelles).

Voir Dean, Goemans, Immorlica - Finite Fin of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data .

ilyaraz
la source
11
Merci. Cela ne répond pas en soi à ma question, cependant, l'exemple donné dans la figure 2 du document Dean-Goemans-Immorlica montre une construction récursive basée sur l'exemple standard, qui répond à ma question et montre que FF avec DFS peut nécessiter de manière exponentielle beaucoup itérations.
Per Austrin