Get all the updates for this publication

Open Access

Packing Arc-Disjoint Cycles in Tournaments

Published in Springer Nature

2021

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 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 is fixed-parameter tractable via a 2O(klogk)nO(1)${2}^{\mathcal{O}(k\mathrm{log}k)}{n}^{\mathcal{O}(1)}$-time algorithm and admits a kernel with O(k)$\mathcal{O}(k)$ vertices. Then, we show that ATT too has a kernel with O(k)$\mathcal{O}(k)$ vertices and can be solved in 2O(k)nO(1)${2}^{\mathcal{O}(k)}{n}^{\mathcal{O}(1)}$ time. Afterwards, we describe polynomial-time algorithms for ACT and ATT when the input tournament has a feedback arc set that is a matching. We also prove that ACT and ATT cannot be solved in 2o(n√)nO(1)${2}^{o(\sqrt{n})}{n}^{\mathcal{O}(1)}$ time under the exponential-time hypothesis.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 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 is fixed-parameter tractable via a 2O(klogk)nO(1)${2}^{\mathcal{O}(k\mathrm{log}k)}{n}^{\mathcal{O}(1)}$-time algorithm and admits a kernel with O(k)$\mathcal{O}(k)$ vertices. Then, we show that ATT too has a kernel with O(k)$\mathcal{O}(k)$ vertices and can be solved in 2O(k)nO(1)${2}^{\mathcal{O}(k)}{n}^{\mathcal{O}(1)}$ time. Afterwards, we describe polynomial-time algorithms for ACT and ATT when the input tournament has a feedback arc set that is a matching. We also prove that ACT and ATT cannot be solved in 2o(n√)nO(1)${2}^{o(\sqrt{n})}{n}^{\mathcal{O}(1)}$ time under the exponential-time hypothesis.

Content may be subject to copyright.

About the journal

Publisher | Data powered by TypesetSpringer Nature |
---|---|

Open Access | Yes |