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

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

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

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

1. Wenn alle $s$ - $t$ Pfade eine Länge $> k$ , liegt ein $k$ Schnitt mit $\leq e(G)/k$ Kanten vor. Dies gilt, weil es dann $k$ disjunkte $k$ Schnitte geben muss : Schichte die Knoten von G einfach $G$entsprechend ihrem Abstand vom Quellknoten $s$ .
2. Wenn $G=T_n$ ein transitives Turnier ist (eine vollständige DAG), dann auch ein $k$ Schnitt mit $\leq k\binom{n/k}{2} \approx e(G)/k$Kanten existieren: Fixiere eine topologische Reihenfolgeder Knoten, teile die Knoten in $k$aufeinanderfolgende Intervalle der Länge$n/k$und entferne alle Kanten, die die Knoten des gleichen Intervalls verbinden; Dadurch werden alle$s$-t-$t$Pfade zerstört, die länger als$k$.

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 $k$ disjunkte $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 $k$ etwa $\sqrt{n}$ , der Graph$T_n$kann nicht mehr als vierdisjunkte $k$Schnitte 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 ¹ 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. $k$$s$$t$$k$$s$$t$$s$$t$$k$

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 $x_i=1$$x_i=0$$s$$t$$f$$l$$w$⋅ w 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 .$l\cdot w$$k\cdot w_k$$w_k$$0$$k$

¹ 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 Ω ( $T$$\log n$$v$$v$$T_v$$v$$T_v$$T$$2$$\sim n$$\sim n\log n$log n ) Kanten müssen entfernt werden, um alle Pfade zu zerstören, die länger als$\Omega(n\log n)$n .$\sqrt{n}$

[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. ) $k$$1/k$$1/\log k$

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:$H_n$$d$$n=m2^m$

• 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\leq \epsilon < 1$$c > 0$$cn$$H_n$$2^{\epsilon 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.$s$$t$$s$$H_n$$H_n$$t$$G_n$$2n+dn=O(n)$

For every constant $0\leq \epsilon < 1$, there is a constant $c ' > 0$ such that, if any subset of at most $c'n$ edges is removed from $G_n$, the remaining graph contains an $s$-$t$ path with $2^{\epsilon m}$ or more edges.

Proof: Call the nodes of $H_n$ inner nodes of $G_n$. Remove any subset of at most $c'n$ edges from $G_n$, where $c'=c/2$. After that, remove an inner node if it was incident to a removed edge. Note that at most $2c'n=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 $H_n$, there must remain a path of length $2^{\epsilon 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 $G_n$. 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".