Flujo máximo con Ford-Fulkerson y DFS

22

Esta pregunta es sobre la complejidad temporal del algoritmo de flujo máximo de Ford-Fulkerson cuando se usa DFS para encontrar rutas de aumento.

Hay un ejemplo bien conocido que muestra que el uso de DFS puede necesitar un número lineal de iteraciones en el flujo máximo; consulte, por ejemplo, la página de Wikipedia vinculada anteriormente.

Sin embargo, no estoy realmente convencido con este ejemplo: una implementación estándar de DFS no exhibiría el comportamiento de alternar entre B y C como primer nodo de la ruta (usando los nombres de vértices de la página de Wikipedia).

Entonces, impongamos la condición muy natural de que cada vez que el DFS visita un nodo , siempre examina a los vecinos de u en el mismo orden. ¿Todavía hay ejemplos para los que FF con DFS usa una gran cantidad de iteraciones?uu

Como variante, suponga que tenemos la propiedad adicional de que los diferentes ordenamientos de vecinos son consistentes con algún ordenamiento global arbitrario pero fijo de los vértices. Eso hace una diferencia?

Esto me parece una pregunta bastante básica; Pido disculpas de antemano si la respuesta es conocida, pero no soy un experto en flujos y algunas búsquedas en Google no arrojaron nada.

Editar: La respuesta resulta ser sí, todavía hay ejemplos. Ver Figura 2 de este documento . En estos ejemplos, FF con DFS toma un número exponencial (en el número de vértices) de iteraciones. Parece fácil demostrar que esto es estricto, es decir, que el número de iteraciones siempre está limitado por (independientemente de los valores de las capacidades).2O(n)

Por Austrin
fuente
44
Me he preguntado sobre la misma pregunta.
Luca Trevisan
1
(1) Buena pregunta. (2) Creo que el mal ejemplo de los casos (como el de Wikipedia) por lo general se presenta como una razón por alguna consideración acerca el fin de visitar es necesario, no como una razón contra el uso de búsqueda en profundidad.
Tsuyoshi Ito
66
No creo que ahora pueda enseñar FF sin una respuesta a esta pregunta. Agradable !!
Suresh Venkat
¿No encuentra el flujo máximo en un número mínimo de iteraciones NP-Complete?
usuario834

Respuestas:

13

Si las listas de adyacencia se arreglan por adelantado, DFS siempre termina (incluso si hay capacidades irracionales).

Ver Dean, Goemans, Immorlica: terminación finita de los algoritmos de "ruta de aumento" en presencia de datos de problemas irracionales .

ilyaraz
fuente
11
Gracias. Eso en sí mismo no responde a mi pregunta, sin embargo, el ejemplo dado en la Figura 2 del documento de Dean-Goemans-Immorlica muestra una construcción recursiva basada en el ejemplo estándar, que responde a mi pregunta y muestra que FF con DFS puede requerir exponencialmente muchos iteraciones
Por Austrin