The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortestpath 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$ pathsof 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, becausewe have the following known min-max fact (a dual toMengers theorem) attributed to Robacker$\ast$.An $s$-$t$ cut isa $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 intersectseach $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)$, andlet $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 sequenceof 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 atmost $1$ in each step. If some value $d(u_i)$ is decreased , then we mustreach value $d(u_i)$ latter. So, there must be a $j$ where a jumpfrom $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 overlaptoo 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 complexityof 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. 
How many disjoint edge-cuts a DAG must have?
graph theory;circuit complexity;lower bounds
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.