Abstrakt
The celebrated Erdos-Posa theorem states that every undirected graph that does not admit a family of k vertex-disjoint cycles contains a feedback vertex set (a set of vertices hitting all cycles in the graph) of size O(k logk). The analogous result for directed graphs has been proven by Reed, Robertson, Seymour, and Thomas, but their proof yields a nonelementary dependency of the size of the feedback vertex set on the size of vertexdisjoint cycle packing.
We show that we can obtain a polynomial bound if we relax the disjointness condition. More precisely, we show that if in a directed graph G there is no family of k cycles such that every vertex of G is in at most two (resp. four) of the cycles, then there exists a feedback vertex set in G of size O(k^6) (resp.
O(k^4)). We show also variants of the above statements for butterfly minor models of any strongly connected digraph that is a minor of a directed cylindrical grid and for quarter-integral packings of subgraphs of high directed treewidth.