Zweitkleinste

13

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

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

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

  • 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

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 k unär kodiert ist (und sicherlich für k konstant). ϵkk
Yuval Filmus
2
Ich verstehe nicht, wie das hilft. Stellen Sie sich ein Pfadnetzwerk aus den drei Knoten , v , t nur mit den beiden Kanten ( s , v ) und ( v , t ) vor . Ferner sei die Kapazität c ( s , v ) = 1 und c ( v , t ) = 2 . Es ist klar, dass die minimalen Schnitte ( s , v ) und die zweitkleinsten Schnitte ( v ,svt(s,v)(v,t)c(s,v)=1c(v,t)=2(s,v) . Eine Erhöhung der Kapazitätenwie Sie beschrieben ergäbe wieder ( s , v ) als min-Schnitt mitKapazität 1 + ε . Wie kann ich daraus den zweitkleinsten Schnitt ableiten? (v,t)(s,v)1+ϵ
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 k Iterationen durchgeführt werden. kk
Oliver Witt
1
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

Antworten:

7

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

HW Hamacher. Ein -Algorithmus zum Finden der k besten Schnitte in einem Netzwerk. Oper. Res. Lette. 1 (5): 186–189, 1982, doi: 10.1016 / 0167–6377 (82) 90037-2 .(Kn4)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 k- ten kleinsten Gewicht zu sein , was Kaveh zufolge eher nach einem # P-vollständigen Problem riecht. kk
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
1
kk