Abstract
A tournament is a directed graph in which there is a single arc between every pair of distinctvertices. Given a tournament T on n vertices, we explore the classical and parameterized complexityof the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) ofsize k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to theseproblems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles inTournaments (ATT), respectively. Although the maximization version of ACT can be seen as thelinear programming dual of the well-studied problem of finding a minimum feedback arc set (a set ofarcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic resultsseem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we showthat the problem of determining if a tournament has a cycle packing and a feedback arc set of thesame size is NP-complete. Next, we prove that ACT and ATT are fixed-parameter tractable, theycan be solved in 2O(k log k)nO(1) time and 2O(k)nO(1) time respectively. Moreover, they both admit √a kernel with O(k) vertices. We also prove that ACT and ATT cannot be solved in 2o( k)nO(1) time under the Exponential-Time Hypothesis.