7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How can you guarantee that a rank $2$ vertex exists? $\endgroup$ – Manuel Lafond Oct 8 '18 at 2:30
  • $\begingroup$ @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$. $\endgroup$ – Mikhail Tikhomirov Oct 8 '18 at 4:17
  • $\begingroup$ 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? $\endgroup$ – Manuel Lafond Oct 8 '18 at 5:07
  • $\begingroup$ @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). $\endgroup$ – Mikhail Tikhomirov Oct 8 '18 at 5:11
  • $\begingroup$ 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$. $\endgroup$ – Ilya Bogdanov Oct 8 '18 at 9:00
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.