Small Feedback Vertex Sets in Planar Digraphs

  • Louis Esperet
  • Laetitia Lemoine
  • Frédéric Maffray
Keywords: Planar Digraphs, Digirth, Feedback Vertex Sets

Abstract

Let $G$ be a directed planar graph on $n$ vertices, with no directed cycle of length less than $g\ge 4$. We prove that $G$ contains a set $X$ of vertices such that $G-X$ has no directed cycle, and $|X|\le \tfrac{5n-5}9$ if $g=4$, $|X|\le \tfrac{2n-5}4$ if $g=5$, and $|X|\le \tfrac{2n-6}{g}$ if $g\ge 6$. This improves recent results of Golowich and Rolnick.

Published
2017-04-13
Article Number
P2.6