(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!

(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!

(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.

Any better (upper or lower) bound is welcome!

(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!