STOC2024

Packing Even Directed Circuits Quarter-Integrally

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

1 citation

Abstract

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)nO(1) for some computable function g∶ ℕ→ℕ.