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.

  • $\begingroup$ What do you mean by "supported on" $V \setminus W$? Do you mean that a path $\gamma \in \Gamma_W$ has all vertices in $V \setminus W$ or some vertices. And by $|\gamma|$ you mean the number of vertices in the path $\gamma$? $\endgroup$
    – Mike
    Aug 28, 2018 at 22:38
  • $\begingroup$ All vertices in $V\backslash W$. And yes, $|\gamma|$ is the number of vertices in $\gamma$ $\endgroup$ Aug 28, 2018 at 23:06
  • $\begingroup$ @Forester Erm.. Is there anything wrong with my counterexample in the MSE thread that prompted you to revive this MO thread with a bounty? $\endgroup$
    – fedja
    Jan 23, 2021 at 20:38
  • $\begingroup$ @fedga Sir, the bounty is from 6 days ago. Your answer was wonderful. $\endgroup$
    – Forester
    Jan 24, 2021 at 16:25
  • $\begingroup$ @Forester Indeed. I misread the time stamp. My apologies then :-) $\endgroup$
    – fedja
    Jan 24, 2021 at 19:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy