Fluxo máximo usando Ford-Fulkerson e DFS

22

Esta pergunta é sobre a complexidade do tempo do algoritmo de fluxo máximo de Ford-Fulkerson ao usar o DFS para encontrar caminhos de aumento.

Há um exemplo conhecido que mostra que o uso do DFS pode precisar de um número linear de iterações no fluxo máximo; veja, por exemplo, a página da Wikipedia vinculada acima.

No entanto, não estou realmente convencido com este exemplo: uma implementação DFS padrão não exibirá o comportamento de alternar entre B e C como primeiro nó do caminho (usando os nomes dos vértices da página da Wikipedia).

Portanto, vamos impor a condição muito natural de que sempre que o DFS visita um nó , ele sempre examina os vizinhos de na mesma ordem. Ainda existem exemplos para os quais o FF com DFS usa um grande número de iterações?uu

Como uma variante, suponha que tenhamos a propriedade adicional de que as diferentes ordens de vizinhos são consistentes com alguma ordem global arbitrária, mas fixa, dos vértices. Isso faz alguma diferença?

Isso me parece uma pergunta bastante básica; Peço desculpas antecipadamente se a resposta é conhecida, mas não sou especialista em fluxos e alguns estudos no Google não revelaram nada.

Edit: A resposta acaba sendo sim, ainda existem exemplos. Veja a Figura 2 deste documento . Nesses exemplos, o FF com DFS recebe um número exponencial (no número de vértices) de iterações. Parece fácil provar que isso é restrito, ou seja, que o número de iterações é sempre limitado por (independentemente dos valores das capacidades).2O(n)

ds.algorithms reference-request max-flow Per Austrin
fonte
4
Eu me perguntei sobre a mesma pergunta.
Luca Trevisan
1
(1) Boa pergunta. (2) Penso que o exemplo de caso grave (como o da Wikipedia) é geralmente apresentado como uma razão pela qual é necessária alguma consideração sobre a ordem de visita, não como uma razão para não usar a pesquisa aprofundada.
Tsuyoshi Ito 24/02
6
Acho que agora não posso ensinar FF sem uma resposta a esta pergunta. Agradável !!
Suresh Venkat
Não é possível encontrar o fluxo máximo em um número mínimo de iterações NP-Complete?
user834

Respostas:

13

Se as listas de adjacência forem corrigidas com antecedência, o DFS sempre será encerrado (mesmo se houver capacidades irracionais).

Veja Dean, Goemans, Immorlica - finalização finita de algoritmos de "caminho de aumento" na presença de dados irracionais de problemas .

ilyaraz
fonte
11
Obrigado. Isso por si só não responde à minha pergunta, no entanto, o exemplo dado na Figura 2 do artigo de Dean-Goemans-Immorlica mostra uma construção recursiva baseada no exemplo padrão, que responde à minha pergunta e mostra que o FF com DFS pode exigir exponencialmente muitos iterações.
Por Austrin