For a graph $G$, let $e(G)$ denote the number of its edges, and $c_k(G)$ the smallest number
of edges that must be removed in order to destroy all paths of length $\geq k+1$.
Note that $c_1(G)\geq c_2(G)\geq \ldots\geq c_k(G)\geq \ldots$.
Let $K_n$ be a complete graph, and $T_n$ a complete acyclic digraph ([transitive tournament](http://en.wikipedia.org/wiki/Tournament_%28graph_theory%29)) on $n$
vertices; hence $e(K_n)=e(T_n)=\tbinom{n}{2}$.
<p> 
A classical [result](http://www.renyi.hu/~p_erdos/1959-10.pdf) of Erd&#337;s and Gallai
states that 
$$
c_k(K_n)=e(K_n)-\frac{kn}{2}.
$$
In contrast, for the directed acyclic analogue $T_n$ of $K_n$, we have
$$
c_k(T_n)= \frac{e(T_n)}{k}.
$$
<b>Proof:</b> To show $c_k(T_n)\leq e(T_n)/k$, take a topological order of vertices of $T_n$: 
vertices $i$ and $j$ are adjacent iff
$i < j$. Split the vertices into $k$ consecutive intervals of length $n/k$. If we remove all
edges whose both endpoints lie in the same interval, then we destroy all paths of length $\geq k+1$. 
 Since only $k\tbinom{n/k}{2}=n^2/2k-n/2\leq e(T_n)/k$ edges were removed, we are done. 
<p>
 The other direction $c_k(T_n)\geq e(T_n)/k$ was essentially shown
by David Epppstein in this [answer](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have):
Let $C$ be a set of edges that must be removed in order to destroy all paths of length $≥k+1$ in $T_n$. Split the vertices into $t\leq k$ layers, where the $i$-th layer
contains all vertices $u$ such that the length of a longest path to $u$ in $T_n\setminus C$
 has length $i$. Since each layer is a layer of the <i>longest-path</i> layering,
it is independent in $T_n\setminus C$, and therefore complete in $C$.
Thus, if $n_i$ is the number of vertices in the $i$-th layer, then
the total number of edges in $C$ is at least
$\sum_{i=1}^t\tbinom{n_i}{2}\geq t\tbinom{n/t}{2}\geq k\tbinom{n/k}{2}$, as desired. 
Q.E.D. 
<p>
Motivated by this (remarkable) difference between $c_k(K_n)$ and $c_k(T_n)$, here is my 
<blockquote>
<b>Question:</b>
Does $c_k(G)$ is at most "about" $e(G)/k$ for <i>every</i> acyclic digraph $G$?
</blockquote>
By "about" I mean  "times some absolute constant or times some slowly growing function in $n$".
Also, here we may assume that $c_k(G)$ is the smallest number
of edges that must be removed in order to destroy all paths of length $\geq k+1$ going from 
a source (fanin $0$) node to a target (fanout $0$) node, not necessarily <i>all</i> possible
paths of this length. 

<p>

Note that the problem is only to get rid with graphs having also short paths (shorter than $k$), 
because $c_1(G)\leq e(G)/t$ holds
for any (not necessarily acyclic) digraph $G$, where $t$ is the length of a shortest source-to-target path. This is a direct consequence of
a dual to
[Menger’s theorem](http://en.wikipedia.org/wiki/Menger%27s_theorem) (attributed to Robacker):
in any directed graph, the <i>minimum</i> length $t$ of a path is equal
to the <i>maximum</i> number of edge-disjoint cuts. (The proof is elementary, see e.g.
[here](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have).)
<p>
Besides being natural in itself, an affirmative answer to my question would have some interesting consequences in [boolean function complexity](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) (see [this](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have) post and references herein).