Packing arc-disjoint cycles in oriented graphs
Jasine Babu, Ajay Saju Jacob, R. Krithika, Deepak Rajendraprasad · Journal of Computer and System Sciences · 2024
Arc-Disjoint Cycle Packing is a classical NP -complete problem and we study it from two perspectives: (1) by restricting the cycles in the packing to be of a fixed length, and (2) by restricting the inputs to bipartite tournaments. Focusing first on Arc-Disjoint r -Cycle Packing (where the cycles in the packing are required to be of length r ), we show NP -completeness in oriented graphs with girth r for each r ≥ 3 and study the parameterized complexity of the problem with respect to two parameterizations (solution size and vertex cover size) for r = 4 in oriented graphs. Moving on to Arc-Disjoint Cycle Packing in bipartite tournaments, we show that every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7 ( k − 1 ) . This result adds to the set of Erdös-Pósa-type results known in the combinatorics literature for packing and covering problems.