Calculer un débit max à partir d'une coupe min

Nous savons que le calcul d'un débit maximal resp. une coupure minimale d'un réseau avec des capacités est équivalente; cf. le théorème de min-cut max-flow .

Nous avons des algorithmes (plus ou moins efficaces) pour calculer les débits maximaux, et calculer une coupure minimale étant donné un débit maximal n'est ni difficile ni coûteux non plus.

Mais qu'en est-il de l'inverse? Compte tenu d'une coupe minimale, comment déterminer un débit maximal? Sans résoudre Max-Flow à partir de zéro, bien sûr, et de préférence plus vite que cela aussi.

Quelques idées:

De la coupe minimale, nous connaissons la valeur de débit maximale. Je ne vois pas comment ces informations aident les approches standard augmentant-path et push-relabel, bien que l'adaptation de ces dernières semble légèrement plus plausible.
Nous ne pouvons pas utiliser la coupure minimale pour diviser le réseau en deux parties et recurse car cela ne réduira pas le problème dans le pire des cas (si une partition est un singleton); nous n'aurions pas non plus de coupe minimale des petites instances.
Connaître la valeur du débit maximum accélère-t-il la résolution du Max-Flow LP, peut-être via les conditions de relâchement complémentaires?

algorithms graphs network-flow Raphael
la source

Question connexe: connaissons-nous des algorithmes pour calculer les coupes minimales (qui n'utilisent pas les algorithmes de débit maximal)?

Raphael

Nous le faisons certainement, l'algorithme randomisé de Karger est très populaire, et vous n'avez besoin d'aucune connaissance des flux max pour cela.

Juho

Si vous ne voulez pas d'algorithmes randomisés, l'algorithme de Stoer-Wagner est très simple, également sans techniques de flux.

Juho

Bon produit! Il y a un autre défi ici. Connaître uniquement les véhicules min-cut

des bits d'information (au plus), étant donné que chaque coupe est isomorphe à un sous - ensemble de

. Cependant, un débit max peut nécessiter beaucoup plus que

des bits d'information à représenter (surtout si les capacités sont importantes). Donc, théoriquement, vous ne pouvez pas espérer un algorithme qui ne regarde que la coupe et crache le flux; il faudrait également regarder le graphique et effectuer des calculs supplémentaires. (Je me rends compte que ce n'est pas vraiment un obstacle.)

| V |

$|V|$

V

$V$

| V |

$|V|$

Réponses:

Dans le pire des cas, la coupe minimale elle-même ne transmet pas beaucoup d'informations sur le débit maximal. Considérons un graphe dans lequel le minimum -cut a la valeur . Si j'étends en ajoutant un nouveau sommet $G=(V,E)$ $s,t$ $w$ $G$ et une arête avec le poids , un minimum -cut dans le nouveau graphique se compose uniquement de l'arête $s'$ $(s',s)$ $w$ $s',t$ $(s', s)$ mais cela ne donne aucune information sur la façon d'obtenir unités de flux de à . $w$ $s$ $t$

En effet, la coupe minimale vous indique la valeur du débit, mais pas comment y parvenir. Cela signifie que connaître la coupure minimale peut accélérer la recherche du débit par au plus un facteur logarithmique, car nous pourrions faire une recherche binaire pour trouver la valeur de la coupure.

Tom van der Zanden
la source

Mais ce facteur logarithmique serait lié à la taille de l'intervalle des valeurs de débit potentiel, donc incomparable aux limites supérieures existantes pour la résolution du débit maximal qui ne dépend que de la taille du graphique. Cela dit, même une accélération logarithmique serait intéressante. Je ne suis pas convaincu que connaître la valeur d'un max-flow n'aide pas du tout.

Raphael

-2

Il existe certainement des algorithmes qui vous permettent de calculer le min cut avant de calculer le maxflow. Deux de ces algorithmes sont le push ré-étiquetage et les algorithmes pseudoflow qui sont étroitement liés. Ce dernier est plus efficace. Ces deux algorithmes utilisent des propriétés spéciales du graphe résiduel qu'ils améliorent de manière itérative pour dériver le débit maximal de la coupe minimale. Pour plus de détails, je recommande fortement de lire le code et les articles.

Pour élaborer sur le cas du réétiquetage push, lorsque l'algorithme ne peut plus envoyer de flux vers l'évier, il est garanti d'avoir calculé une coupe minimale. Cette partie de l'algorithme est appelée phase 1 faute d'un meilleur nom. La phase 2 est l'étape la plus efficace où elle transforme la coupe minimale en débit maximal en annulant de manière itérative les cycles dans le graphique résiduel en utilisant une première recherche de profondeur unique et en repoussant l'excès vers la source. Je crois que la phase 2 peut être prouvée asymptomatiquement plus efficace que la phase 1.

ldog
la source

Veuillez relire la question; ce n'est pas celle à laquelle vous avez répondu.

Raphael

L'exemple de PR que j'ai donné suppose que vous avez calculé d'autres informations en cours de route pendant que vous calculiez le min-cut. Votre question d'origine ne précisait pas si vous étiez autorisé à conserver d'autres informations avec le min-cut pour faciliter le calcul de maxflow ultérieur. Est-il juste de dire que votre question initiale était "étant donné une coupe minimale et aucune autre information , comment pouvons-nous déterminer un débit maximal?".

ldog

J'ai dit: "étant donné A, calculez B". La seule hypothèse raisonnable est que l'on ne vous donne que A, sinon parler de problèmes de calcul serait une affaire très floue.

Raphael

Je ne suis pas d'accord. D'un point de vue pratique, vous ne calculeriez jamais un min-cut sans calculer des informations supplémentaires (telles que celles de l'algorithme PR). D'un point de vue théorique, il pourrait être agréable de considérer les choses isolément comme vous le dites. Le contexte est essentiel ici.

ldog