{"id":"arxiv/2611.06250","url":"https://arxiv.org/abs/2611.06250","tags":["cs.DM","cs.DS","math.CO"],"score":0,"title":"A Polynomial Erdős-Pósa bound for Eulerian digraphs","domain":"cs.DM","source":"arxiv","authors":["Esther Galby","Roohani Sharma","Bart van der Steenhoven"],"reviews":0,"subject":"cs.DM","summary":"In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erdős-Pósa property. Specifically, they showed that every directed graph $D$ contains either $k$ arc-disjoint cycles or a set of at most $f(k)$ arcs that intersect every directed cycle. The function $f$, depending only on $k$, is however notoriously large--in fact, not even elementary. The first improvement on this function was only very recently provided by Hatzel, Kreutzer, Milani, and Muzi [FOCS 2024] who showed that $f$ can be taken to be…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}