Packing Arc-Disjoint Cycles in Tournaments
Résumé
A tournament is a directed graph in which there is a single arc between every pair of distinct
vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity
of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of
size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these
problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in
Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the
linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of
arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results
seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show
that the problem of determining if a tournament has a cycle packing and a feedback arc set of the
same size is NP-complete. Next, we prove that ACT and ATT are fixed-parameter tractable, they
can 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.
Origine | Fichiers produits par l'(les) auteur(s) |
---|