Kernelization of Arc Disjoint Cycle Packing in α-Bounded Digraphs

In the Arc Disjoint Cycle Packing problem, we are given a simple directed graph (digraph) G, a positive integer k, and the task is to decide whether there exist k arc disjoint cycles. The problem is known to be W[1]-hard on general digraphs parameterized by the standard parameter k. In this paper we show that the problem admits a polynomial kernel on α-bounded digraphs. That is, we give a polynomial-time algorithm, that given an instance (D,k) of Arc Disjoint Cycle Packing, outputs an equivalent instance $(D^{\prime },k^{\prime })$ of Arc Disjoint Cycle Packing, such that $k^{\prime }\leq k$ and the size of $D^{\prime }$ is upper-bounded by a polynomial function of k. For any integer α ≥ 1, the class of α-bounded digraphs, denoted by ${\mathcal D}_{\alpha }$ , contains a digraph D such that the maximum size of an independent set in D is at most α. That is, in D, any set of α + 1 vertices has an arc with both end-points in the set. For α = 1, this corresponds to the well-studied class of tournaments. Our results generalize the recent result by Bessy et al. [MFCS, 2019] about Arc Disjoint Cycle Packing on tournaments.