Flujo máximo incremental en gráficos dinámicos

Estoy buscando un algoritmo rápido para calcular el flujo máximo en gráficos dinámicos. es decir, considerando un gráfico y s , t ∈ V tenemos máximo flujo F en G de s a la t . Entonces nuevo / viejo nodo u añadido / borrado con sus correspondientes bordes para formar un gráfico G 1 . ¿Qué es un flujo máximo en un gráfico recién creado? ¿Hay alguna manera de evitar recalcular el flujo máximo?$G=(V,E)$$s,t\in V$$F$$G$$s$$t$$u$$G^1$

Se aprecia cualquier preprocesamiento que no consuma mucho tiempo / memoria.

La idea más simple es volver a calcular el flujo.

Otra idea simple es la siguiente: guardar todas las rutas de aumento que se usaron en el cálculo de flujo máximo anterior, para agregar un vértice , podemos encontrar rutas simples (en el gráfico de capacidad actualizado por paso anterior) que comienzan desde la fuente, van a la v y luego van al destino, pero el problema es que este camino debería ser simple, no pude encontrar mejor que O ( n ⋅ m ) para este caso, para m = | E | . (También tenga en cuenta que si solo se tratara de una ruta, esto podría hacerse en O ( n + m ) pero no es así).$v$$v$$O(n\cdot m)$$m=|E|$$O(n+m)$

También para eliminar el nodo anterior la idea no funciona.

También ya vi documentos como el enfoque incremental para bordes , pero parece que no son lo suficientemente buenos en este caso, es más que para cada borde y parece que no es una extensión adecuada en este caso (simplemente recalculamos un flujo). También actualmente estoy usando el algoritmo de flujo máximo de Ford-Fulkerson. Si hay una mejor opción para los algoritmos en línea, es bueno saberlo.$O(m)$

El enfoque descrito puede no ser teóricamente óptimo. Es solo una solución práctica simple que puede funcionar para el autor. No puedo proporcionar ninguna referencia porque siempre pensé que es un folklore ampliamente conocido, pero, curiosamente, nadie lo publicó en la respuesta. Entonces lo hago.

Supongamos que tenemos una red no dirigida . Suponga que está almacenado en una estructura de datos que permite inserciones / eliminaciones de vértices / arcos fáciles. A veces usaremos la red residual G f (es decir, con capacidades actualizadas c f = c - f ).$G=(V,E,c)$$G_f$$c_f = c - f$

La primera parte es cómo procesar inserciones / eliminaciones de vértices. Es más o menos sencillo para las inserciones:

1. Agregue un nuevo vértice con los bordes correspondientes a la red residual.
2. Encuentre un flujo máximo en la red residual actualizada utilizando un algoritmo de flujo máximo de su elección.

Para las eliminaciones las cosas se volvieron más complicadas. Imaginemos que dividimos el vértice estamos a punto de eliminar en 2 mitades V i n y V o U t tal que todos en-arcos puntos a v i n , todos fuera arcos va de V o U t y este nuevo vértices están conectados por un arco de capacidad infinita. Entonces, la eliminación de v es equivalente a la eliminación del arco entre v i n y v o u t . ¿Qué pasará en este caso? Vamos a denotar por f $v$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$v$$v_{in}$$v_{out}$$f^v$el flujo que pasa por el vértice . Entonces v i n experimentará el exceso de f v unidades de flujo y V o U t experimentarán escasez de f v unidades de flujo justo después de su eliminación (las restricciones de flujo serán obviamente rotos). Para que las restricciones de flujo se mantengan nuevamente, debemos reorganizar los flujos, pero también queremos mantener el valor del flujo original lo más alto posible. Veamos primero si podemos reorganizar sin disminuir el flujo total. Para verificar eso, encuentre un flujo máximo ~ f v de v i n a v o $v$$v_{in}$$f^v$$v_{out}$$f^v$$\tilde{f^v}$$v_{in}$ en la red residual "cortada" (es decir, sin el arco que conecta v i n y v o u t ). Deberíamos limitarlo por f v obviamente. Si resulta ser igual a f v, entonces tenemos suerte: hemos reasignado el flujo que pasaba porvde tal manera que no se modificó el flujo total. En el otro caso, el flujo total debe reducirse en exceso "inútil" deunidadesΔ= f v - ~ f v . Para hacer eso, Conecte temporalmentesy$v_{out}$$v_{in}$$v_{out}$$f^v$$f^v$$v$$\Delta = f^v - \tilde{f^v}$$s$$t$mediante un arco de capacidad infinita y ejecute el algoritmo maxflow nuevamente de a v o u t (debemos unir el flujo por Δ ). Eso arreglará la red residual y hará que las restricciones de flujo se mantengan nuevamente, disminuyendo automáticamente el flujo total en Δ .$v_{in}$$v_{out}$$\Delta$$\Delta$

La complejidad temporal de tales actualizaciones puede depender del algoritmo de maxflow que usemos. Sin embargo, los peores casos pueden ser bastante malos, pero aún así es mejor que el recálculo total.

La segunda parte es qué algoritmo maxflow usar. Hasta donde entiendo, el autor no necesita un algoritmo muy complejo (pero aún eficiente) con una pequeña constante oculta para ejecutarlo en una plataforma móvil. Su primera elección de Ford-Fulkerson (espero que sea Edmonds-Karp ) no se ve muy mal desde este punto de vista. Pero hay algunas otras posibilidades. El que recomendaría probar primero es la variante del algoritmo de Dinic porque es bastante rápido en la práctica y se puede implementar de una manera muy simple. Otras opciones pueden incluir el escalado de capacidad de Ford-Fulkerson en O ( | E $O(|V|^2|E|)$ y, después de todo, diferentes versiones de push-relabel con heurística. De todos modos, el rendimiento dependerá de un caso de uso, por lo que el autor debe encontrar el mejor empíricamente.$O(|E|^2 \log C_{max})$

Ok, teniendo en cuenta la nueva información y evitando algunos trucos de inicio falso falso / referencias de arenque rojo (mea culpa), aquí hay algunas referencias nuevas sobre esto.

Solución rápida de una secuencia en línea de problemas de flujo máximo con extensiones para calcular cortes mínimos robustos Doug Altner y Özlem Ergun

esta referencia considera secuencias en línea de MFP y "arranques en caliente", es decir, construyendo sobre cambios incrementales a un MFP anterior. "Demostramos que nuestros algoritmos reducen el tiempo de ejecución en un orden de magnitud cuando se comparan códigos similares que usan un solucionador MFP de caja negra. En particular, mostramos que nuestro algoritmo para cortes mínimos robustos puede resolver instancias en segundos que requerirían más de cuatro horas usando un solucionador de flujo máximo de caja negra ".

avances en problemas que involucran flujos máximos Altner, Douglas S., georgia tech

En esta tesis doctoral de 2008 (pdf descargable), el autor considera el problema de agregar arcos de forma incremental que parece estar "lo suficientemente cerca" del problema de agregar nuevos vértices (con múltiples arcos nuevos).

Gran parte de esta referencia está relacionada con la eliminación de partes de la red (cortes / "interdicción") como se indica en la primera parte del resumen.

ver esp "IV SOLUCIÓN DE SECUENCIAS EN LÍNEA DE FLUJOS MÁXIMOS....... p63".

p 63 "Sin embargo, el objetivo de este capítulo es convencer al lector de que el uso iterativo de un solucionador de flujo máximo de caja negra para resolver una gran secuencia de dispositivos multifunción puede conducir a una enorme cantidad de cálculos innecesarios".

p66 "En las aplicaciones mencionadas anteriormente, las MFP son típicamente topológicamente similares. Es decir, la siguiente MFP en la secuencia difiere de la anterior al agregar o eliminar un pequeño número de arcos o al cambiar previsiblemente las capacidades de un conjunto de arcos localizados. Además , cuando se resuelven estas instancias, el tiempo y el espacio necesarios para almacenar cualquier cosa más allá de la solución del problema anterior generalmente no se justifica ".

El autor de p67 también utiliza el enfoque de "inicio en caliente" aquí. "Una estrategia efectiva para resolver rápidamente una secuencia completa en línea de problemas de optimización es desarrollar heurísticas de reoptimización eficientes. Para este fin, desarrollamos un algoritmo de flujo máximo modificado que está diseñado para arranques en caliente eficientes".

vea esp p71 que tiene el problema incremental específico del nuevo arco:

Nuevo problema de reoptimización de flujo máximo de arco (NAMFRP)

el autor considera los problemas más generales p67

Problema de reoptimización de flujo máximo (MFROP)
Problema de reoptimización de arco único de flujo máximo (MFSAROP)

de alguna búsqueda rápida parece que la versión en línea es un área de investigación activa. no menciona el área de aplicación que podría ayudar a reducir la búsqueda de literatura. Una opción es buscar un área de aplicación donde haya más o la última innovación. por lo tanto, hay alguna aplicación de flujo máximo incremental en sistemas de visión y algunos algoritmos para ello allí; pruebe los flujos máximos por amplitud de búsqueda primero en los laboratorios de investigación de microsoft. Parafraseando la introducción de este artículo, aparentemente para los casos de visión, el algoritmo de Boykov y Kolmogorov funciona bien y no hay contraejemplos de tiempo exponencial conocidos, aunque fuera de las aplicaciones de visión podría funcionar mal. Por lo tanto, podría valer la pena probar el algoritmo B&K en sus datos y ver cómo funciona y

Parece que está diciendo que un algoritmo incremental que es lineal en el número de bordes del gráfico no es suficiente velocidad? ¿Pero no es esa eficiencia bastante alta? ¿Con cuántas aristas estás tratando? quizás el enfoque podría ser disminuir el costo de atravesar el gráfico si eso es costoso o un factor significativo (por ejemplo, gráfico almacenado en db frente a gráfico almacenado en la memoria)

Aquí hay un artículo interesante que argumenta que mientras el algoritmo no incremental para flujo máximo está en P, la versión incremental es NP completa. "Hasta donde sabemos, nuestros resultados son los primeros en encontrar un problema de tiempo P cuya versión incremental es NP completa".

Flujo incremental de Hartline, Sharp

Otra posibilidad / dirección es el algoritmo de flujo máximo push-relabel que es "uno de los algoritmos más eficientes para el flujo máximo" y puede tener mejores perfiles de complejidad dependiendo de sus datos. por ejemplo, como dice la página de wikipedia

$O(V^3)$$O(V^2 \sqrt E$$O(V \cdot E \cdot log(V^2 / E))$