Speaker: Tomas Masarik
Title: Packing Directed Circuits Quarter-Integrally
Abstract:
The celebrated Erdős-Pósa 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 log k). After being known for long as Younger’s
conjecture, a similar statement for directed graphs has been proven in
1996 by Reed, Robertson, Seymour, and Thomas. However, in their proof,
the dependency of the size of the feedback vertex set on the size of
vertex-disjoint cycle packing is not elementary.

We show that if we compare the size of a minimum feedback vertex set
in a directed graph with quarter-integral cycle packing number, we
obtain a polynomial bound. 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 four of the cycles, then there exists a feedback
vertex set in G of size O(k^4 ). On the way there we prove a more
general result about quarter-integral packing of subgraphs of high
directed treewidth: for every pair of positive integers a and b, if a
directed graph G has directed treewidth Ω(a^6 b^8 log^2 (ab)), then
one can find in G a family of a subgraphs, each of directed treewidth
at least b, such that every vertex of G is in at most four subgraphs.