Zweitkleinste

Ist etwas über den zweitkleinsten - - Schnitt in einem Fließnetz bekannt? Oder allgemeiner zu diesem Problem: $s$ $t$

Eingabe: Ein Netzwerk und eine Zahl , alle binär. Ausgabe: A kleinster - Schnitt. $N$ $k$
$k$ $s$ $t$

Ein - ten kleinsten - Schnitt ist keine - geschnitten, so dass es genau sind , - Schnitte , deren Kapazitäten $k$ $s$ $t$ $(S,T)$ $s$ $t$ $k-1$ $s$ $t$

sind paarweise verschieden und
wirklich kleiner als die Kapazität von . $(S,T)$

Ich würde gerne wissen, wie es berechnet werden kann und ob dies wie für den Fall effizient durchgeführt werden kann . $k=1$

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

Sie können den zweitkleinsten Schnitt finden, indem Sie

Gewicht zu allen Kanten im kleinsten Schnitt hinzufügen und dann den neuen kleinsten Schnitt berechnen. Dies funktioniert wahrscheinlich so lange, wie

unär kodiert ist (und sicherlich für

konstant).

ϵ

$\epsilon$

k

$k$

k

$k$

Yuval Filmus

Ich verstehe nicht, wie das hilft. Stellen Sie sich ein Pfadnetzwerk aus den drei Knoten

nur mit den beiden Kanten

und

. Ferner sei die Kapazität

und

. Es ist klar, dass die minimalen Schnitte

und die zweitkleinsten Schnitte

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

. Eine Erhöhung der Kapazitätenwie Sie beschrieben ergäbe wieder

als min-Schnitt mitKapazität

. Wie kann ich daraus den zweitkleinsten Schnitt ableiten?

(v, t)

$(v,t)$

(s, v)

$(s,v)$

1 + ϵ

$1+\epsilon$

Oliver Witt

Das Hinzufügen einer Untergrenze für die Schnittobergrenze ist eine lineare Ungleichung. Fügen Sie einfach ein Epsilon hinzu, das größer als die Obergrenze von min ist, und führen Sie LP aus. Sie können es k-mal wiederholen, um zu bekommen, was Sie wollen. Dies kann wahrscheinlich als Änderung im Netzwerk neu geschrieben werden, aber ich habe es nicht ausgearbeitet.

Kaveh

Ich sehe, wie es funktioniert, wenn

in unärer Kodierung ist. Was ist, wenn es binär ist? In diesem Fall kann die Netzwerkänderung nicht in

Iterationen durchgeführt werden.

k

$k$

k

$k$

Oliver Witt

Ich bezweifle, dass es eine einfache Lösung gibt, wenn k binär ist. Wir können überprüfen, ob es einen Schnitt von Kappe c gibt, wie ich beschrieben habe. Es scheint mir, dass im Wesentlichen die Anzahl der möglichen c gezählt wird, könnte vorgesehen sein, sich auf das Zählen der Anzahl der Übereinstimmungen und wahrscheinlich # P-vollständig zu beziehen. (Dies ist nur meine Intuition, kein Argument.)

Kaveh

Der zweitkleinste Schnitt und allgemeiner die kleinsten Schnitte können im Zeitpolynom in und der Netzwerkgröße gefunden werden. Sehen: $k$ $k$

HW Hamacher. Ein -Algorithmus zum Finden der besten Schnitte in einem Netzwerk. Oper. Res. Lette. 1 (5): 186–189, 1982, doi: 10.1016 / 0167–6377 (82) 90037-2 . $(K\cdot n^4)$ $k$

HW Hamacher, J.-C. Picard und M. Queyranne. Auf der Suche nach den besten Schnitten in einem Netzwerk. Oper. Res. Lette. 2 (6): 303–305, 1984, doi: 10.1016 / 0167–6377 (84) 90083-X . $K$

HW Hamacher und M. Queyranne. beste Lösungen für kombinatorische Optimierungsprobleme. Ann. Oper. Res. 4 (1-4): 123–143, 1985, doi: 10.1007 / BF02022039 . $K$

David Eppstein
quelle

Erlauben diese nicht gleiche Gewichte unter den Top-

? Die Frage scheint nach dem

ten kleinsten Gewicht zu sein , was Kaveh zufolge eher nach einem # P-vollständigen Problem riecht.

k

$k$

k

$k$

András Salamon

Ich verstehe das auch so: Gleiche Gewichte sind erlaubt. Dies scheint die Frage nicht zu beantworten. Trotzdem kannte ich diese Papiere nicht, danke dafür.

Oliver Witt

k

$k$

k

$k$

Zweitkleinste

Antworten: