How expensive may it be to destroy all long s-t paths in a DAG?

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$.
2. If $G=T_n$ is a transitive tournament (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 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 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 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 exist¹ 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 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$.

¹The construction is given in this paper. 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}$.

Asked by user5788 (1 )
Jun 25, 2015 at 13:33