Segundo menor

Existe algo conhecido sobre o segundo menor - cut em uma rede de fluxo? Ou, de maneira mais geral, sobre esse problema: $s$ $t$

Entrada: Uma rede e um número , todos em binário. Saída: Um menor corte - . $N$ $k$
$k$ $s$ $t$

Um menor corte - é qualquer corte - , de modo que haja exatamente - $k$ $s$ $t$ $(S,T)$ $s$ $t$ $k-1$ $s$ cortes cujas capacidades $t$

são pares diferentes e
verdadeiramente menor que a capacidade de $(S,T)$ .

Gostaria de saber como isso pode ser calculado e se isso pode ser feito com eficiência, como no caso $k=1$ .

cc.complexity-theory optimization max-flow-min-cut flow-problems Oliver Witt
fonte

Você pode encontrar o segundo menor corte adicionando

peso a todas as bordas no menor corte e depois calcular o novo menor corte. Provavelmente isso funciona desde que

seja codificado em unário (e certamente para

constante).

ϵ

$\epsilon$

k

$k$

k

$k$

Yuval Filmus

Não vejo como isso ajuda. Imagine uma rede de caminhos que consiste nos três nós

apenas com as duas arestas

. Além disso, deixar que as capacidades de ser

. Claramente, os cortes mínimos

e os segundos menores cortes

s

$s$

v

$v$

t

$t$

(s, v)

$(s,v)$

(v, t)

$(v,t)$

c (s, v) = 1

$c(s,v)=1$

c (v, t) = 2

$c(v,t)=2$

(s, v)

$(s,v)$

. Aumentar as capacidades, como você descreveu, produziria novamente

como min-cut com a capacidade

. Como vou inferir o segundo menor corte disso?

(v, t)

$(v,t)$

(s, v)

$(s,v)$

1 + ϵ

$1+\epsilon$

23715 Oliver Witt

Adicionar um limite inferior ao limite de corte é uma desigualdade linear, basta adicionar um épsilon maior que o limite de min e executar o LP. Você pode repeti-lo k vezes para obter o que deseja. Provavelmente isso pode ser reformulado como uma modificação na rede, mas ainda não o resolvi.

Kaveh

Eu vejo como isso funciona se

estiver em codificação unária. O que, se for binário? Nesse caso, a modificação da rede não pode ser feita em

iterações.

k

$k$

k

$k$

22615 Oliver Witt

Duvido que exista uma solução fácil se k for binário. Podemos verificar se há um corte da tampa c, como descrevi. Parece-me que, basicamente, está contando o número possível de c, pode estar relacionado à contagem do número de correspondências e provavelmente # P-completo. (Esta é apenas a minha intuição, não um argumento.)

Kaveh

O segundo corte menor e, geralmente, os cortes menores, podem ser encontrados no polinômio de tempo em tamanho da rede. Vejo: $k$ $k$

HW Hamacher. Um algoritmo para encontrar os melhores cortes em uma rede. Oper. Res. Lett. 1 (5): 186-189, 1982, doi: 10.1016 / 0167-6377 (82) 90037-2 . $(K\cdot n^4)$ $k$

HW Hamacher, J.‑C. Picard e M. Queyranne. Ao encontrar os melhores cortes em uma rede. Oper. Res. Lett. 2 (6): 303-305, 1984, doi: 10.1016 / 0167-6377 (84) 90083-X . $K$

HW Hamacher e M. Queyranne. melhores soluções para problemas de otimização combinatória. Ann. Oper. Res. 4 (1–4): 123-143, 1985, doi: 10.1007 / BF02022039 . $K$

David Eppstein
fonte

Eles não permitem pesos iguais entre os

superiores ? A pergunta parece estar se perguntando sobre o

menor peso , que, como sugere Kaveh, cheira mais a um problema de P-completo.

k

$k$

k

$k$

András Salamon

Também entendo assim: pesos iguais são permitidos. Isso parece não responder à pergunta. No entanto, eu não tinha conhecimento desses papéis, obrigado por isso.

Oliver Witt

A pergunta está mal formulada, porque pede uma coisa (o

menor corte) e depois adiciona uma restrição que transforma a pergunta em outra coisa (o

menor peso de corte distinto). Concordo que a versão de peso distinto do problema provavelmente será $ P-complete.

k

$k$

k

$k$

David Eppstein

Segundo menor

Respostas: