How many disjoint edge-cuts a DAG must have?

Question

The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest path dynamic programming algorithm (see this post for a connection). Also, a positive answer would imply that the minimal size of a monotone nondeterministic branching program for the STCONN 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) 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, David Eppstein answered the original question above in negative: the complete DAG $T_n$ (a transitive tournament) 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 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.

Answer 1

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.