<p>[Self answer; this is a shortened version, the old one can be found
<a href="https://web.archive.org/web/20150906174611/http://www.thi.informatik.uni-frankfurt.de/~jukna/drafts/old-answer.html" rel="nofollow noreferrer">here</a>]</p>
<p>
We realized with Georg Schnitger that the answer to my question is <b>strongly negative</b>: there are DAGs
(even of constant degree), where every <span class="math-container">$k$</span>-cut must have a <i>constant</i> fraction of all edges, not just an about <span class="math-container">$1/k$</span> fraction, as in my question. (A slightly weaker result that a <span class="math-container">$1/\log k$</span> fraction may be necessary can be obtained by using a much simpler construction mentioned in the footnote above.
A quick write-up is <a href="https://web.archive.org/web/20150906173230/http://www.thi.informatik.uni-frankfurt.de/~jukna/drafts/mincut.pdf" rel="nofollow noreferrer">here</a>)
<p>
Namely, in the paper <a href="https://ieeexplore.ieee.org/document/4568095" rel="nofollow noreferrer">
"On depth-reduction and grates"</a>, Georg constructed a sequence of directed acyclic
graphs <span class="math-container">$H_n$</span> of constant maximum degree <span class="math-container">$d$</span> on <span class="math-container">$n=m2^m$</span> nodes with the following property:
<ul>
<li> For every constant <span class="math-container">$0\leq \epsilon &lt; 1$</span> there is a constant <span class="math-container">$c &gt; 0$</span> such that, if any subset of at most <span class="math-container">$cn$</span> nodes is removed from <span class="math-container">$H_n$</span>, the remaining graph
contains a  path of length at least <span class="math-container">$2^{\epsilon m}$</span>.
</ul>
Take now two new nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, and draw an edge from <span class="math-container">$s$</span> to every node of <span class="math-container">$H_n$</span>, and an edge
from every node of <span class="math-container">$H_n$</span> to <span class="math-container">$t$</span>. The resulting graph <span class="math-container">$G_n$</span> still has at most  <span class="math-container">$2n+dn=O(n)$</span> edges.
<blockquote>
For every constant <span class="math-container">$0\leq \epsilon &lt; 1$</span>, there is a constant <span class="math-container">$c ' &gt; 0$</span> such that, if any subset of at most <span class="math-container">$c'n$</span> edges is removed from <span class="math-container">$G_n$</span>, the remaining graph
contains an <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path with  <span class="math-container">$2^{\epsilon m}$</span> or more edges.
</blockquote>
<p><b>Proof:</b>
Call the nodes of <span class="math-container">$H_n$</span>  <i>inner</i> nodes of <span class="math-container">$G_n$</span>.
Remove any subset of at most <span class="math-container">$c'n$</span> edges from <span class="math-container">$G_n$</span>, where <span class="math-container">$c'=c/2$</span>.
After that, remove an inner node if it was incident to a removed edge. Note that
at most <span class="math-container">$2c'n=cn$</span> 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 <i>both</i> nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span>. By the above property of <span class="math-container">$H_n$</span>, there must remain
a path of length <span class="math-container">$2^{\epsilon m}$</span> consisting entirely of survived inner nodes.
Since the endpoints of each of these paths survived, each of them
can be extended to an <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path in <span class="math-container">$G_n$</span>. Q.E.D.</p>
<p>
 A consequence is sad:  there does <b>not</b> exist any analogue of Markov's lemma for functions with many <i>short</i> minterms, even though the set of <i>long</i> 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>
P.S. This "length times width" argument (when all <span class="math-container">$s$</span>-<span class="math-container">$t$</span> paths are long enough) was earlier used by <a href="https://www.sciencedirect.com/science/article/abs/pii/0016003256905592" rel="nofollow noreferrer">Moore and Shannon (1956).</a> The only difference is that they did not allow rectifies (unlabeled edges). So, this is, in fact, a "Moore-Shannon-Markov argument".

CC BY-SA 4.0
2015-07-02T16:24:20.003Z
2022-07-10T08:58:14.623Z
2022-07-10T08:58:14.623Z
Stasys
<p>We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-<b>cut</b> is a set of edges whose removal destroys all $s$-$t$ paths longer than $k$; shorter $s$-$t$ paths as well as long "inner" paths (those not between $s$ and $t$) may survive!</p>

<blockquote>
<b>Question:</b>
Is it enough to remove at most about a $1/k$ portion of edges from a DAG
 in order to destroy all $s$-$t$ paths longer than $k$?
</blockquote>

<p>That is, if $e(G)$ denotes the total number of edges in $G$, does then every DAG $G$ have
a $k$-cut with at most about $e(G)/k$ edges?  Two examples:</p>

<ol>
<li> If <i>all</i> $s$-$t$ paths have length $&gt; k$, then a $k$-cut with $\leq e(G)/k$ edges exists.
 This holds because then 
there must be $k$ disjoint $k$-cuts: just layer the nodes of $G$ according to their
distance from the source node $s$.

<li> If $G=T_n$ is a <a href="https://en.wikipedia.org/wiki/Tournament_%28graph_theory%29" rel="nofollow noreferrer">transitive tournament</a> (a complete DAG), then also a $k$-cut with 
$\leq k\binom{n/k}{2} \approx e(G)/k$ edges exists: fix a
<a href="https://en.wikipedia.org/wiki/Topological_sorting" rel="nofollow noreferrer">topological ordering</a> of nodes, split the nodes into
$k$ consecutive intervals of length $n/k$, and remove all edges joining the nodes of the same interval; this will destroy all $s$-$t$ paths longer than $k$.
</ol>

<p><p>
<b>Remark 1:</b> A naive attempt to give a positive answer (which I also <a href="https://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have">tried</a> as first) would be to try to show that every DAG
must have about $k$ <i>disjoint</i> $k$-cuts. Unfortunately, Example 2 shows that this attempt can badly fail: via a nice argument, David Eppstein has <a href="https://cstheory.stackexchange.com/a/16123/5788">shown</a> that, for $k$ about $\sqrt{n}$, the graph $T_n$ cannot have more than four <i>disjoint</i> $k$-cuts!
<p>
<b>Remark 2:</b> It is important that a $k$-cut needs only to destroy all long $s$-$t$ paths, and not necessarily all long paths. Namely, there exist<sup>1</sup> DAGs in which every
"pure" $k$-cut (avoiding edges incident to $s$ or $t$) must contain almost all edges.
 So, my question actually is: can the possibility to remove also edges incident with $s$ or $t$ substantially reduce the size of a $k$-cut? Most probably, the answer is negative, but I could not find
a counterexample as yet.
<p>
<b>Motivation:</b> My question is motivated by proving lower bounds for monotone switching-and-rectifier networks. Such a network is just a DAG, some of whose edges are labeled by tests "is $x_i=1$?" (there are no tests $x_i=0$).  The <i>size</i> of a network is the number of labeled edges. An input
vector is accepted, if there is an $s$-$t$ path all whose tests are consistent with this vector. Markov has <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/Markov-threshold.pdf" rel="nofollow noreferrer">proved</a> that, if
a monotone boolean function $f$ has no minterms shorter than $l$ and no maxterms shorter than $w$, then size  $l\cdot w$ is necessary.  A positive answer to my question would imply that
networks of size about $k\cdot w_k$ are necessary, if at least $w_k$ variables must be set to $0$ in order to destroy all minterms longer than $k$.</p>

<p><hr>
<p><sup>1</sup>The construction is given in <a href="http://www.sciencedirect.com/science/article/pii/030439758290113X" rel="nofollow noreferrer">this paper.</a>
Take a complete binary tree $T$ of depth $\log n$. Remove all edges. For every inner node $v$, draw an edge to $v$ from every leaf of the left subtree of $T_v$, and an edge from $v$ to every leaf of the right subtree of $T_v$. Thus, every two leaves of $T$ are connected by a path of length $2$ in the DAG. The DAG itself has $\sim n$ nodes and $\sim n\log n$ edges, but $\Omega(n\log n)$ edges must be removed in order to destroy all paths longer than $\sqrt{n}$. </p>

CC BY-SA 3.0
2015-06-25T21:48:39.733Z
Length bounded flows and cuts are closely related to the questions you ask. I recommend looking at the thesis of Baier. ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/dissertation-baier.pdf
Chandra Chekuri
CC BY-SA 3.0
2015-06-26T10:42:16.553Z
@Chandra Chekuri: thanks for the interesting link. The thesis is more about the weighted Menger's theorem for *short* paths/flaws.  Concerning Menger for *long* paths, I found [this](http://www.sciencedirect.com/science/article/pii/0095895684900261) paper: the min size of a k-cut is at most about k times the max number of long disjoint s-t paths. But this also doesn't seem to help.
Stasys
CC BY-SA 3.0
2015-06-26T16:13:42.513Z
Sorry, I misunderstood the question. Thanks for the other reference.
Chandra Chekuri
<cc.complexity-theory><graph-theory><circuit-complexity><directed-acyclic-graph>
How expensive may it be to destroy all long s-t paths in a DAG?
Stasys
# How expensive may it be to destroy all long s-t paths in a DAG?

(Asked by: username_0 on 2015-06-25)

We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-**cut** is a set of edges whose removal destroys all $s$-$t$ paths longer than $k$; shorter $s$-$t$ paths as well as long "inner" paths (those not between $s$ and $t$) may survive!

> **Question:**
> Is it enough to remove at most about a $1/k$ portion of edges from a DAG
> in order to destroy all $s$-$t$ paths longer than $k$?

That is, if $e(G)$ denotes the total number of edges in $G$, does then every DAG $G$ have
a $k$-cut with at most about $e(G)/k$ edges? Two examples:

1. If *all* $s$-$t$ paths have length $> k$, then a $k$-cut with $\leq e(G)/k$ edges exists.
   This holds because then
   there must be $k$ disjoint $k$-cuts: just layer the nodes of $G$ according to their
   distance from the source node $s$.- If $G=T\_n$ is a [transitive tournament](https://en.wikipedia.org/wiki/Tournament_%28graph_theory%29) (a complete DAG), then also a $k$-cut with
     $\leq k\binom{n/k}{2} \approx e(G)/k$ edges exists: fix a
     [topological ordering](https://en.wikipedia.org/wiki/Topological_sorting) of nodes, split the nodes into
     $k$ consecutive intervals of length $n/k$, and remove all edges joining the nodes of the same interval; this will destroy all $s$-$t$ paths longer than $k$.

**Remark 1:** A naive attempt to give a positive answer (which I also [tried](https://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have) as first) would be to try to show that every DAG
must have about $k$ *disjoint* $k$-cuts. Unfortunately, Example 2 shows that this attempt can badly fail: via a nice argument, David Eppstein has [shown](https://cstheory.stackexchange.com/a/16123/5788) that, for $k$ about $\sqrt{n}$, the graph $T\_n$ cannot have more than four *disjoint* $k$-cuts!

**Remark 2:** It is important that a $k$-cut needs only to destroy all long $s$-$t$ paths, and not necessarily all long paths. Namely, there exist1 DAGs in which every
"pure" $k$-cut (avoiding edges incident to $s$ or $t$) must contain almost all edges.
So, my question actually is: can the possibility to remove also edges incident with $s$ or $t$ substantially reduce the size of a $k$-cut? Most probably, the answer is negative, but I could not find
a counterexample as yet.

**Motivation:** My question is motivated by proving lower bounds for monotone switching-and-rectifier networks. Such a network is just a DAG, some of whose edges are labeled by tests "is $x\_i=1$?" (there are no tests $x\_i=0$). The *size* of a network is the number of labeled edges. An input
vector is accepted, if there is an $s$-$t$ path all whose tests are consistent with this vector. Markov has [proved](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/Markov-threshold.pdf) that, if
a monotone boolean function $f$ has no minterms shorter than $l$ and no maxterms shorter than $w$, then size $l\cdot w$ is necessary. A positive answer to my question would imply that
networks of size about $k\cdot w\_k$ are necessary, if at least $w\_k$ variables must be set to $0$ in order to destroy all minterms longer than $k$.

---

1The construction is given in [this paper.](http://www.sciencedirect.com/science/article/pii/030439758290113X)
Take a complete binary tree $T$ of depth $\log n$. Remove all edges. For every inner node $v$, draw an edge to $v$ from every leaf of the left subtree of $T\_v$, and an edge from $v$ to every leaf of the right subtree of $T\_v$. Thus, every two leaves of $T$ are connected by a path of length $2$ in the DAG. The DAG itself has $\sim n$ nodes and $\sim n\log n$ edges, but $\Omega(n\log n)$ edges must be removed in order to destroy all paths longer than $\sqrt{n}$.

**Tags:** cc.complexity-theory, graph-theory, circuit-complexity, directed-acyclic-graph

> **Comments:**
> **username_1**: Length bounded flows and cuts are closely related to the questions you ask. I recommend looking at the thesis of Baier. ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/dissertation-baier.pdf  
> **username_0**: @username_1: thanks for the interesting link. The thesis is more about the weighted Menger's theorem for *short* paths/flaws.  Concerning Menger for *long* paths, I found [this](http://www.sciencedirect.com/science/article/pii/0095895684900261) paper: the min size of a k-cut is at most about k times the max number of long disjoint s-t paths. But this also doesn't seem to help.  
> **username_1**: Sorry, I misunderstood the question. Thanks for the other reference.  

---

## 1 answers

### Answer by username_0 on 2015-07-02. Score: 9 | Accepted answer

[Self answer; this is a shortened version, the old one can be found
[here](https://web.archive.org/web/20150906174611/http://www.thi.informatik.uni-frankfurt.de/~jukna/drafts/old-answer.html)]

We realized with Georg Schnitger that the answer to my question is **strongly negative**: there are DAGs
(even of constant degree), where every $k$-cut must have a *constant* fraction of all edges, not just an about $1/k$ fraction, as in my question. (A slightly weaker result that a $1/\log k$ fraction may be necessary can be obtained by using a much simpler construction mentioned in the footnote above.
A quick write-up is [here](https://web.archive.org/web/20150906173230/http://www.thi.informatik.uni-frankfurt.de/~jukna/drafts/mincut.pdf))

Namely, in the paper ["On depth-reduction and grates"](https://ieeexplore.ieee.org/document/4568095), Georg constructed a sequence of directed acyclic
graphs $H\_n$ of constant maximum degree $d$ on $n=m2^m$ nodes with the following property:

* For every constant $0\leq \epsilon < 1$ there is a constant $c > 0$ such that, if any subset of at most $cn$ nodes is removed from $H\_n$, the remaining graph
  contains a path of length at least $2^{\epsilon m}$.

Take now two new nodes $s$ and $t$, and draw an edge from $s$ to every node of $H\_n$, and an edge
from every node of $H\_n$ to $t$. The resulting graph $G\_n$ still has at most $2n+dn=O(n)$ edges.
> 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).](https://www.sciencedirect.com/science/article/abs/pii/0016003256905592) The only difference is that they did not allow rectifies (unlabeled edges). So, this is, in fact, a "Moore-Shannon-Markov argument".


---

