Blocking $a\to b\to c$ in a DAG with bounded degrees

Question

(This is an (easy-looking) toy question for this one.)

Question. Find the smallest $\alpha$ satisfying the following:

Let $G=(V,E)$ be a finite directed acyclic graph, where each in- and out-degree is at most $2$. Then it is possible to remove at most $\alpha|V|$ vertices so that the remaining graph contains no (directed) path with $3$ vertices.

I seem to have troubles even with this setup; if it can be answered, then, surely, a more general question would be about the graphs with all (in- and out-) degrees bounded by $k$.

What I know.

($1$) $\alpha\geq 1/2$. This is achieved on every graph with $4n$ vertices $v_1,\dots,v_{4n}$ and edges $v_i\to v_{i+1}$ and $v_i\to v_{i+2}$.

($2$) $\alpha\leq 3/5$. This can be shown by induction on $|V|$. Say that the rank of a vertex is the maximal length (=number of vertices) of a path ending at that vertex. If all vertices are of rank $1$, then the graph has no edges. Otherwise, let $s$ be a rank $2$ vertex, with $v\to s$ an incoming edge. Now one can remove the other neighbor of $v$ (if it exists), all the out-neighbors of $s$, thus making $v$ and $s$ ``safe''. So one may forget about $v$ and $s$, and proceed by induction.

UPD: ($2'$) $\alpha\leq 4/7$: see an answer by Mikhail Tikhomirov.

Any better (upper or lower) bound is welcome!

Answer 1

We can obtain $\alpha \leq 4/7$ as follows. Process vertices in a topological order and divide them into three sets $V_0, V_1, V_2$ as follows:

• if all edges leading into $v$ start in $V_2$, then $v \in V_0$ (in particular, all vertices with in-degree 0 go to $V_0$);
• if there is an edge $u \to v$ with $u \in V_1$, then $v \in V_2$;
• otherwise, $v \in V_1$ (in this case, there is an edge from $V_0$ and no edge from $V_1$).

We claim that removing $V_2$ breaks all paths of length 3. Indeed, suppose that there is a path $v \to u \to w$ confined to $V_0 \cup V_1$. All edges leaving $V_1$ go to $V_2$, hence $v, u \in V_0$. But simultaneously $u \not \in V_0$ by construction, a contradiction.

Further, we claim $|V_1| \leq 2|V_0|$ and $|V_2| \leq 2|V_1|$. Indeed, for any $v \in V_1$ there is an edge $u \to v$ with $u \in V_0$, and all such edges are distinct, but the number of these edges is at most $2|V_0|$. The second bound is completely analogous.

The bounds above imply $|V| = |V_0| + |V_1| + |V_2| \geq |V_2|/4 + |V_2|/2 + |V_2| = 7|V_2|/4$, hence $|V_2| \leq 4|V|/7$.

This upper bound still doesn't seem tight (for instance, we didn't at all use the fact that all in-degree are $\leq 2$). I believe $\alpha = 1/2$ is attainable. Will update later hopefully.