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

Let G=(V,E) be a directed acyclic graph.
Define the set of all directed paths in G by Γ.
Given a subset WV, let
ΓWΓ be the set of all paths γΓ supported on VW (i.e all vertices in γ belong to VW).
Now define l(W) to be:
Where |\gamma| is the number of vertices in \gamma.

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

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

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 G. Indeed, the maximal topological order on vertices indexed from 1 to n can not be "blocked" for any \epsilon>0 by any set W of size linear in n.

Any direction or idea would be welcome.

Edit 1:

For trees, a standard proof would go like this: For 0\leq i\leq L-1, Define W_L^i to be the set of all vertices reachable from the root with a directed path of length i \pmod L. Since the graph is a tree, any such path is uniquely defined for every vertex and therefore, for a given L, the set \{W_L^i\}_{0\leq i\leq L-1} gives a partition of V. Therefore choosing L=\frac{1}{\epsilon}, there is some i_0 such that |W_L^{i_0}| is at most \frac{|V|}{L}=\epsilon |V|. It is left to show that every W_L^i is indeed L-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^i has to be of length at most L-1 (Connecting 2 adjacent floors in W_L^i)

Edit 2:

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

1- choose a vertex v in the graph that still has neighbours. Keep v, 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=1) and we removed at most an \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}.
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} where the previous bound is only \epsilon=\frac{2}{3}.
Define the in-degree and out-degree of a vertex v in G by in(v) and out(v) respectively. From the assumption, for all v \in V, in(v)+out(v)\leq 3. Define 4 sets: \{V_i\}_{i=0}^3 by:
V_i=\{v\in V | in(v)=i\}

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

This proves the claim.

PS. Crossposted at MO.


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 🙂

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

Leave a Comment