<p>Short answer: no.</p>

<p>Let $G$ be a complete DAG (transitive tournament) on $n$ vertices with $s$ and $t$ its source and sink, and let $k=\sqrt{n/3}$. Observe that there can be at most four disjoint cuts that contain more tham $n/3$ edges incident to $s$ or more than $n/3$ edges incident to $t$. So, if there are to be many disjoint cuts, we can assume that there exists a cut $C$ that does not contain large numbers of edges incident to $s$ and $t$.</p>

<p>Now let $X$ be the complete subgraph induced in $G$ by the set of vertices $x$ such that edges $sx$ and $xt$ do not belong to $C$. The number of vertices in $X$ is at least $n/3$, because otherwise $C$ would touch too many edges incident to $s$ or $t$. However, $X\setminus C$ cannot contain a $k$-path, because if such a path existed it could be concatenated with $s$ and $t$ to form a long path in $G\setminus C$. Therefore, the longest-path layering of $X\setminus C$ has fewer than $k$ layers, and has a layer containing more than $(n/3)/k=k$ vertices. Since this is a layer of the longest path layering, it is independent in $X\setminus C$, and therefore complete in $C$, so $C$ contains a path $P$ through the vertices of this layer, of length $k$. This path must be disjoint from all of the other cuts.</p>

<p>Every cut that is not $C$ must contain either the edge from $s$ to the start of path $P$ or the edge from the end of path $P$ to $t$, or else it would not block the path $s$–$P$–$t$. So if $C$ exists, there can be at most three disjoint cuts. And if $C$ does not exist (that is, if all cuts cover more than $n/3$ edges incident to $s$ or to $t$) there can be at most four disjoint cuts. Either way, this is a lot fewer than $k$ cuts.</p>

CC BY-SA 3.0
2013-01-17T12:34:21.597Z
@ David: Interesting argument (albeit I have not quite understood it yet: why C must have a k-path). But where the argument fails (it should) if *all* s-t paths are long, of length at least k?
Stasys
CC BY-SA 3.0
2013-01-17T12:53:37.453Z
@Stasys: G is a tournament, the proof uses this fact, so imo that is why it would fail.
domotorp
CC BY-SA 3.0
2013-01-17T14:13:01.947Z
@domotorp: thanks, indeed I missed the word "complete". I cannot find a flaw as yet, but this would be a rather counterintuitive fact: even if there are a lot of k-path in an acyclic tournament, we cannot select many disjoint systems of their representatives (edges).
Stasys
CC BY-SA 3.0
2013-01-17T15:42:16.433Z
@David: Actually, to have the mentioned consequences, we can allow that cuts are only "almost disjoint", i.e may share edges incident to s or t (we have only 2n these special edges). A real goal is to show that G must have about kN edges, if we know that every "pure" k-cut (without these special edges) must have N edges. Can your (very nice, as I now see) argument be modified to this ("almost disjoint") situation?
Stasys
CC BY-SA 3.0
2013-01-17T16:45:07.917Z
If you allow cuts to share edges incident to s or t, then why can't you make all the cuts consist exactly of the set of edges incident to s? On the other hand, my argument shows that (with its choice of $G$ and $k$) there can be only one pure cut.
David Eppstein
CC BY-SA 3.0
2013-01-17T17:45:05.753Z
@David: I cannot see why your argument shows that there can be only one pure k-cut, because now we allow that cuts *can* share the edge s->P and/or P->t. Am I missing something? I don't want to take just edges leaving s - the goal is to show that G must have many edges if there are many pure k-cuts.
Stasys
CC BY-SA 3.0
2013-01-17T21:51:31.997Z
You defined a pure cut to be a cut that has no special edges, right? So it would fit the criteria of the cut $C$ in my argument.
David Eppstein
CC BY-SA 3.0
2013-01-18T11:35:28.540Z
Yes, you are right: any other pure k-cut must intersect C. A nice fact! But what about the relaxed Question 2? That is, knowing that each k-cut must have N edges, can we then conclude that there must be at least about k times N edges in the graph? I haven't marked your nice answer as "accepted" yet only because I won't close it: there remains a small hope that Question 2 still has an affirmative answer.
Stasys
CC BY-SA 3.0
2013-01-19T18:43:06.560Z
@David: Can it be (I guess - yes) that an analogue of Erdos-Gallai result (mentioned in my edit above) holds also for transitive tournaments T_n instead of complete undirected graphs K_n? That is, *every* pure k-cut of T_n must have all but about kn edges of T_n? For this, we only need to ensure that every DAG without a k-path must have an inner vertex of degree at most about k; this [seems](http://en.wikipedia.org/wiki/Talk%3AOre%27s_theorem) to hold. If so, then the answer to my (relaxed) Question 2 would be also NO (for, say, k=n^{1/2}), because then M would already be large, about n^2.
Stasys
CC BY-SA 3.0
2013-01-20T00:51:49.797Z
I'm not sure what you mean by the degree bound. If you mean outdegree, then every DAG has a vertex other than its source s and sink t with outdegree at most one: take the vertex next to t in a topological ordering. On the other hand, if you mean total degree, then it's easy to find DAGs with no k-path in which all nodes have big total degree: arrange the nodes into k-1 layers, with s in the first layer, t in the last layer, and n/(k-3) nodes in every other layer, and connect all pairs of nodes that are in different layers from each other.
David Eppstein
CC BY-SA 3.0
2013-01-20T16:53:56.093Z
Right, k-path-freeness of a digraph only implies outdeg(x)+indeg(y) < 2k-3 for some nonedge (x,y). But your last example ("complete" layered DAG) shows that, in order to destroy all paths (not just s-t paths) in T_n (transitive tournament), it is enough to remove about f(n,k):=k \binom{n/k}{2} = n^2/2k - n/2 edges, far fewer than in K_n (where we need to remove (n-k)n/2 edges). Thus, M \leq f(n,k) in Question 2, meaning that T_n is *not* an immediate counterexample for this question. This is good news. Interestingly, your answer to Question 1 also implies that M\geq f(n,k).
Stasys
CC BY-SA 3.0
2013-01-17T06:41:49.583Z
2013-01-17T16:48:23.947Z
2013-01-17T16:48:23.947Z
David Eppstein
<p>The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest
path dynamic programming algorithm (see <a href="https://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-cyclic-graphs-acyclic">this post</a> for a connection). Also, a positive answer would imply that the minimal size of 
a monotone <a href="http://people.cs.uchicago.edu/~razborov/files/fct.pdf" rel="nofollow noreferrer">nondeterministic branching program</a> for the 
<a href="https://cstheory.stackexchange.com/questions/12841/monotone-complexity-of-s-t-connectivity">STCONN</a> problem is $\Theta(n^3)$.
<p>
Let $G$ be a DAG (directed acyclic graph)
with one source node $s$ and one target node $t$.
A $k$-<b>cut</b> is a set of edges, whose removal destroys all $s$-$t$ paths
of length $\geq k$; we assume that there are such paths in $G$. 
Note that shorter $s$-$t$ paths need <i>not</i> be destroyed.</p>

<blockquote>
<b>Question:</b>
Does $G$ must have at least (about) $k$ <b>disjoint</b> $k$-cuts?
</blockquote>

<p>If there are no $s$-$t$ paths shorter than $k$, the answer is YES, because
we have the following known min-max fact (a dual to
<a href="http://en.wikipedia.org/wiki/Menger%27s_theorem" rel="nofollow noreferrer">Menger’s theorem</a>) attributed to Robacker<sup>$\ast$</sup>.
An $s$-$t$ cut is
a $k$-cut for $k=1$ (destroys <i>all</i> $s$-$t$ paths).</p>

<blockquote>
<b>Fact:</b>
In any directed graph, the <i>maximum</i> number of edge-disjoint $s$-$t$ cuts is equal to the <i>minimum</i> length of an $s$-$t$ path.
</blockquote>

<p>Note that this holds even if the graph is <i>not</i> acyclic.
<p>
<b>Proof:</b>
Trivially, the minimum is at least the maximum, since each $s$-$t$
path intersects
each $s$-$t$ cut in an edge.
To see equality, let $d(u)$ be the length of a shortest path from $s$ to $u$.
Let  $U_r=\{u\colon d(u)=r\}$, for $r = 1,\ldots, d(t)$, and
let $E_r$ be the set of edges leaving $U_r$.
It is clear that the sets $E_r$ are disjoint, because the sets $U_r$ are such.
So, it remains to show that each $E_r$ is an $s$-$t$ cut.
To show this, take an arbitrary $s$-$t$ path $p=(u_1, u_2, \ldots,u_m)$
with $u_1=s$ and $u_m=t$. Since $d(u_{i+1})\leq d(u_i)+1$, the sequence
of distances $d(u_1),\ldots,d(u_m)$ must reach the value
$d(u_m)=d(t)$ by starting at $d(u_1)=d(s)=0$ and increasing the value by at
most $1$ in each step. If some value $d(u_i)$ is decreased , then we must
reach value $d(u_i)$ latter. So, there must be a $j$ where a jump
from $d(u_j)=r$ to $d(u_{j+1})=r+1$ happens, meaning the edge $(u_j,u_{j+1})$
belongs to $E_r$, as desired. Q.E.D.
<p>
But what if there are also shorter (than $k$) paths? Any hint/reference?
<p>
<hr>
$^{\ast}$
J.T. Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network, 
Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California, [12 Jan-
uary] 1956. 
<hr>
<b>EDIT</b> (a day later): Via a short and very nice argument, 
David Eppstein answered the original question 
above in <em>negative</em>: the <strong>complete</strong> DAG $T_n$ (a <a href="http://en.wikipedia.org/wiki/Tournament_%28graph_theory%29" rel="nofollow noreferrer">transitive tournament</a>) cannot have more than four disjoint $k$-cuts! In fact, he proves the following interesting <em>structural</em> fact, for $k$ about $\sqrt{n}$. A cut is <i>pure</i> if it contains no edges incident to $s$ or to $t$.</p>

<blockquote>
Every pure $k$-cut in $T_n$ contains a path of length $k$.
</blockquote>

<p>This, in particular, implies that every two pure $k$-cuts must intersect! But perhaps there still are many pure $k$-cuts that do not overlap
"too much". Hence, a relaxed question (the consequences for STCONN would be the <i>same</i>):</p>

<blockquote>
<b>Question 2:</b> 
If every pure $k$-cut has $\geq M$ edges, does then the graph must have 
about $\Omega(k\cdot M)$ edges?
</blockquote>

<p>The connection with the complexity
of STCONN comes from the <a href="http://www.renyi.hu/~p_erdos/1959-10.pdf" rel="nofollow noreferrer">result</a> of Erd&#337;s and Gallai that one has to remove all but $(k-1)m/2$ edges from (undirected) $K_m$ in order to destroy all paths of length $k$. 
<hr>
<b>EDIT 2:</b> I now asked Question 2 at <a href="https://mathoverflow.net/questions/119511/do-sparse-dags-can-have-large-min-cuts">mathoverflow</a>. </p>

<graph-theory><circuit-complexity><lower-bounds>
How many disjoint edge-cuts a DAG must have?
Stasys
# How many disjoint edge-cuts a DAG must have?

(Asked by: username_0 on 2013-01-15)

The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest
path dynamic programming algorithm (see [this post](https://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-cyclic-graphs-acyclic) for a connection). Also, a positive answer would imply that the minimal size of
a monotone [nondeterministic branching program](http://people.cs.uchicago.edu/~razborov/files/fct.pdf) for the
[STCONN](https://cstheory.stackexchange.com/questions/12841/monotone-complexity-of-s-t-connectivity) problem is $\Theta(n^3)$.

Let $G$ be a DAG (directed acyclic graph)
with one source node $s$ and one target node $t$.
A $k$-**cut** is a set of edges, whose removal destroys all $s$-$t$ paths
of length $\geq k$; we assume that there are such paths in $G$.
Note that shorter $s$-$t$ paths need *not* be destroyed.

> **Question:**
> Does $G$ must have at least (about) $k$ **disjoint** $k$-cuts?

If there are no $s$-$t$ paths shorter than $k$, the answer is YES, because
we have the following known min-max fact (a dual to
[Menger’s theorem](http://en.wikipedia.org/wiki/Menger%27s_theorem)) attributed to Robacker$\ast$.
An $s$-$t$ cut is
a $k$-cut for $k=1$ (destroys *all* $s$-$t$ paths).

> **Fact:**
> In any directed graph, the *maximum* number of edge-disjoint $s$-$t$ cuts is equal to the *minimum* length of an $s$-$t$ path.

Note that this holds even if the graph is *not* acyclic.

**Proof:**
Trivially, the minimum is at least the maximum, since each $s$-$t$
path intersects
each $s$-$t$ cut in an edge.
To see equality, let $d(u)$ be the length of a shortest path from $s$ to $u$.
Let $U\_r=\{u\colon d(u)=r\}$, for $r = 1,\ldots, d(t)$, and
let $E\_r$ be the set of edges leaving $U\_r$.
It is clear that the sets $E\_r$ are disjoint, because the sets $U\_r$ are such.
So, it remains to show that each $E\_r$ is an $s$-$t$ cut.
To show this, take an arbitrary $s$-$t$ path $p=(u\_1, u\_2, \ldots,u\_m)$
with $u\_1=s$ and $u\_m=t$. Since $d(u\_{i+1})\leq d(u\_i)+1$, the sequence
of distances $d(u\_1),\ldots,d(u\_m)$ must reach the value
$d(u\_m)=d(t)$ by starting at $d(u\_1)=d(s)=0$ and increasing the value by at
most $1$ in each step. If some value $d(u\_i)$ is decreased , then we must
reach value $d(u\_i)$ latter. So, there must be a $j$ where a jump
from $d(u\_j)=r$ to $d(u\_{j+1})=r+1$ happens, meaning the edge $(u\_j,u\_{j+1})$
belongs to $E\_r$, as desired. Q.E.D.

But what if there are also shorter (than $k$) paths? Any hint/reference?

---

$^{\ast}$
J.T. Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network,
Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California, [12 Jan-
uary] 1956.

---

**EDIT** (a day later): Via a short and very nice argument,
username_1 answered the original question
above in *negative*: the **complete** DAG $T\_n$ (a [transitive tournament](http://en.wikipedia.org/wiki/Tournament_%28graph_theory%29)) cannot have more than four disjoint $k$-cuts! In fact, he proves the following interesting *structural* fact, for $k$ about $\sqrt{n}$. A cut is *pure* if it contains no edges incident to $s$ or to $t$.

> Every pure $k$-cut in $T\_n$ contains a path of length $k$.

This, in particular, implies that every two pure $k$-cuts must intersect! But perhaps there still are many pure $k$-cuts that do not overlap
"too much". Hence, a relaxed question (the consequences for STCONN would be the *same*):

> **Question 2:**
> If every pure $k$-cut has $\geq M$ edges, does then the graph must have
> about $\Omega(k\cdot M)$ edges?

The connection with the complexity
of STCONN comes from the [result](http://www.renyi.hu/~p_erdos/1959-10.pdf) of Erdős and Gallai that one has to remove all but $(k-1)m/2$ edges from (undirected) $K\_m$ in order to destroy all paths of length $k$.

---

**EDIT 2:** I now asked Question 2 at [mathoverflow](https://mathoverflow.net/questions/119511/do-sparse-dags-can-have-large-min-cuts).

**Tags:** graph-theory, circuit-complexity, lower-bounds


---

## 1 answers

### Answer by username_1 on 2013-01-17. Score: 9 | Accepted answer

Short answer: no.

Let $G$ be a complete DAG (transitive tournament) on $n$ vertices with $s$ and $t$ its source and sink, and let $k=\sqrt{n/3}$. Observe that there can be at most four disjoint cuts that contain more tham $n/3$ edges incident to $s$ or more than $n/3$ edges incident to $t$. So, if there are to be many disjoint cuts, we can assume that there exists a cut $C$ that does not contain large numbers of edges incident to $s$ and $t$.

Now let $X$ be the complete subgraph induced in $G$ by the set of vertices $x$ such that edges $sx$ and $xt$ do not belong to $C$. The number of vertices in $X$ is at least $n/3$, because otherwise $C$ would touch too many edges incident to $s$ or $t$. However, $X\setminus C$ cannot contain a $k$-path, because if such a path existed it could be concatenated with $s$ and $t$ to form a long path in $G\setminus C$. Therefore, the longest-path layering of $X\setminus C$ has fewer than $k$ layers, and has a layer containing more than $(n/3)/k=k$ vertices. Since this is a layer of the longest path layering, it is independent in $X\setminus C$, and therefore complete in $C$, so $C$ contains a path $P$ through the vertices of this layer, of length $k$. This path must be disjoint from all of the other cuts.

Every cut that is not $C$ must contain either the edge from $s$ to the start of path $P$ or the edge from the end of path $P$ to $t$, or else it would not block the path $s$–$P$–$t$. So if $C$ exists, there can be at most three disjoint cuts. And if $C$ does not exist (that is, if all cuts cover more than $n/3$ edges incident to $s$ or to $t$) there can be at most four disjoint cuts. Either way, this is a lot fewer than $k$ cuts.

> **Comments:**
> **username_0**: @ David: Interesting argument (albeit I have not quite understood it yet: why C must have a k-path). But where the argument fails (it should) if *all* s-t paths are long, of length at least k?  
> **username_2**: @username_0: G is a tournament, the proof uses this fact, so imo that is why it would fail.  
> **username_0**: @username_2: thanks, indeed I missed the word "complete". I cannot find a flaw as yet, but this would be a rather counterintuitive fact: even if there are a lot of k-path in an acyclic tournament, we cannot select many disjoint systems of their representatives (edges).  
> **username_0**: @David: Actually, to have the mentioned consequences, we can allow that cuts are only "almost disjoint", i.e may share edges incident to s or t (we have only 2n these special edges). A real goal is to show that G must have about kN edges, if we know that every "pure" k-cut (without these special edges) must have N edges. Can your (very nice, as I now see) argument be modified to this ("almost disjoint") situation?  
> **username_1**: If you allow cuts to share edges incident to s or t, then why can't you make all the cuts consist exactly of the set of edges incident to s? On the other hand, my argument shows that (with its choice of $G$ and $k$) there can be only one pure cut.  
> **username_0**: @David: I cannot see why your argument shows that there can be only one pure k-cut, because now we allow that cuts *can* share the edge s->P and/or P->t. Am I missing something? I don't want to take just edges leaving s - the goal is to show that G must have many edges if there are many pure k-cuts.  
> **username_1**: You defined a pure cut to be a cut that has no special edges, right? So it would fit the criteria of the cut $C$ in my argument.  
> **username_0**: Yes, you are right: any other pure k-cut must intersect C. A nice fact! But what about the relaxed Question 2? That is, knowing that each k-cut must have N edges, can we then conclude that there must be at least about k times N edges in the graph? I haven't marked your nice answer as "accepted" yet only because I won't close it: there remains a small hope that Question 2 still has an affirmative answer.  
> **username_0**: @David: Can it be (I guess - yes) that an analogue of Erdos-Gallai result (mentioned in my edit above) holds also for transitive tournaments T_n instead of complete undirected graphs K_n? That is, *every* pure k-cut of T_n must have all but about kn edges of T_n? For this, we only need to ensure that every DAG without a k-path must have an inner vertex of degree at most about k; this [seems](http://en.wikipedia.org/wiki/Talk%3AOre%27s_theorem) to hold. If so, then the answer to my (relaxed) Question 2 would be also NO (for, say, k=n^{1/2}), because then M would already be large, about n^2.  
> **username_1**: I'm not sure what you mean by the degree bound. If you mean outdegree, then every DAG has a vertex other than its source s and sink t with outdegree at most one: take the vertex next to t in a topological ordering. On the other hand, if you mean total degree, then it's easy to find DAGs with no k-path in which all nodes have big total degree: arrange the nodes into k-1 layers, with s in the first layer, t in the last layer, and n/(k-3) nodes in every other layer, and connect all pairs of nodes that are in different layers from each other.  
> **username_0**: Right, k-path-freeness of a digraph only implies outdeg(x)+indeg(y) < 2k-3 for some nonedge (x,y). But your last example ("complete" layered DAG) shows that, in order to destroy all paths (not just s-t paths) in T_n (transitive tournament), it is enough to remove about f(n,k):=k \binom{n/k}{2} = n^2/2k - n/2 edges, far fewer than in K_n (where we need to remove (n-k)n/2 edges). Thus, M \leq f(n,k) in Question 2, meaning that T_n is *not* an immediate counterexample for this question. This is good news. Interestingly, your answer to Question 1 also implies that M\geq f(n,k).  

---

