O corte mínimo poderia ser mais fácil do que o fluxo da rede?

18

Graças ao teorema min-cut de fluxo máximo, sabemos que podemos usar qualquer algoritmo para calcular um fluxo máximo em um gráfico de rede para calcular um -min-cut. Portanto, a complexidade de calcular um corte mínimo ( s , t ) não é mais do que a complexidade de calcular um fluxo máximo ( s , t ) .(s,t)(s,t)(s,t)

Poderia ser menos? Poderia haver um algoritmo para calcular um corte mínimo mais rápido do que qualquer algoritmo de fluxo máximo?(s,t)

Tentei encontrar uma redução para reduzir o problema de ) -max-flow para o problema de ( s , t ) -min-cut, mas não consegui encontrar um. Meu primeiro pensamento foi usar um algoritmo de dividir e conquistar: primeiro encontre um min-cut, que separa o gráfico em duas partes; Agora encontre recursivamente um fluxo máximo para a parte esquerda e um fluxo máximo para a parte direita e combine-os com todas as arestas que cruzam o corte. Isso realmente funcionaria para produzir um fluxo máximo, mas seu pior caso de execução pode ser até O ( | V | ) vezes maior que o tempo de execução do algoritmo min-cut. Existe uma redução melhor?(s,t(s,t)O(|V|)

Percebo que o teorema do corte mínimo de fluxo máximo mostra que a complexidade de calcular o valor de um fluxo máximo é a mesma que a complexidade de calcular a capacidade de um corte mínimo, mas não é disso que estou perguntando. Estou perguntando sobre o problema de encontrar um fluxo máximo e um min-cut (explicitamente).

Isso está intimamente relacionado ao cálculo de um fluxo máximo a partir de um corte mínimo , exceto: (1) estou disposto a permitir reduções de Cook (reduções de Turing), não apenas reduções de Karp (reduções de uma a uma) e (2) talvez, dado , possamos encontrar algum gráfico modo que o min-cut de facilite a computação do fluxo máximo de , que é algo que está fora do escopo dessa outra questão.GG GGGG

DW
fonte
2
@AshkanKzme, não estou te seguindo; Você pode elaborar? Como afirmo no quarto parágrafo da pergunta, o teorema de corte mínimo de fluxo máximo mostra que o valor do fluxo máximo é igual à capacidade do min-cut. Eu suspeito que é isso que você está pensando. No entanto, conhecer o valor do fluxo máximo não informa o fluxo máximo em si (por exemplo, quanto enviar em cada borda específica). Esta pergunta está perguntando sobre a complexidade de calcular o fluxo máximo em si, em comparação com o cálculo do min-cut em si. Minha pergunta é exatamente como declarado no segundo parágrafo da pergunta.
DW
2
@AshkanKzme, Não, não fiz suposições erradas. Você está assumindo implicitamente que Ford-Fulkerson é o algoritmo mais rápido possível para encontrar um min-cut ... mas, tanto quanto eu sei, ninguém jamais provou isso, e não sabemos se isso está correto ou não. Parece-me que você está cometendo o erro padrão de novato com provas de limite inferior: "Não consigo encontrar nenhuma maneira de resolver esse problema mais rapidamente, portanto deve ser impossível". (. PS Você está me dizendo coisas livro padrão sobre max-flow min-cut Eu aprecio sua tentativa de ajuda, mas eu já estou familiarizado com isso ...)
DW
1
No que diz respeito à sua afirmação "Eu acho que pode ser provado que, se você tiver apenas o min-cut, poderá obter o fluxo máximo", bem, encorajo você a escrever uma resposta com a prova disso - porque é basicamente isso minha pergunta está perguntando. Eu nunca vi uma prova disso, mas se você tiver, espero que você a escreva!
DW
1
@ DW Acho que estou melhorando a pergunta agora. Eu acho que fiquei impressionado com o fato de você dar uma redução de turbulência polinomial. Você não precisaria de uma redução constante de turing para provar f(n)=Θ(g(n)) , mesmo que provar que não há essa redução possível não a refute?
9788 Thomas Thomson
1
@ThomasBosman, sim, está correto. [Desculpe por te confundir. A redução que dei na pergunta prova que , que é um limite inferior muito fraco. Espero que possa haver uma redução que prove que f ( n ) = Ω ( g ( n ) ) , mas não sei como construir uma coisa dessas.]f(n)=Ω(g(n)/n)f(n)=Ω(g(n))
DW

Respostas:

-1

Aqui está uma abordagem possível:

Suponha que você conheça o corte S e, em seguida, encontrar o fluxo de para t é um problema de fluxo de rede de custo mínimo com custo zero, pois você sabe exatamente o fluxo de saída em cada vértice em V S e a entrada em t . Suponha que f denota um fluxo S - t e A a matriz arco-nó (ou seja, a linha i , col j tem 1 se i é a cauda de j , -1 se é a cabeça, zero caso contrário), e seja b que A f = b se fStVStfStAijijbAf=bfsatisfaz a oferta / demanda e a conservação do fluxo. Então, com a eliminação gaussiana, podemos encontrar uma solução viável em operações.|V|3

Para encontrar um corte de um fluxo, precisamos construir o gráfico residual que leva no máximo tempo e, potencialmente, atravessar|E|vértices. |V|

Portanto, para gráficos completos e o corte mínimo sendo apenas a fonte ou apenas o coletor, a redução leva tempo igual nas duas direções, no pior caso. No entanto, eu acho que encontrar uma solução viável para pode ser feito mais rapidamente do que | V | 3 dada a estrutura especial. Não tenho certeza de como provar isso.Af=b|V|3

Thomas Bosman
fonte
Não entendo como encontrar usando a eliminação gaussiana. Nós temos | V | equações lineares em | E | desconhecidos. Geralmente | E | > | V | , portanto, não teremos equações suficientes para determinar exclusivamente as incógnitas. Existe um truque que estou ignorando? f|V||E||E|>|V|
DW
Também não sou especialista nisso, por isso posso estar errado. Mas o fato de não haver uma solução única parece facilitar. Se você reduzi-lo à forma reduzida de escalão, você possui colunas independentes. Então a solução exclusiva dessa submatriz eb , combinada com fluxo zero para todas as outras colunas, produziria uma solução não exclusiva, que não é um problema em si. O problema que se pode prever é que f viola as restrições de capacidade, mas intuitivamente eu diria que há uma maneira de contornar isso diretamente|V|bf
Thomas Bosman
Sim, as restrições de capacidade parecem ser o principal desafio. Caso contrário, resolver o sistema de equações lineares pode fornecer uma solução que satisfaça mas não é um fluxo válido, pois viola as restrições de capacidade. UMAf=b
DW
Merda, isso mesmo. Você pode adicionar as restrições (superior e inferior), que você sabe que têm uma solução, mas então | V | +2 | E | linhas, de modo que seria mais lento do que apenas calcular o fluxo máximo diretamente.
Thomas Bosman
O outro problema é que as restrições de capacidade são desigualdades (e não igualdades), então você não pode usar a eliminação gaussiana: seria necessário usar programação linear, que, como você diz, não parece ser mais rápida do que apenas calcular o fluxo máximo diretamente.
DW