Wie teuer kann es sein, alle langen Pfade in einer DAG zu zerstören?

14

Wir betrachten DAGs (Directed Acyclic Graphs) mit einem Quellknoten ss und einem Zielknoten tt ; Es sind parallele Kanten zulässig, die dasselbe Scheitelpunktpaar verbinden. A kk - Schnitt ist ein Satz von Kanten , deren Entfernung zerstört alle ss - tt Wege länger als kk ; kürzere ss - tt pfade sowie lange "innere" pfade (die nicht zwischen ss und t liegent ) können überleben!

Frage: Reicht es aus, höchstens etwa 1 / k1/k Kanten einer DAG zu entfernen , um alle ss - t - tPfade zu zerstören, die länger als k sindk ?

Das heißt, wenn e ( G )e(G) die Gesamtzahl der Kanten in G bezeichnetG , hat dann jeder DAG GG einen k-k Schnitt mit höchstens etwa e ( G ) / ke(G)/k Kanten? Zwei Beispiele:

  1. Wenn alle ss - t-t Pfade eine Länge > k haben>k , liegt ein k-k Schnitt mit e ( G ) / ke(G)/k Kanten vor. Dies gilt, weil es dann kk disjunkte k-k Schnitte geben muss : Schichte die Knoten von G einfach Gentsprechend ihrem Abstand vom Quellknoten ss .
  2. Wenn G = T nG=Tn ein transitives Turnier ist (eine vollständige DAG), dann auch ein k-k Schnitt mit k ( n / k2 )e(G)/kk(n/k2)e(G)/kKanten existieren: Fixiere eine topologische Reihenfolgeder Knoten, teile die Knoten in kkaufeinanderfolgende Intervalle der Längen/k aufn/kund entferne alle Kanten, die die Knoten des gleichen Intervalls verbinden; Dadurch werden alless-t-tPfade zerstört, die länger alsk sindk.

Bemerkung 1: Ein naiver Versuch, eine positive Antwort zu geben (was ich auch als erstes versucht habe ) wäre zu zeigen, dass jede DAG über kk disjunkte k-k Schnitte verfügen muss . Leider zeigt Beispiel 2, dass dieser Versuch scheitern kann: David Eppstein hat mit einem netten Argument gezeigt, dass für kk etwa √ giltnn , der GraphTnTnkann nicht mehr als vierdisjunkte k-kSchnitte haben!

Anmerkung 2: Es ist wichtig , dass ein k -Schnitt nur benötigt , um alles lange zu zerstören s - t Pfade und nicht notwendigerweise alle langen Wege. Es gibt nämlich 1 DAGs, in denen jeder "reine" k- Schnitt (unter Vermeidung von Kanten, die auf s oder t fallen ) fast alle Kanten enthalten muss. Meine Frage ist also tatsächlich: Kann die Möglichkeit, auch mit s oder t einfallende Kanten zu entfernen , die Größe eines k- Schnitts wesentlich verringern ? Höchstwahrscheinlich ist die Antwort negativ, aber ich konnte noch kein Gegenbeispiel finden. kstkststk

Motivation: Meine Frage ist durch den Nachweis der unteren Schranken für monotone Schalt- und Gleichrichternetze motiviert. Ein solches Netzwerk ist nur eine DAG, deren Kanten zum Teil durch Tests mit "is x i = 1 ?" (es gibt keine Tests x i = 0 ). Die Größe eines Netzwerks ist die Anzahl der beschrifteten Kanten. Ein Eingabevektor wird akzeptiert, wenn es einen s - t - Pfad gibt, dessen Tests mit diesem Vektor übereinstimmen. Markov hat bewiesen, dass, wenn eine monotone Boolesche Funktion f keine kürzeren Intervalle als l und keine kürzeren Intervalle als w hat , die Größe l istxi=1xi=0stflww ist notwendig. Eine positive Antwort auf meine Frage würde bedeuten, dass Netzwerke mit einer Größe von ungefähr k w k notwendig sind, wenn mindestens w k Variablen auf 0 gesetzt werden müssen, um alle Mintermen zu zerstören, die länger als k sind .lwkwkwk0k


1 Die Konstruktion ist in diesem Artikel angegeben. Nehmen Sie einen vollständigen binären Baum T der Tiefe log n . Alle Kanten entfernen. Zeichnen Sie für jeden inneren Knoten v eine Kante zu v von jedem Blatt des linken Teilbaums von T v und eine Kante von v zu jedem Blatt des rechten Teilbaums von T v . Somit sind alle zwei Blätter von T durch einen Pfad der Länge 2 in der DAG verbunden. Die DAG selbst hat ~ n Knoten und ~ n log n Kanten, aber Ω ( nTlognvvTvvTvT2nnlognlog n ) Kanten müssen entfernt werden, um alle Pfade zu zerstören, die länger als √ sindΩ(nlogn)n .n

Stasys
quelle
Längenbegrenzte Bewegungen und Schnitte hängen eng mit den von Ihnen gestellten Fragen zusammen. Ich empfehle die Arbeit von Baier anzuschauen. ftp.math.tu-berlin.de/pub/Preprints/combi/…
Chandra Chekuri
@Chandra Chekuri: danke für den interessanten Link. In dieser Arbeit geht es mehr um das gewichtete Menger-Theorem für kurze Wege / Fehler. Bezüglich Menger für lange Wege, fand ich dieses Papier: die maximale Anzahl von langen disjunkten Pfaden st die Mindestgröße eines k-cut höchstens k - mal ist. Aber das scheint auch nicht zu helfen.
Stasys
Entschuldigung, ich habe die Frage falsch verstanden. Danke für den anderen Hinweis.
Chandra Chekuri

Antworten:

8

[Selbstantwort; Dies ist eine verkürzte Version, kann die alte gefunden werden hier ]

Wir haben mit Georg Schnitger festgestellt, dass die Antwort auf meine Frage sehr negativ ist : Es gibt DAGs (auch mit konstantem Grad), bei denen jeder k- Schnitt einen konstanten Bruchteil aller Kanten haben muss, nicht nur einen Bruchteil von etwa 1 / k , wie in meine Frage. (Ein etwas schwächeres Ergebnis, bei dem möglicherweise ein Bruchteil von 1 / log k erforderlich ist, kann durch Verwendung einer viel einfacheren Konstruktion erhalten werden, die in der obigen Fußnote erwähnt ist. Eine schnelle Beschreibung finden Sie hier. ) k1/k1/logk

In der Arbeit "Über Tiefenreduktion und Gitter" konstruierte Georg eine Folge gerichteter azyklischer Graphen H n mit konstantem Maximalgrad d auf n = m 2 m Knoten mit der folgenden Eigenschaft:Hndn=m2m

  • Für jede Konstante 0 ϵ < 1 gibt es eine Konstante c > 0, so dass, wenn eine Teilmenge von höchstens c n Knoten von H n entfernt wird , der verbleibende Graph einen Pfad mit einer Länge von mindestens 2 ϵ m enthält . 0ϵ<1c>0cnHn2ϵm

Nehmen Sie nun zwei neue Knoten s und t und zeichnen Sie eine Kante von s zu jedem Knoten von H n und eine Kante von jedem Knoten von H n zu t . Der resultierende Graph G n hat noch höchstens 2 n + d n = O ( n ) Kanten.stsHnHntGn2n+dn=O(n)

For every constant 0ϵ<10ϵ<1, there is a constant c>0 such that, if any subset of at most cn edges is removed from Gn, the remaining graph contains an s-t path with 2ϵm or more edges.

Proof: Call the nodes of Hn inner nodes of Gn. Remove any subset of at most cn edges from Gn, where c=c/2. After that, remove an inner node if it was incident to a removed edge. Note that at most 2cn=cn inner nodes are then removed. None of the edges incident to survived nodes was removed. In particular, each survived inner node is still connected to both nodes s and t. By the above property of Hn, there must remain a path of length 2ϵm consisting entirely of survived inner nodes. Since the endpoints of each of these paths survived, each of them can be extended to an s-t path in Gn. Q.E.D.

A consequence is sad: there does not exist any analogue of Markov's lemma for functions with many short minterms, even though the set of long minterms has some "complicated" structure: no super-linear lower bounds on the network size can be then proved using this "length times width" argument.

P.S. This "length times width" argument (when all s-t paths are long enough) was earlier used by Moore and Shannon (1956). The only difference is that they do not allowed rectifies (unlabeled edges). So, this is, in fact, a "Moore-Shannon-Markov argument".

Stasys
quelle