Feedback vertex sets of planar digraphs with fixed digirth

Abstract

Let $fvs(G)$ denote the size of a minimum feedback vertex set of a digraph $G$. We study $fv{s}_g(n)$, which is the maximum $fvs(G)$ over all $n$-vertex planar digraphs $G$ of digirth $g$. We prove a planar-digraph analogue of the celebrated Lucchesi-Younger theorem showing that the minimum feedback vertex set is at most the maximum packing of a special type of directed cycles. As a corollary, we derive that $fv{s}_g(n)\le \frac{n-2}{g-2}$ for all $g\ge 3$. This improves all previously known upper bounds for $g\ge 4$, and for $g\ge 6$ it supersedes the best known upper bound of $\frac{2n-6}{g}$ (Esperet, Lemoine and Maffray, 2017) by a factor of 2. On the other hand, we develop a new framework to construct planar digraphs of fixed digirth and large $fvs$. Using it, for $g=6$ and every $g\ge 8$, we construct an infinite family of planar digraphs of digirth $g$ and $fvs(G)=\frac{g+2}{g^2}n+O(1)$. For $g=7$, our construction gives $fvs(G)=\frac{2}{11}n+O(1)$ and for $g=4$ and $5$, $fvs(G)=\frac{n}{g-1}$. These improve the best known lower bound of $\frac{n-1}{g-1}$ (Knauer, Valicov and Wenger, 2017) for all $g\ge 4$. We thus obtain the two-sided bound $\frac{g+2}{g^2}\le {\sup }_{n\ge 1}\frac{fv{s}_g(n)}{n}\le \frac{1}{g-2}$ for all values $g=6$ and every $g\ge 8$. The gap between the lower and the upper bound for ${\sup }_{n\ge 1}\frac{fv{s}_g(n)}{n}$ decreases from $\frac{g-2}{g(g-1)}$ to $\frac{4}{g^2(g-2)}$.

54 pages

Topics & keywords