Wie viele disjunkte Kantenschnitte muss eine DAG haben?

10

Die folgende Frage an die Optimalitäts des Bellman-Ford im Zusammenhang - kürzester Weg dynamischen Programmier - Algorithmus (siehe diesen Beitrag für eine Verbindung). Eine positive Antwort würde auch bedeuten, dass die minimale Größe eines monotonen nichtdeterministischen Verzweigungsprogramms für das STCONN- Problem . t Θ ( n 3 )stΘ(n3)

Sei eine DAG (gerichteter azyklischer Graph) mit einem Quellknoten s und einem Zielknoten t . Ein k - Schnitt ist eine Menge von Kanten, deren Entfernung alle s - t Pfade mit einer Länge k zerstört ; wir nehmen an, dass es solche Pfade in G gibt . Beachten Sie, dass kürzere s - t - Pfade nicht zerstört werden müssen.GstkstkGst

Frage: Muss mindestens (ungefähr) k disjunkte k- Schnitte haben? Gk k

Wenn es keine kürzeren - t - Pfade als k gibt , lautet die Antwort JA, da Robacker die folgende bekannte Min-Max-Tatsache (ein Dual zu Mengers Theorem ) zugeschrieben wird . Ein s - t - Schnitt ist ein k - Schnitt für k = 1 (zerstört alle s - t Pfade).stkstkk=1 st

Fakt: In jedem gerichteten Graphen entspricht die maximale Anzahl von kantendisjunkten - t - Schnitten der minimalen Länge eines s - t Pfads. stst

Beachten Sie, dass dies auch dann gilt, wenn der Graph nicht azyklisch ist.

Beweis: Trivialerweise ist das Minimum mindestens das Maximum, da jeder - t - Pfad jeden s - t Schnitt in einer Kante schneidet. Um Gleichheit zu sehen, sei d ( u ) die Länge eines kürzesten Weges von s nach u . Sei U r = { u : d ( u ) = r } , für r = 1 , , d ( t ) , und sei E rststd(u)suUr={u:d(u)=r}r=1,,d(t)Ersei die Menge der Kanten, die . Es ist klar, dass die Mengen E r disjunkt sind, weil die Mengen U r solche sind. Es bleibt also zu zeigen, dass jedes E r ein s - t- Schnitt ist. Um dies zu zeigen, nehmen eine beliebige s - t Pfad p = ( u 1 , u 2 , ... , u m ) mit u 1 = s und u m = t . Da dUrErUrErststp=(u1,u2,,um)u1=sum=t , die Folge der Abstände d ( u 1 ) , , d ( u m ) muss den Wert d ( u m ) = d ( t ) erreichen, indem bei d begonnen wird ( u 1 ) = d ( s ) = 0 und Erhöhen des Wertes um höchstens 1d(ui+1)d(ui)+1d(u1),,d(um)d(um)=d(t)d(u1)=d(s)=01in jedem Schritt. Wenn ein Wert verringert wird, müssen wir letzteren Wert d ( u i ) erreichen . Es muss also ein j geben, bei dem ein Sprung von d ( u j ) = r nach d ( u j + 1 ) = r + 1 stattfindet, was bedeutet, dass die Kante ( u j , u j + 1 ) zu E r gehört , as erwünscht. QED d(ui)d(ui)jd(uj)=rd(uj+1)=r+1(uj,uj+1)Er

Was aber, wenn es auch kürzere (als ) Wege gibt? Irgendwelche Hinweise / Hinweise? k


JT Robacker, Min-Max-Theoreme über kürzeste Ketten und disjunkte Schnitte eines Netzwerks, Forschungsmemorandum RM-1660, The RAND Corporation, Santa Monica, Kalifornien, [12. Januar] 1956.
EDIT (ein Tag später): über ein kurzes und sehr schönes Argument, antwortete David Eppstein die ursprüngliche Frage oben in Negativ : die komplette DAG (a transitiv Turnier ) kann nicht mehr als vier disjunkt k -Schnitte! Tatsächlich beweist er die folgende interessante strukturelle Tatsache für k ungefähr Tnkk . Ein Schnitt istrein,wenn er keine Kanten enthält, die aufsodert fallen.nst

Jeder reine Schnitt in T n enthält einen Pfad der Länge k . kTnk

Dies impliziert insbesondere, dass sich alle zwei reinen Schnitte schneiden müssen! Aber vielleicht gibt es noch viele reine k- Schnitte, die sich nicht "zu sehr" überlappen. Daher eine entspannte Frage (die Konsequenzen für STCONN wären dieselben ):kk

Frage 2: Wenn jeder reine Schnitt M Kanten hat, muss der Graph dann ungefähr Ω ( k M ) Kanten haben? kMΩ(kM)

Der Zusammenhang mit der Komplexität von STCONN ergibt sich aus dem Ergebnis von Erdős und Gallai, dass man alle außer Kanten von (ungerichteten) K m entfernen muss, um alle Pfade der Länge k zu zerstören . (k1)m/2Kmk


EDIT 2: Ich habe jetzt Frage 2 bei mathoverflow gestellt .

Stasys
quelle

Antworten:

9

Kurze Antwort: nein.

Sei eine vollständige DAG (transitives Turnier) auf n Eckpunkten mit s und t als Quelle und Senke und sei k = Gnst . Beachtendass es höchstens vier disjunkte Schnitte werden kanndie mehr tham enthaltenn/3Kanten Vorfallsoder mehr alsn/3Kanten Vorfallt. Wenn es also viele disjunkte Schnitte geben soll, können wir annehmen, dass es einen SchnittC gibt, der keine große Anzahl von Kanten enthält, die aufsundt fallen.k=n/3n/3sn/3tCst

Nun sei der vollständige Teilgraph, der in G durch die Menge der Eckpunkte x induziert wird, so dass die Kanten s x und x t nicht zu C gehören . Die Anzahl der Eckpunkte in X beträgt mindestens n / 3 , da C sonst zu viele Kanten berühren würde, die auf s oder t fallen . Allerdings X C kann kein enthalten k -Pfad, denn wenn ein solcher Weg existiert es mit verkettet werden könnte s und t bilden einen langen Weg in GXGxsxxtCXn/3CstXCkst . Daher hat dieSchicht mitdem längsten Pfad von X C weniger als k Schichten und eine Schicht, die mehr als ( n / 3 ) / k = k Eckpunkte enthält. Da dies eine Schicht mit der längsten Pfadschicht ist, ist sie in X C unabhängigund daher in C vollständig, sodass C einen Pfad P durch die Eckpunkte dieser Schicht mit der Länge k enthält . Dieser Pfad muss von allen anderen Schnitten getrennt sein.GCXCk(n/3)/k=kXCCCPk

Jeder Schnitt, der nicht muss entweder die Kante von s bis zum Anfang von Pfad P oder die Kante vom Ende von Pfad P bis t enthalten , sonst würde er den Pfad s - P - t nicht blockieren . Wenn also C existiert, kann es höchstens drei disjunkte Schnitte geben. Und wenn C nicht existiert (dh wenn alle Schnitte mehr als n / 3 Kanten abdecken, die auf s oder t fallen ), kann es höchstens vier disjunkte Schnitte geben. In jedem Fall ist dies viel weniger als k Schnitte.CsPPtsPtCCn/3stk

David Eppstein
quelle
@ David: Interessantes Argument (obwohl ich es noch nicht ganz verstanden habe: warum C einen k-Pfad haben muss). Aber wo schlägt das Argument fehl (sollte es), wenn alle st Pfade lang sind, mit einer Länge von mindestens k?
Stasys
1
@Stasys: G ist ein Turnier, der Beweis nutzt diese Tatsache, also imo, deshalb würde es scheitern.
Domotorp
@domotorp: danke, tatsächlich habe ich das wort "komplett" verpasst. Ich kann noch keinen Fehler finden, aber dies wäre eine eher eingängige Tatsache: Selbst wenn es in einem azyklischen Turnier viele k-Pfade gibt, können wir nicht viele disjunkte Systeme ihrer Vertreter (Kanten) auswählen.
Stasys
@ David: Um die genannten Konsequenzen zu haben, können wir zulassen, dass Schnitte nur "fast unzusammenhängend" sind, dh Kanten teilen, die auf s oder t fallen (wir haben nur 2n diese speziellen Kanten). Ein echtes Ziel ist es zu zeigen, dass G ungefähr kN Kanten haben muss, wenn wir wissen, dass jeder "reine" k-Schnitt (ohne diese speziellen Kanten) N Kanten haben muss. Kann Ihr (sehr schönes, wie ich jetzt sehe) Argument auf diese ("fast unzusammenhängende") Situation geändert werden?
Stasys
2
Wenn Sie zulassen, dass Schnitte Kanten teilen, die auf s oder t fallen, warum können Sie dann nicht dafür sorgen, dass alle Schnitte genau aus dem Satz von Kanten bestehen, die auf s fallen? Andererseits zeigt mein Argument, dass es (mit seiner Wahl von und k ) nur einen reinen Schnitt geben kann. Gk
David Eppstein