Packing Even Directed Circuits Quarter-Integrally

We prove the existence of a computable function f ∶ℕ→ℕ such that for every integer k and every digraph D , either D contains a collection C of k directed cycles of even length such that no vertex of D belongs to more than four cycles in C , or there exists a set S ⊆ V ( D ) of size at most f ( k ) such that D − S has no directed cycle of even length. Moreover, we provide an algorithm that finds one of the two outcomes of this statement in time g ( k ) n O (1) for some computable function g ∶ ℕ→ℕ.

Authors

• Maximilian Gorsky
• Ken-ichi Kawarabayashi
• Stephan Kreutzer
• Sebastian Wiederrecht

Keywords

• Directed Graphs
• Erdős-Pósa property
• Even Dicycles
• Fixed Parameter Tractability
• Graph Structure Theory
• Matching Theory