Feedback vertex sets in oriented graphs

Abstract

For an oriented graph $G$, denote by $fvs(G)$ the minimum number of vertices whose deletion from $G$ makes it acyclic. We show that an oriented graph $G$ on $n$ vertices and $m$ arcs satisfies $fvs(G)\le \frac{2n+m+h}{9}$ where $h$ denotes the number of connected components of $G$ that belong to a special class of oriented graphs. This result has three consequences. First, when $G$ is planar, we obtain that $fvs(G)\le \frac{2n+m}{9}$. In particular, this implies that $fvs(G)\le \frac{5n-6}{9}$ for any planar oriented graph $G$, improving the best known upper bound of $\frac{3n}{5}$~[Borodin, Discrete Mathematics, 1979]. Then, applying this inequality to the planar digraphs without directed triangles, we get that $fvs(G)\le \frac{6n-8}{13}$, which improves the current best bound of $\frac{n}{2}$~[Li and Mohar, SIAM Journal on Discrete Mathematics, 2017]. Finally, when $G$ has maximum degree 6, we have $fvs(G)\le \frac{4n}{7}$ and this bound is tight, answering a conjecture of Ai, Gutin, Liu, Yeo and Zhou~[arXiv:2512.01676, 2025].

15 pages, 14 figures

Topics & keywords