A Polynomial Erdős-Pósa bound for Eulerian digraphs
Source: arxiv.org/abs/2611.06250
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.06250
curl -X POST /api/v1/records/arxiv/2611.06250/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06250/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'