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

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

• How can you guarantee that a rank $2$ vertex exists? – Manuel Lafond Oct 8 '18 at 2:30
• @ManuelLafond A vertex of rank $r + 1$ has an edge from a vertex of rank $r$ to it, hence we can reduce from a vertex of rank $\geq 2$ to a vertex of rank $2$. – Mikhail Tikhomirov Oct 8 '18 at 4:17
• Thank you. So the question I really had in mind was: if the graph is just a directed cycle, what are the ranks of the vertices? – Manuel Lafond Oct 8 '18 at 5:07
• @ManuelLafond In this question the graph is supposed to be acyclic. The upper bound given doesn't work for cyclic graphs (although, the question is still interesting in cyclic setting). – Mikhail Tikhomirov Oct 8 '18 at 5:11
• Relaxing acyclicity, we would have $\alpha\geq 2/3$, due to the graph with vertex set $\{0,\dots,5\}$ and edges $i\to i+1,i+2\mod 6$. – Ilya Bogdanov Oct 8 '18 at 9:00

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.

• Good! It is also interesting whether this estimate is sharp if we relax the in-degrees condition... – Ilya Bogdanov Oct 8 '18 at 8:25