# Blocking directed paths on a DAG with a linear number of vertex defects.

Let $$G=(V,E)G=(V,E)$$ be a directed acyclic graph.
Define the set of all directed paths in $$GG$$ by $$Γ\Gamma$$.
Given a subset $$W⊆VW\subseteq V$$, let
$$ΓW⊆Γ\Gamma_W\subseteq \Gamma$$ be the set of all paths $$γ∈Γ\gamma\in\Gamma$$ supported on $$V∖WV\backslash W$$ (i.e all vertices in $$γ\gamma$$ belong to $$V∖WV\backslash W$$).
Now define $$l(W)l(W)$$ to be:
$$l(W)=maxl(W)=\max_{\gamma\in \Gamma_W} |\gamma|$$
Where $$|\gamma||\gamma|$$ is the number of vertices in $$\gamma\gamma$$.

I want to prove (or disprove) the following claim:

$${\bf Claim:}{\bf Claim:}$$ For every $$\epsilon>0\epsilon>0$$ and every $$k>0k>0$$, there are constants $$LL$$ and $$NN$$ such that for any directed acyclic graph $$G=(V, E)G=(V, E)$$ satisfying $$|V|>N|V|>N$$ with the sum of incoming and outgoing degrees bounded by $$kk$$, there exists a subset $$W\subseteq VW\subseteq V$$ such that $$\frac{|W|}{|V|}<\epsilon\frac{|W|}{|V|}<\epsilon$$ and $$l(W).

The claim is true for directed trees (see edit 1 for a proof) but the same proof idea fails to work in more general DAGs.
Moreover, the statement fails to be true if we remove the constant degree requirement for $$GG$$. Indeed, the maximal topological order on vertices indexed from 1 to n can not be "blocked" for any $$\epsilon>0\epsilon>0$$ by any set $$WW$$ of size linear in $$nn$$.

Any direction or idea would be welcome.

Edit 1:

For trees, a standard proof would go like this: For $$0\leq i\leq L-10\leq i\leq L-1$$, Define $$W_L^iW_L^i$$ to be the set of all vertices reachable from the root with a directed path of length $$i \pmod Li \pmod L$$. Since the graph is a tree, any such path is uniquely defined for every vertex and therefore, for a given $$LL$$, the set $$\{W_L^i\}_{0\leq i\leq L-1}\{W_L^i\}_{0\leq i\leq L-1}$$ gives a partition of $$VV$$. Therefore choosing $$L=\frac{1}{\epsilon}L=\frac{1}{\epsilon}$$, there is some $$i_0i_0$$ such that $$|W_L^{i_0}||W_L^{i_0}|$$ is at most $$\frac{|V|}{L}=\epsilon |V|\frac{|V|}{L}=\epsilon |V|$$. It is left to show that every $$W_L^iW_L^i$$ is indeed $$LL$$-blocking, but this is trivial since any step in a directed path down the tree increases the distance from the root by exactly 1, so the longest path containing no vertices from $$W_L^iW_L^i$$ has to be of length at most $$L-1L-1$$ (Connecting 2 adjacent floors in $$W_L^iW_L^i$$)

Edit 2:

In general, the claim is true for any DAG for the special case of $$\epsilon = \frac{2k}{2k+1}\epsilon = \frac{2k}{2k+1}$$ and $$L=1L=1$$. To see that consider the following algorithm:

1- choose a vertex $$vv$$ in the graph that still has neighbours. Keep $$vv$$, and remove all of its neighbours (in both directions) from graph

2 - if any non isolated vertex is left, go back to 1. Otherwise exit.

The resulting graph is completely disconnected ($$L=1L=1$$) and we removed at most an $$\epsilon=\frac{2k}{2k+1}\epsilon=\frac{2k}{2k+1}$$ fraction of vertices from the graph.
The claim follows.

Edit 3:

As Misha Lavrov showed, the previous bound can be made tighter and we can prove the claim for $$\epsilon=\frac{k}{k+1}\epsilon=\frac{k}{k+1}$$.
I discovered that this bound is not tight when the DAG has total degree bounded by 3. In this case, I will prove the claim for any $$\epsilon>\frac{1}{2}\epsilon>\frac{1}{2}$$ where the previous bound is only $$\epsilon=\frac{2}{3}\epsilon=\frac{2}{3}$$.
Define the in-degree and out-degree of a vertex $$vv$$ in $$GG$$ by $$in(v)in(v)$$ and $$out(v)out(v)$$ respectively. From the assumption, for all $$v \in Vv \in V$$, $$in(v)+out(v)\leq 3in(v)+out(v)\leq 3$$. Define 4 sets: $$\{V_i\}_{i=0}^3\{V_i\}_{i=0}^3$$ by:
$$V_i=\{v\in V | in(v)=i\}V_i=\{v\in V | in(v)=i\}$$

Obviously, $$\{V_i\}_{i=0}^3\{V_i\}_{i=0}^3$$ forms a partition of $$VV$$. Therefore, either of the sets $$V_1V_1$$ or $$V_2V_2$$ has cardinality at most $$\frac{n}{2}\frac{n}{2}$$. W.l.o.g, assume it is $$V_1V_1$$.
Let $$G'G'$$ be the subgraph of $$GG$$ induced by $$V_2V_2$$. Obviously, for all $$v\in V_2v\in V_2$$, $$out(v)\leq 1out(v)\leq 1$$ and therefore, $$G'G'$$ is a disjoint union of directed trees with one vertex sink. Using the proof for trees, for any $$\epsilon>0\epsilon>0$$, we can find a subset $$W\subseteq V_2W\subseteq V_2$$ such that $$\frac{|W|}{|V_2|}<\epsilon\frac{|W|}{|V_2|}<\epsilon$$ and $$WW$$ is $$\frac{1}{\epsilon}\frac{1}{\epsilon}$$-blocking in $$G'G'$$.
Finally, define $$W'= V_1 \cup WW'= V_1 \cup W$$. On one hand, $$|W'||W'|$$ is upper bounded by $$(\frac{1}{2}+\epsilon)n(\frac{1}{2}+\epsilon)n$$ and on the other hand $$W'W'$$ is $$(\frac{1}{\epsilon}+2)(\frac{1}{\epsilon}+2)$$-blocking since a directed path in $$GG$$ can either stay in $$V_2V_2$$ and get blocked by $$WW$$ or get outside of $$V_2V_2$$ and either be blocked by $$V_1V_1$$ or do one last step from $$V_0V_0$$, to $$V_3V_3$$ or both.

This proves the claim.

PS. Crossposted at MO.

## Answer

I know it is a bad style but I have no time for proper typing now (maybe I'll do it later), so here is a set of handwritten notes with a counterexample. Questions are welcome, as usual 🙂

Attribution
Source : Link , Question Author : Yonathan Touati , Answer Author : fedja