Fluxo máximo incremental em gráficos dinâmicos

Estou procurando um algoritmo rápido para calcular o fluxo máximo em gráficos dinâmicos. ou seja, dado um gráfico e , temos o fluxo máximo em de para . Em seguida, novos / antigo nó adicionado / eliminadas com as suas arestas correspondentes de modo a formar um gráfico . O que é um fluxo máximo no gráfico recém-criado? Existe uma maneira de impedir o recálculo do fluxo máximo?s , t ∈ V F L s t u L $G=(V,E)$$s,t\in V$$F$$G$$s$$t$$u$$G^1$

Qualquer pré-processamento que não consome muito tempo / memória é apreciado.

A ideia mais simples é recalcular o fluxo.

Outra idéia simples é a seguinte: salve todos os caminhos de aumento usados ​​no cálculo de fluxo máximo anterior; para adicionar um vértice , podemos encontrar caminhos simples (no gráfico de capacidade atualizado pela etapa anterior) que começam na fonte, vão para o depois vão para o destino, mas o problema é que esse caminho deve ser simples, não consegui encontrar melhor que para esse caso, para. (Observe também que, se fosse apenas um caminho, isso poderia ser feito em mas não é assim.)v O ( n ⋅ m ) m = | E | O ( n + m $v$$v$$O(n\cdot m)$$m=|E|$$O(n+m)$

Também para remover o nó acima da ideia não funciona.

Também já vi papéis como a abordagem incremental para arestas , mas parece que não são bons o suficiente neste caso, é mais do que para cada aresta e parece não ser uma extensão adequada neste caso (apenas recalculamos um fluxo). Atualmente, também estou usando o algoritmo de fluxo máximo Ford-Fulkerson. Se houver uma opção melhor para algoritmos on-line, é bom conhecê-lo.$O(m)$

A abordagem descrita pode não ser teoricamente ideal. É apenas uma solução prática simples que pode funcionar para o autor. Não posso fornecer referências, porque sempre achei que era um folclore amplamente conhecido, mas, estranhamente, ninguém postou na resposta. Então eu faço.

Suponha que temos uma rede não direcionada . Suponha que ele seja armazenado em uma estrutura de dados que permita inserções / exclusões fáceis de vértices / arco. Às vezes, usaremos a rede residual (ou seja, com capacidades atualizadas ).G f c f = c - $G=(V,E,c)$$G_f$$c_f = c - f$

A primeira parte é como processar inserções / exclusões de vértices. É mais ou menos simples para inserções:

1. Adicione um novo vértice com arestas correspondentes à rede residual.
2. Encontre um fluxo máximo na rede residual atualizada usando o algoritmo maxflow de sua escolha.

Para exclusões, as coisas ficaram mais complicadas. Imagine que dividimos o vértice que estamos prestes a excluir em duas metades e modo que todos os arcos-pontos para , todos os arcos-out vão de e esses novos vértices são conectados por um arco de capacidade infinita. A exclusão de é equivalente à exclusão do arco entre e . O que acontecerá neste caso? Vamos denotar por o fluxo que passa pelo vértice . Então experimentará excesso de unidades de fluxo ev i n v o u t v i n v o u t v v i n v o u t f v v v i n f v v o u t f $v$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$v$$v_{in}$$v_{out}$$f^v$$v$$v_{in}$$f^v$$v_{out}$haverá escassez de unidades de fluxo logo após a exclusão (as restrições de fluxo serão obviamente quebradas). Para fazer com que as restrições de fluxo sejam mantidas novamente, devemos reorganizar os fluxos, mas também queremos manter o valor original do fluxo o mais alto possível. Vamos ver primeiro se podemos fazer um rearranjo sem diminuir o fluxo total. Para verificar se encontra um maxflow de a na rede residual "cortada" (ou seja, sem o arco conectando e ). Deveríamos limitá-lo por obviamente. Se for igual a , teremos sorte: reatribuímos o fluxo que passava por$f^v$ vinvoutvinvoutfvfvvΔ$\tilde{f^v}$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$f^v$$f^v$$v$de tal maneira que o fluxo total não foi alterado. No outro caso, o fluxo total deve ser diminuído pelo excesso "inútil" de unidades . Para fazer isso, conecte temporariamente e por um arco de capacidade infinita e execute o algoritmo maxflow novamente de a (devemos limitar o fluxo por ). Isso fixará a rede residual e fará com que as restrições de fluxo sejam mantidas novamente, diminuindo automaticamente o fluxo total em . s t v i n v o u t Δ $\Delta = f^v - \tilde{f^v}$$s$$t$$v_{in}$$v_{out}$$\Delta$$\Delta$

A complexidade do tempo dessas atualizações pode depender do algoritmo maxflow que usamos. Os piores casos podem ser bem ruins, mas ainda são melhores do que o recálculo total.

A segunda parte é qual o algoritmo maxflow a ser usado. Tanto quanto eu entendo, o autor não precisa de um algoritmo muito complexo (mas ainda eficiente) com pequena constante oculta para executá-lo em uma plataforma móvel. Sua primeira escolha de Ford-Fulkerson (eu espero que seja Edmonds-Karp ) não parece muito ruim desse ponto de vista. Mas existem outras possibilidades. O que eu recomendaria tentar primeiro é a variante do algoritmo de Dinic porque é bastante rápido na prática e pode ser implementado de uma maneira muito simples. Outras opções podem incluir o dimensionamento da capacidade Ford-Fulkerson emO ( | E | 2 log C m a x$O(|V|^2|E|)$$O(|E|^2 \log C_{max})$e, afinal, diferentes versões do push-re-label com heurísticas. De qualquer forma, o desempenho dependerá de um caso de uso, para que o autor encontre o melhor empiricamente.

ok, levando em conta as novas informações e evitando algumas referências complicadas e falsas antes do início / arenque vermelho (mea culpa), aqui estão algumas novas referências sobre isso.

Solução rápida de uma sequência on-line de problemas de fluxo máximo com extensões para calcular cortes mínimos robustos Doug Altner e Özlem Ergun

essa referência considera sequências on-line de MFPs e "partidas a quente", ou seja, com base em alterações incrementais a uma MFP anterior. "Demonstramos que nossos algoritmos reduzem o tempo de execução em uma ordem de grandeza quando comparados códigos semelhantes que usam um solucionador de MFP de caixa preta. Em particular, mostramos que nosso algoritmo para cortes mínimos robustos pode resolver instâncias em segundos que exigiriam mais de quatro horas usando um solucionador de fluxo máximo de caixa preta ".

avanços em problemas envolvendo fluxos máximos Altner, Douglas S., georgia tech

nesta tese de doutorado de 2008 (pdf para download), o autor considera o problema de adicionar gradualmente arcos que parecem estar "suficientemente próximos" ao problema de adicionar novos vértices (com vários novos arcos).

grande parte desta referência se refere à exclusão de partes da rede (cortes / "interdições"), conforme declarado na 1ª parte do resumo

consulte esp "IV SOLUÇÃO DE SEQUÊNCIAS ONLINE DE FLUXOS MÁXIMOS...... pág. 63".

p 63 "O objetivo deste capítulo, no entanto, é convencer o leitor de que o uso iterativo de um solucionador de fluxo máximo de caixa preta para resolver uma grande sequência de MFPs pode levar a um número enorme de cálculos desnecessários".

p66 "Nas aplicações mencionadas, as MFPs são tipicamente topologicamente semelhantes. Ou seja, a próxima MFP da sequência difere da anterior adicionando ou removendo um pequeno número de arcos ou alterando previsivelmente as capacidades de um conjunto de arcos localizado. , ao resolver essas instâncias, o tempo e o espaço necessários para armazenar qualquer coisa além da solução para o problema anterior geralmente são injustificados ".

O autor da p67 também usa a abordagem "início a quente" aqui. "Uma estratégia eficaz para resolver rapidamente uma seqüência on-line inteira de problemas de otimização é desenvolver heurísticas de reoptimização eficientes. Para esse fim, desenvolvemos um algoritmo de fluxo máximo modificado, projetado para partidas a quente eficientes".

veja esp p71 que possui o problema incremental específico de novo arco:

Novo problema de reoptimização do fluxo máximo do arco (NAMFRP)

o autor considera os problemas mais gerais p67

Problema de reoptimização de fluxo máximo (MFROP)
Problema de reoptimização de arco único de fluxo máximo (MFSAROP)

a partir de uma pesquisa rápida, parece que a versão online é uma área de pesquisa ativa. você não menciona a área de aplicação que pode ajudar a restringir a pesquisa de literatura. uma opção é procurar uma área de aplicação onde exista a maior ou mais recente inovação. portanto, existe alguma aplicação de fluxo máximo incremental em sistemas de visão e alguns algoritmos para isso; tente Fluxos máximos por pesquisa incremental em primeiro lugar nos laboratórios de pesquisa da microsoft. parafraseando a introdução deste artigo, aparentemente para instâncias de visão o algoritmo de Boykov e Kolmogorov se sai bem e não há contra-exemplos de tempo exponencial conhecidos, embora fora dos aplicativos de visão possa ter um desempenho ruim. vale a pena experimentar o algoritmo B&K nos seus dados e ver como ele se comporta e

você parece estar dizendo que um algoritmo incremental linear no número de arestas do gráfico não é velocidade suficiente? mas não é essa eficiência bastante alta? com quantas arestas você está lidando? talvez a abordagem seja diminuir o custo de percorrer o gráfico se isso for caro ou um fator significativo (por exemplo, gráfico armazenado em db vs gráfico armazenado na memória)

Aqui está um artigo interessante que argumenta que, enquanto o algoritmo não incremental para fluxo máximo está em P, a versão incremental é NP completa. "Até onde sabemos, nossos resultados são os primeiros a encontrar um problema de tempo P cuja versão incremental é NP completa".

Fluxo incremental da Hartline, Sharp

outra possibilidade / direção é o algoritmo de fluxo máximo push-re-label , que é "um dos algoritmos mais eficientes para o fluxo máximo" e pode ter melhores perfis de complexidade, dependendo dos seus dados. por exemplo, como afirma a página da Wikipedia

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