{"id":"arxiv/2605.12279","url":"https://arxiv.org/abs/2605.12279","tags":["math.CO","cs.DM"],"score":0,"title":"Feedback vertex sets of planar digraphs with fixed digirth","domain":"math.CO","source":"arxiv","authors":["Simon Dreyer","Alexandre Pinlou","Petru Valicov"],"reviews":0,"subject":"math.CO","summary":"Let $fvs(G)$ denote the size of a minimum feedback vertex set of a digraph $G$. We study $fvs_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 $fvs_g(n)\\le \\frac{n-2}{g-2}$ for all $g\\geq 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-12","reactions":{}}