Deuxième plus petit

Sait-on quelque chose sur la deuxième plus petite coupe - dans un réseau de flux? Ou, plus généralement, à propos de ce problème: $s$ $t$

Entrée: Un réseau et un nombre , tous en binaire. Sortie: A e plus petit - coupé. $N$ $k$
$k$ $s$ $t$

Une ème plus petite coupe - est toute coupe - , de sorte qu'il existe exactement - coupes dont les capacités $k$ $s$ $t$ $(S,T)$ $s$ $t$ $k-1$ $s$ $t$

sont différents par paire et
vraiment plus petit que la capacité de . $(S,T)$

Je voudrais savoir comment cela peut être calculé et si cela peut être fait efficacement comme pour le cas . $k=1$

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

Vous pouvez trouver la deuxième plus petite coupe en ajoutant

poids à tous les bords de la plus petite coupe, puis en calculant la nouvelle plus petite coupe. Cela fonctionne probablement tant que

est encodé en unaire (et certainement pour

constant).

ϵ

$\epsilon$

k

$k$

k

$k$

Yuval Filmus

Je ne vois pas comment ça aide. Imaginez un réseau de chemins composé des trois nœuds

uniquement avec les deux bords

. De plus, que les capacités soient

. De toute évidence, les coupes min-coupe

et les deuxièmes plus petites coupes

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)$

. L'augmentation des capacités, comme vous l'avez décrit, donnerait à nouveau

coupe minimale avec une capacité

. Comment puis-je en déduire la deuxième plus petite coupe?

(v, t)

$(v,t)$

(s, v)

$(s,v)$

1 + ϵ

$1+\epsilon$

Oliver Witt du

L'ajout d'une borne inférieure sur le plafond de coupe est une inégalité linéaire, il suffit d'ajouter un epsilon plus grand que le plafond de min et d'exécuter LP. Vous pouvez le répéter k fois pour obtenir ce que vous voulez. Cela peut probablement être refondu en tant que modification sur le réseau, mais je ne l'ai pas résolu.

Kaveh

Je vois comment cela fonctionne si

est en encodage unaire. Et si c'est binaire? Dans ce cas, la modification du réseau ne peut pas être effectuée en

itérations.

k

$k$

k

$k$

Oliver Witt

Je doute qu'il existe une solution simple si k est binaire. Nous pouvons vérifier s'il y a une coupe de capuchon c comme je l'ai décrit. Il me semble que c'est essentiellement compter le nombre de c possible, pourrait être fourni pour se rapporter au comptage du nombre de correspondances et probablement # P-complet. (Ce n'est que mon intuition, pas un argument.)

Kaveh

La deuxième plus petite coupure, et plus généralement les plus petites coupures, se trouvent dans le polynôme temporel en et la taille du réseau. Voir: $k$ $k$

HW Hamacher. Un algorithme pour trouver les meilleures coupes dans un réseau. 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 et M. Queyranne. Sur la recherche des meilleures coupes dans un réseau. Oper. Res. Lett. 2 (6): 303-305, 1984, doi: 10.1016 / 0167-6377 (84) 90083-X . $K$

HW Hamacher et M. Queyranne. meilleures solutions aux problèmes d'optimisation combinatoire. Ann. Oper. Res. 4 (1–4): 123–143, 1985,doi: 10.1007 / BF02022039. $K$

David Eppstein
la source

Ne permettent-ils pas des poids égaux parmi les

premiers ? La question semble se poser sur le

ème poids le plus petit qui, comme le suggère Kaveh, sent plus comme un problème # P-complet.

k

$k$

k

$k$

András Salamon

Je le comprends également: des poids égaux sont autorisés. Cela ne semble pas répondre à la question. Néanmoins, je n'étais pas au courant de ces papiers, merci pour cela.

Oliver Witt

La question est mal formulée, car elle demande une chose (la

ème plus petite coupe), puis ajoute plus tard une restriction qui transforme la question en autre chose (la

ème plus petit poids de coupe distinct). Je suis d'accord que la version à poids distinct du problème est susceptible d'être complète.

k

$k$

k

$k$

David Eppstein

Deuxième plus petit

Réponses: