La réduction minimale pourrait-elle être plus facile que le flux réseau?

18

Grâce au théorème de min-cut max-flow, nous savons que nous pouvons utiliser n'importe quel algorithme pour calculer un flux maximum dans un graphe de réseau pour calculer une -min-cut. Par conséquent, la complexité du calcul d'une coupe minimale n'est pas plus que la complexité du calcul d'un débit maximal .( s , t ) ( s , t )(s,t)(s,t)(s,t)

Serait-ce moins? Pourrait-il y avoir un algorithme pour calculer une coupe minimale plus rapide que n'importe quel algorithme de débit maximal?(s,t)

J'ai essayé de trouver une réduction pour réduire le problème ) -max-flow au problème -min-cut, mais je n'ai pas pu en trouver un. Ma première pensée a été d'utiliser un algorithme de division et de conquête: trouver d'abord un min-cut, qui sépare le graphique en deux parties; trouver maintenant récursivement un max-flow pour la partie gauche et un max-flow pour la partie droite, et les combiner avec tous les bords traversant la coupe. Cela fonctionnerait en effet pour produire un débit maximum, mais son pire temps de fonctionnement pourrait être autant que fois plus grand que le temps de fonctionnement de l'algorithme de coupure min. Y a-t-il une meilleure réduction?( s , t ) O ( | V | )(s,t(s,t)O(|V|)

Je me rends compte que le théorème de min-cut max-flow montre que la complexité du calcul de la valeur d'un max-flow est la même que la complexité du calcul de la capacité d'un min-cut, mais ce n'est pas ce que je demande. Je pose la question du problème de trouver un max-flow et de trouver un min-cut (explicitement).

Ceci est très étroitement lié au calcul d'un débit maximal à partir d'une coupe minimale , sauf: (1) je suis prêt à autoriser les réductions Cook (réductions Turing), pas seulement les réductions Karp (plusieurs réductions), et (2) peut-être, étant donné nous pouvons trouver un graphique tel que la coupe minimale de facilite le calcul du débit maximal de , ce qui est hors de portée pour cette autre question.G ′ G ′ GGG′G′G

complexity-theory reductions network-flow graph-algorithms DW
la source
2
@AshkanKzme, je ne vous suis pas; peux-tu élaborer? Comme je l'indique dans le 4ème paragraphe de la question, le théorème de la coupe minimale du débit maximal montre que la valeur du débit maximal est égale à la capacité de la coupe minimale. Je pense que c'est à cela que vous pensez. Cependant, connaître la valeur du max-flow ne vous dit pas le max-flow lui-même (par exemple, combien envoyer sur chaque front particulier). Cette question porte sur la complexité du calcul du max-flow lui-même, par rapport au calcul du min-cut lui-même. Ma question est exactement celle qui est énoncée au 2e paragraphe de la question.
DW
2
@AshkanKzme, Non, je n'ai fait aucune hypothèse erronée. Vous supposez implicitement que Ford-Fulkerson est l'algorithme le plus rapide possible pour trouver un min-cut ... mais pour autant que je sache, personne ne l'a jamais prouvé, et nous ne savons pas si c'est correct ou non. Il me semble que vous faites l'erreur de recrue standard avec des preuves de limite inférieure: "Je ne vois aucun moyen de résoudre ce problème plus rapidement, donc cela doit être impossible". (PS Vous me dites des trucs standard sur le max-flow min-cut. J'apprécie votre tentative d'aider, mais je le connais déjà ...)
DW
1
En ce qui concerne votre déclaration "Je pense qu'il peut être prouvé que si vous n'avez que le min-cut, vous pouvez obtenir le débit maximum", eh bien, je vous encourage à écrire une réponse avec la preuve de cela - parce que c'est essentiellement ce que ma question demande. Je n'en ai jamais vu de preuve, mais si c'est le cas, j'espère que vous l'écrirez!
DW
1
@DW Je pense que je comprends mieux la question maintenant. Je pense que j'ai été rebuté par le fait que vous donniez une réduction de turing polynomiale. N'auriez-vous pas besoin d'une réduction de Turing constante pour prouver , alors que même prouver qu'une telle réduction n'est pas possible ne la réfute pas? f(n)=Θ(g(n))
Thomas Bosman
1
@ThomasBosman, oui, c'est exact. [Désolé de vous rendre confus. La réduction que j'ai donnée dans la question prouve que , qui est une borne inférieure très faible. J'espère qu'il pourrait y avoir une réduction qui prouve que f ( n ) = Ω ( g ( n ) ) , mais je ne sais pas comment construire une telle chose.]f(n)=Ω(g(n)/n)f(n)=Ω(g(n))
DW

Réponses:

-1

Voici une approche possible:

Supposons que vous connaissiez la coupe S, puis trouver le flux de vers t est un problème de flux de réseau à coût min avec un coût nul, car vous connaissez exactement le flux sortant à chaque sommet de V ∖ S et à l'entrée à t . Supposons que f désigne un flux S - t et A la matrice nœud-arc (c'est-à-dire que la ligne i , col j a 1 si i est la queue de j , -1 si c'est la tête, zéro sinon), et soit b tel que A f = b si fStV∖StfS−tAijijbAf=bfsatisfait l'offre / la demande et la conservation des flux. Ensuite, avec l'élimination gaussienne, nous pouvons trouver une solution réalisable dans opérations.|V|3

Pour trouver une coupe à partir d'un flux, nous devons construire le graphe résiduel qui prend au plus temps, puis potentiellement traverser | V | sommets. |E||V|

Ainsi, pour des graphiques complets et la coupe minimale n'étant que la source ou le puits, la réduction prend le même temps dans les deux directions dans le pire des cas. Cependant, je pense que trouver une solution réalisable à peut être fait plus rapidement que | V | 3 étant donné la structure spéciale. Je ne sais pas comment le prouver.Af=b|V|3

Thomas Bosman
la source
Je ne comprends pas comment trouver utilisant l'élimination gaussienne. Nous avons | V | équations linéaires en | E | inconnues. Habituellement | E | > | V | , nous n'aurons donc pas assez d'équations pour déterminer de manière unique les inconnues. Y a-t-il une astuce que je néglige? f|V||E||E|>|V|
DW
|V|bf
Af=b
Merde c'est vrai. Vous pouvez ajouter les contraintes (supérieures et inférieures), dont vous savez qu'elles ont une solution, mais vous avez alors | V | +2 | E | lignes de sorte que ce serait plus lent que de calculer directement le débit max.
Thomas Bosman
L'autre problème est que les contraintes de capacité sont des inégalités (pas des égalités), donc vous ne pouvez pas utiliser l'élimination gaussienne: vous devez utiliser une programmation linéaire qui, comme vous le dites, ne semble pas être plus rapide que le simple calcul de la débit max directement.
DW