Calcular um fluxo máximo de um min-cut

Sabemos que calcular um fluxo máximo resp. um corte mínimo de uma rede com capacidades é equivalente; cf. o teorema de corte mínimo de fluxo máximo .

Temos algoritmos (mais ou menos eficientes) para calcular fluxos máximos, e calcular um corte mínimo dado um fluxo máximo também não é difícil nem caro.

Mas e o inverso? Dado um corte mínimo, como podemos determinar um fluxo máximo? Sem resolver o Max-Flow do zero, é claro, e de preferência mais rápido que isso também.

Alguns pensamentos:

Desde o corte mínimo, sabemos o valor máximo do fluxo. Não vejo como essas informações ajudam o padrão a abordar o caminho de aumento e a re-atribuição de push, embora a adaptação do último pareça um pouco mais plausível.
Não podemos usar o corte mínimo para dividir a rede em duas partes e recuperar, pois isso não reduzirá o problema no pior dos casos (se uma partição for um singleton); também não teríamos um corte mínimo das instâncias menores.
O conhecimento do valor do fluxo máximo acelera a solução do Max-Flow LP, talvez por meio de condições complementares de folga?

algorithms graphs network-flow Rafael
fonte

Pergunta relacionada: conhecemos algoritmos para calcular min-recortes (que não usam algoritmos de fluxo máximo)?

Raphael

Definitivamente, o algoritmo aleatório de Karger é muito popular e você precisa de zero conhecimento de fluxos máximos para isso.

Juho

Se você não deseja algoritmos aleatórios, o algoritmo de Stoer-Wagner é muito simples, também sem técnicas de fluxo.

Juho

Coisa boa! Há outro desafio aqui. Conhecer apenas o min-cut transmite apenas

bits de informação (no máximo), uma vez que cada corte é isomorfa a um subconjunto de

. No entanto, um fluxo máximo pode precisar de muito mais do que

bits de informação para representar (especialmente se as capacidades forem grandes). Portanto, teoricamente, você não pode esperar um algoritmo que analise apenas o corte e cuspa o fluxo; também precisaria olhar para o gráfico e fazer alguns cálculos adicionais. (Sei que isso não é muito de uma barreira.)

| V |

$|V|$

V

$V$

| V |

$|V|$

Respostas:

Na pior das hipóteses, o corte mínimo em si não transmite muita informação sobre o fluxo máximo. Considere um gráfico no qual o mínimo cut tem o valor . Se eu estender adicionando um novo vértice e uma aresta com peso , um mínimo de corte no novo gráfico consiste apenas na aresta $G=(V,E)$ $s,t$ $w$ $G$ $s'$ $(s',s)$ $w$ $s',t$ $(s', s)$ mas isso não fornece nenhuma informação sobre como obter unidades de fluxo de para . $w$ $s$ $t$

Efetivamente, o corte mínimo informa o valor do fluxo, mas não como atingi-lo. Isso significa que conhecer o corte mínimo pode acelerar a localização do fluxo, no máximo, por um fator logarítmico, uma vez que poderíamos fazer uma busca binária para encontrar o valor do corte.

Tom van der Zanden
fonte

Mas esse fator logarítmico estaria no tamanho do intervalo dos valores de fluxo em potencial, portanto incomparável aos limites superiores existentes na solução do fluxo máximo que depende apenas do tamanho do gráfico. Dito isto, mesmo uma aceleração logarítmica seria interessante. Não estou convencido de que conhecer o valor de um fluxo máximo não ajuda em nada.

Raphael

-2

Certamente existem algoritmos que permitem calcular o corte mínimo antes de calcular o maxflow. Dois desses algoritmos são os algoritmos push relabel e pseudoflow, que estão intimamente relacionados. O último é mais eficiente. Ambos os algoritmos usam propriedades especiais do gráfico residual que iterativamente melhoram para derivar o fluxo máximo do corte mínimo. Para detalhes, eu recomendo a leitura do código e dos documentos.

Para elaborar o caso push relabel, quando o algoritmo não pode enviar mais fluxo para o coletor, é garantido que ele tenha calculado um corte mínimo. Essa parte do algoritmo é chamada de fase 1 por falta de um nome melhor. A Fase 2 é o estágio mais eficiente em que transforma o corte mínimo em um fluxo máximo, cancelando iterativamente os ciclos no gráfico residual usando uma primeira pesquisa de profundidade única e empurrando o excesso de volta para a fonte. Acredito que a fase 2 pode ser comprovadamente mais eficiente do que a fase 1.

ldog
fonte

Por favor, releia a pergunta; não é quem você respondeu.

Raphael

O exemplo de RP que forneci pressupõe que você tenha calculado outras informações ao longo do caminho enquanto calculava min-cut. Sua pergunta original não especificou se você poderia manter outras informações junto com o min-cut para facilitar o cálculo do fluxo máximo subsequente. É justo afirmar sua pergunta original como "Dado um corte mínimo e nenhuma outra informação , como podemos determinar um fluxo máximo?".

Ldog 17/04/19

Eu afirmei, "dado A, calcule B". A única suposição razoável é que você recebe apenas A; caso contrário, falar sobre problemas computacionais seria um assunto muito confuso.

Raphael

Eu peço desculpa mas não concordo. De uma perspectiva prática, você nunca computaria um min-cut sem calcular informações adicionais (como as do algoritmo PR). De uma perspectiva teórica, pode ser bom considerar as coisas isoladamente, como você diz. O contexto é fundamental aqui.

Ldog 17/04/19