Polynomial bound found for cycle packing in Eulerian directed graphs
A Polynomial Erdős-Pósa bound for Eulerian digraphs
Discrete MathematicsData Structures and Algorithms
Summary
The paper tackles a problem about cycles in special kinds of directed graphs called Eulerian digraphs. It improves how well we can find either many separate cycles or a small set of links that block all cycles. Previous work provided huge bounds that were hard to work with, but the authors show a much smaller, polynomial (fourth power) bound for this problem on Eulerian digraphs. They also show that the simplest kind of bound is not possible for all such graphs, providing a new limitation. This answers an open question about when polynomial bounds can exist in this area.
What this means in practice
- •For network schedulers: Optimize detection or elimination of feedback cycles in communication or data flow networks modeled by Eulerian digraphs using a polynomial bound on cycle blockers.
- •For circuit designers: Improve analysis of circuit feedback loops by bounding the number of components needed to intersect all cyclic paths in Eulerian digraph representations.
A theory result. No direct application yet.
Authors
Esther Galby, Roohani Sharma, Bart van der Steenhoven
Abstract
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 an exponential tower of height $8$. In this work, we improve this function to $O(k^4)$ in the case where the digraph is Eulerian. This also answers an open question by Wahlström [Springer Monographs in Mathematics 2018] who asked explicitly when Eulerian digraphs have a polynomial Erdős-Pósa property. The only other known result about Erdős-Pósa on Eulerian digraphs is a result from Seymour [Combinatorica 1996] who showed that $f(k)=k$ when the Eulerian digraph admits a linkless embedding in 3-space, and such an equality is not possible for general Eulerian digraphs. We also complement our positive result, by showing that the result of Seymour cannot be extended to give a linear bound ($O(k)$) on general Eulerian digraphs, by showing that even on Eulerian digraphs the lower bound for the Erdős-Pósa property is $Ω(k \log k)$.