¿Podría el corte mínimo ser más fácil que el flujo de red?

18

Gracias al teorema de corte mínimo de flujo máximo, sabemos que podemos usar cualquier algoritmo para calcular un flujo máximo en un gráfico de red para calcular un corte -min. Por lo tanto, la complejidad de calcular un corte mínimo ( s , t ) no es más que la complejidad de calcular un flujo máximo ( s , t ) .(s,t)(s,t)(s,t)

¿Podría ser menos? ¿Podría haber un algoritmo para calcular un corte mínimo que sea más rápido que cualquier algoritmo de flujo máximo?(s,t)

Traté de encontrar una reducción para reducir el problema ) -max-flow al problema ( s , t ) -min-cut, pero no pude encontrar una. Lo primero que pensé fue usar un algoritmo de divide y vencerás: primero busca un corte mínimo, que separa el gráfico en dos partes; ahora encuentre recursivamente un flujo máximo para la parte izquierda y un flujo máximo para la parte derecha, y combínelos con todos los bordes que cruzan el corte. De hecho, esto funcionaría para producir un flujo máximo, pero su peor tiempo de ejecución podría ser tanto como O ( | V | ) veces mayor que el tiempo de ejecución del algoritmo de corte mínimo. ¿Hay una mejor reducción?(s,t(s,t)O(|V|)

Me doy cuenta de que el teorema de corte mínimo de flujo máximo muestra que la complejidad de calcular el valor de un flujo máximo es la misma que la complejidad de calcular la capacidad de un corte mínimo, pero eso no es lo que estoy preguntando. Estoy preguntando sobre el problema de encontrar un flujo máximo y encontrar un corte mínimo (explícitamente).

Esto está muy relacionado con Calcular un flujo máximo a partir de un corte mínimo , excepto: (1) Estoy dispuesto a permitir reducciones de Cook (reducciones de Turing), no solo reducciones de Karp (reducciones de muchos) y (2) quizás dado podemos encontrar algún gráfico G ' tal que el corte mínimo de G ' facilite el cálculo del flujo máximo de G , que es algo que está fuera del alcance de esa otra pregunta.GG′G′G

complexity-theory reductions network-flow graph-algorithms DW
fuente
2
@AshkanKzme, no te estoy siguiendo; ¿puedes elaborar? Como afirmo en el cuarto párrafo de la pregunta, el teorema de corte mínimo de flujo máximo muestra que el valor del flujo máximo es igual a la capacidad del corte mínimo. Sospecho que esto es lo que estás pensando. Sin embargo, conocer el valor del flujo máximo no le indica el flujo máximo en sí mismo (por ejemplo, cuánto enviar en cada borde en particular). Esta pregunta es acerca de la complejidad de calcular el flujo máximo en sí mismo, en comparación con calcular el corte mínimo en sí. Mi pregunta es exactamente como se indica en el segundo párrafo de la pregunta.
DW
2
@AshkanKzme, No, no hice ninguna suposición errónea. Está suponiendo implícitamente que Ford-Fulkerson es el algoritmo más rápido posible para encontrar un corte mínimo ... pero que yo sepa, nadie lo ha probado nunca, y no sabemos si eso es correcto o no. Me parece que está cometiendo el error estándar de novato con pruebas de límite inferior: "No veo ninguna forma de resolver este problema más rápido, por lo que debe ser imposible". (Sal. ¿Me estás diciendo cosas de libro de texto estándar sobre-flujo máximo min de corte aprecio su intento de ayuda, pero ya estoy familiarizado con ese ...)
DW
1
En cuanto a su afirmación "Creo que se puede probar que si solo tiene el corte mínimo, puede obtener el flujo máximo", bueno, le animo a que escriba una respuesta con la prueba de eso, porque eso es básicamente lo que Mi pregunta es preguntar. Nunca he visto una prueba de eso, pero si lo has hecho, ¡espero que lo escribas!
DW
1
@DW Creo que ahora tengo la pregunta un poco mejor. Creo que me disgustó el hecho de que le das una reducción polinomial de turing. ¿No necesitaría una reducción constante de turing para demostrar , mientras que incluso probar que no existe tal reducción posible no lo refuta? f(n)=Θ(g(n))
Thomas Bosman
1
@ThomasBosman, sí, eso es correcto. [Perdón por confundirte. La reducción que di en la pregunta prueba que , que es un límite inferior muy débil. Espero que haya una reducción que pruebe que f ( n ) = Ω ( g ( n ) ) , pero no sé cómo construir tal cosa.]f(n)=Ω(g(n)/n)f(n)=Ω(g(n))
DW

Respuestas:

-1

Aquí hay un posible enfoque:

Suponga que conoce el corte S, luego encontrar el flujo de a t es un problema de flujo de red de costo mínimo con costo cero, ya que conoce exactamente el flujo de salida en cada vértice en V ∖ S y en el flujo de entrada en t . Suponga que f denota un flujo S - t y A la matriz de arco de nodo (es decir, la fila i , col j tiene 1 si i es la cola de j , -1 si es la cabeza, de lo contrario cero), y deje que bStV∖StfS−tAijijb tal que si fAf=bfSatisface la oferta / demanda y la conservación del flujo. Luego, con la eliminación gaussiana, podemos encontrar una solución factible en operaciones.|V|3

Para encontrar un corte de un flujo necesitamos construir el gráfico residual que toma como máximo tiempo, y luego potencialmente atravesar | V | vértices |E||V|

Entonces, para gráficos completos y el corte mínimo es solo la fuente o solo el sumidero, la reducción toma el mismo tiempo en ambas direcciones en el peor de los casos. Sin embargo, creo que encontrar una solución factible para se puede hacer más rápido que | V | 3 dada la estructura especial. Sin embargo, no estoy seguro de cómo probar eso.Af=b|V|3

Thomas Bosman
fuente
No entiendo cómo encontrar usando la eliminación gaussiana. Tenemos | V | ecuaciones lineales en | E | incógnitas Por lo general | E | > | V | , por lo que no tendremos suficientes ecuaciones para determinar de forma exclusiva las incógnitas. ¿Hay algún truco que estoy pasando por alto? f|V||E||E|>|V|
DW
Tampoco soy un experto en esto, así que puedo estar equivocado. Pero el hecho de que no haya una solución única parece facilitarlo. Si lo reduce a fila en forma escalonada reducida, tiene Columnas independientes. Entonces, la solución única de esa submatriz yb , combinada con flujo cero para todas las otras columnas produciría una solución no única, que no es un problema per se. El problema que puedo prever es que f viola las limitaciones de capacidad, pero intuitivamente diría que hay una manera de sortear esto directamente|V|bf
Thomas Bosman
Af=b
Mierda eso es correcto. Puede agregar las restricciones (superior e inferior), que sabe que tiene una solución, pero luego tiene | V | +2 | E | filas para que sea más lento que simplemente calcular el flujo máximo directamente.
Thomas Bosman
El otro problema es que las restricciones de capacidad son desigualdades (no igualdades), por lo que no puede usar la eliminación gaussiana: necesitaría usar programación lineal, que como usted dice, no parece ser más rápido que simplemente calcular el flujo máximo directamente.
DW