Calcule un flujo máximo a partir de un corte mínimo

Sabemos que calcular un flujo máximo resp. un corte mínimo de una red con capacidades es equivalente; cf. el teorema de corte mínimo y flujo máximo .

Tenemos algoritmos (más o menos eficientes) para calcular los flujos máximos, y calcular un corte mínimo dado un flujo máximo tampoco es difícil ni costoso.

¿Pero qué pasa con el reverso? Dado un corte mínimo, ¿cómo podemos determinar un flujo máximo? Sin resolver Max-Flow desde cero, por supuesto, y preferiblemente más rápido que eso también.

Algunos pensamientos:

Desde el corte mínimo, sabemos el valor de flujo máximo. No veo cómo esta información ayuda a los enfoques estándar de ruta de aumento y re-etiquetado, aunque la adaptación de este último parece un poco más plausible.
No podemos usar el corte mínimo para dividir la red en dos partes y recurrir ya que eso no reducirá el problema en el peor de los casos (si una partición es un singleton); Tampoco tendríamos un corte mínimo de las instancias más pequeñas.
¿Conocer el valor del flujo máximo acelera la resolución del Max-Flow LP, tal vez a través de las condiciones de holgura complementarias?

algorithms graphs network-flow Rafael
fuente

Pregunta relacionada: ¿conocemos algoritmos para calcular cortes mínimos (que no usan algoritmos de flujo máximo)?

Raphael

Definitivamente lo hacemos, el algoritmo aleatorio de Karger es muy popular, y no necesitas ningún conocimiento de los flujos máximos para eso.

Juho

Si no desea algoritmos aleatorios, el algoritmo Stoer-Wagner es muy simple, también sin técnicas de flujo.

Juho

¡Buen material! Hay otro desafío aquí. Conocer solo el min-cut transmite

bits de información (como máximo), ya que cada corte es isomorfo a un subconjunto de

. Sin embargo, un flujo máximo puede necesitar mucho más que

bits de información para representar (especialmente si las capacidades son grandes). Entonces, teóricamente, la información no puede esperar un algoritmo que solo mire el corte y escupe el flujo; también necesitaría mirar el gráfico y hacer algunos cálculos adicionales. (Me doy cuenta de que esto no es una gran barrera.)

| V |

$|V|$

V

$V$

| V |

$|V|$

Respuestas:

En el peor de los casos, el corte mínimo en sí mismo no transmite mucha información sobre el flujo máximo. Considere una gráfica en la cual el mínimo -cut tiene valor . Si extiendo agregando un nuevo vértice y un borde con peso , un mínimo -cut en el nuevo gráfico consiste solo en el borde $G=(V,E)$ $s,t$ $w$ $G$ $s'$ $(s',s)$ $w$ $s',t$ $(s', s)$ pero eso no proporciona ninguna información sobre cómo obtener unidades de flujo de a . $w$ $s$ $t$

Efectivamente, el corte mínimo le indica el valor del flujo, pero no cómo lograrlo. Esto significa que conocer el corte mínimo puede acelerar la búsqueda del flujo como máximo por un factor logarítmico, ya que podríamos hacer una búsqueda binaria para encontrar el valor del corte.

Tom van der Zanden
fuente

Pero ese factor logarítmico estaría en el tamaño del intervalo de valores de flujo potenciales, por lo tanto incomparable con los límites superiores existentes para resolver el flujo máximo que solo depende del tamaño del gráfico. Dicho esto, incluso una aceleración logarítmica sería de interés. No estoy convencido de que conocer el valor de un flujo máximo no ayude en absoluto.

Raphael

-2

Ciertamente existen algoritmos que le permiten calcular el corte mínimo antes de calcular el flujo máximo. Dos de estos algoritmos son los algoritmos de relé de empuje y pseudoflow que están estrechamente relacionados. Este último es más eficiente. Ambos algoritmos usan propiedades especiales del gráfico residual que mejoran iterativamente para derivar el flujo máximo del corte mínimo. Para más detalles, recomiendo leer el código y los documentos.

Para profundizar en el caso de la etiqueta de empuje, cuando el algoritmo no puede empujar más flujo hacia el sumidero, se garantiza que ha calculado un corte mínimo. Esta parte del algoritmo se llama fase 1 por falta de un nombre mejor. La Fase 2 es la etapa más eficiente donde transforma el corte mínimo en un flujo máximo al cancelar iterativamente los ciclos en el gráfico residual usando una primera búsqueda de profundidad única y empujando el exceso de regreso a la fuente. Creo que se puede demostrar que la fase 2 es asintomáticamente más eficiente que la fase 1.

ldog
fuente

Por favor, vuelva a leer la pregunta; no es el que respondiste.

Raphael

El ejemplo de relaciones públicas que di supone que ha calculado otra información en el camino mientras calculaba min-cut. Su pregunta original no especificó si se le permitió mantener otra información junto con el corte mínimo para facilitar el cálculo del flujo máximo posterior. ¿Es justo declarar su pregunta original como "Dado un corte mínimo y ninguna otra información , cómo podemos determinar un flujo máximo?".

ldog

Dije, "dado A, calcular B". La única suposición razonable es que solo se le da A, de lo contrario, hablar de problemas computacionales sería un asunto muy confuso.

Raphael

Siento disentir. Desde una perspectiva práctica, nunca calcularía un corte mínimo sin calcular información adicional (como la del algoritmo PR). Desde una perspectiva teórica, sería bueno considerar las cosas de manera aislada como usted dice. El contexto es clave aquí.

ldog