Let $G=(V,E)$ be a directed acyclic graph. Define the set of all directed paths in $G$ by $\Gamma$. Given a subset $W\subseteq V$, let $\Gamma_W\subseteq \Gamma$ be the set of all paths in $\Gamma$ supported on $V\backslash W$. Now define $l(W)$ to be: $$l(W)=max_{\gamma\in \Gamma_W} |\gamma|$$
I want to show that for every $\epsilon>0$ and every $k>0$, there exists a constant $L$ such that for any directed acyclic graph $G=(V, E)$ with ingoing and outgoing degree bounded by $k$, there exists a subset $W\subseteq V$ such that $\frac{|W|}{|V|}<\epsilon$ and $l(W)<L$.
While it is obviously true for directed trees since you can just remove all vertices at some given depths to block any path going down the tree, the same approach fails to work in more general DAGs. Moreover, the statement fails to be true if we remove the constant degree requirement for $G$.
Any direction or idea would be welcome.
PS. Crossposted at MSE.
