Stéphane Bessy
email: bessy@lirmm.fr

Marin Bougeret
email: bougeret@lirmm.fr

R Krithika
email: krithika@iitpkd.ac.in

Abhishek Sahu
email: asahu@imsc.res.in

Saket Saurabh

Jocelyn Thiebaut
email: thiebaut@lirmm.fr

Meirav Zehavi
email: meiravze@bgu.ac.il

Packing Arc-Disjoint Cycles in Tournaments *

Keywords: 2012 ACM Subject Classification F.2 Analysis of Algorithms and Problem Complexity arc-disjoint cycle packing, tournaments, parameterized algorithms, kernelization disjoint cycle packing, tournaments, parameterized algorithms, kernelization .CVIT.2016.23

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 2 O(k log k) n O(1) time and 2 O(k) n O(1) time respectively. Moreover, they both admit a kernel with O(k) vertices. We also prove that ACT and ATT cannot be solved in 2 O( √ k) n O(1) time under the Exponential-Time Hypothesis.

Introduction

Given a (directed or undirected) graph G and a positive integer k, the Disjoint Cycle Packing problem is to determine whether G has k (vertex or arc/edge) disjoint (directed or undirected) cycles. Packing disjoint cycles is a fundamental problem in Graph Theory and Algorithm Design with applications in several areas. Since the publication of the classic Erdős-Pósa theorem in 1965 [22], this problem has received significant scientific attention in various algorithmic realms. In particular, Vertex-Disjoint Cycle Packing in undirected graphs is one of the first problems studied in the framework of parameterized complexity.

In this framework, each problem instance is associated with a non-negative integer k called parameter, and a problem is said to be fixed-parameter tractable (FPT) if it can be solved in 1) time for some computable function f , where n is the input size. For convenience, the running time f (k)n O (1) is denoted as O (f (k)). A kernelization algorithm is a polynomialtime algorithm that transforms an arbitrary instance of the problem to an equivalent instance of the same problem whose size is bounded by some computable function g of the parameter of the original instance. The resulting instance is called a kernel and if g is a polynomial function, then it is called a polynomial kernel. A decidable parameterized problem is FPT if and only if it has a kernel (not necessarily of polynomial size). Kernelization typically involves applying a set reduction rules to the given instance to produce another instance.

f (k)n O(
A reduction rule is said to be safe if it is sound and complete, i.e., applying it to the given instance produces an equivalent instance. In order to classify parameterized problems as being FPT or not, the W-hierarchy is defined:

FPT ⊆ W[1] ⊆ W[2] ⊆ . . . ⊆ XP.
It is believed that the subset relations in this sequence are all strict, and a parameterized problem that is hard for some complexity class above FPT in this hierarchy is said to be fixed-parameter intractable. Further details on parameterized algorithms can be found in [17,20,25,27].

Vertex-Disjoint Cycle Packing in undirected graphs is FPT with respect to the solution size k [11,38] but has no polynomial kernel unless NP ⊆ coNP/poly [12]. In contrast,

Edge-Disjoint Cycle Packing in undirected graphs admits a kernel with O(k log k) vertices (and is therefore FPT) [12]. On directed graphs, these problems have many practical applications (for example in biology [13,19]) and they have been extensively studied [7,36].

It turns out that Vertex-Disjoint Cycle Packing and Arc-Disjoint Cycle Packing are equivalent and are W [1]-hard [35,43]. Therefore, studying these problems on a subclass of directed graphs is a natural direction of research. Tournaments form a mathematically rich subclass of directed graphs with interesting structural and algorithmic properties [6,40].

Tournaments have several applications in modeling round-robin tournaments and in the study of voting systems and social choice theory [30,32].

Feedback Vertex Set and Feedback Arc Set are two well-explored algorithmic problems on tournaments. A feedback vertex (arc) set is a set of vertices (arcs) whose deletion results in an acyclic graph. Given a tournament, MinFAST and MinFVST are the problems of obtaining a feedback arc set and feedback vertex set of minimum size, respectively. We refer to the corresponding decision version of the problems as FAST and FVST. The optimization problems MinFAST and MinFVST have numerous practical applications in the areas of voting theory [18], machine learning [16], search engine ranking [21] and have been intensively studied in various algorithmic areas. MinFAST and MinFVST are NP-hard [3,14] while FAST and FVST are FPT when parameterized by the solution size k [4,24,26,32]. Further, FAST has a kernel with O(k) vertices [10] and FVST has a kernel with O(k 1.5 ) vertices S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi 23:3 [37]. Surprisingly, the duals (in the linear programming sense) of MinFAST and MinFVST have not been considered in the literature until recently. Any tournament that has a cycle also has a triangle [7]. Therefore, if a tournament has k vertex-disjoint cycles, then it also has k vertex-disjoint triangles. Thus, Vertex-Disjoint Cycle Packing in tournaments is just packing vertex-disjoint triangles. This problem is NP-hard [8]. A straightforward application of the colour coding technique [5] shows that this problem is FPT and a kernel with O(k 2 ) vertices is an immediate consequence of the quadratic element kernel known for 3-Set Packing [1]. Recently, a kernel with O(k 1.5 ) vertices was shown for this problem using interesting variants and generalizations of the popular expansion lemma [37].

A tournament that has k arc-disjoint cycles need not necessarily have k arc-disjoint triangles. This observation hints that packing arc-disjoint cycles could be significantly harder than packing vertex-disjoint cycles. It also hints that packing arc-disjoint cycles and arc-disjoint triangles in tournaments could be problems of different complexities. This is the starting point of our study. Subsequently, we refer to a set of pairwise arc-disjoint cycles as a cycle packing and a set of pairwise arc-disjoint triangles as a triangle packing.

Given a tournament, MaxACT and MaxATT are the problems of obtaining a maximum set of arc-disjoint cycles and triangles, respectively. We refer to the corresponding decision version of the problems as ACT and ATT. Formally, given a tournament T and a positive integer k, ACT (resp. ATT) is the task of determining if T has k arc-disjoint cycles (resp.

triangles). From a structural point of view, the problem of partitioning the arc set of a directed graph into a collection of triangles has been studied for regular tournaments [45],

almost regular tournaments [2] and complete digraphs [29]. In this work, we study the classical complexity of MaxACT and MaxATT and the parameterized complexity of ACT and ATT with respect to the solution size (i.e. the number k of cycles/triangles) as parameter.

Our main contributions:

We prove that MaxATT and MaxACT are NP-hard (Theorems 4 and 6). As a consequence, we also show that ACT and ATT do not admit algorithms with

O (2 o( √ k) )
running time under the Exponential-Time Hypothesis (Theorem 9). Moreover, deciding if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete (Theorem 8).

A tournament T has k arc-disjoint cycles if and only if T has k arc-disjoint cycles each of length at most 2k + 1 (Theorem 10).

ACT can be solved in O (2 O(k log k) ) time (Theorem 16) and admits a kernel with O(k) vertices (Theorem 15).

ATT can be solved in O (2 O(k) ) time and admits a kernel with O(k) vertices (Theorem 17).

Preliminaries

We denote the set {1, 2, . . . , n} of consecutive integers from 1 to n by

v i v j ∈ A(D), i < j holds.
Given an ordering σ and two vertices u and v, we write

u < σ v if u is before v in σ.
Tournaments. A tournament T is a digraph in which for every pair u, v of distinct vertices either uv ∈ A(T ) or vu ∈ A(T ) but not both. In other words, a tournament T on n vertices is an orientation of the complete graph K n . A tournament T can alternatively be defined by an ordering σ(T ) = (v 1 , . . . , v n ) of its vertices and a set of backward arcs A σ (T ) (which will be denoted A(T ) as the considered ordering is not ambiguous), where each arc

a ∈ A(T ) is of the form v i1 v i2 with i 2 < i 1 .
Indeed, given σ(T ) and A(T ), we define V (T ) =

{v i : i ∈ [n]} and A(T ) = A(T )∪A(T ) where A(T ) = {v i1 v i2 : (i 1 < i 2 ) and v i2 v i1 / ∈ A(T )}
V (T ) = V (T 2 ) ∪ V (T 2 ), σ(T ) = σ(T 1 )σ(T 2 ) is
the concatenation of the two sequences, and

A(T ) = A(T 1 ) ∪ A(T 2 ).

NP-hardness of MaxACT and MaxATT

This section contains our main results. We prove the NP-hardness of MaxATT using a reduction from 3-SAT(3). Recall that 3-SAT(3) corresponds to the specific case of 3-SAT

where each clause has at most three literals, and each literal appears at most two times positively and exactly one time negatively. In the following, denote by F the input formula of an instance of 3-SAT(3). Let n be the number of its variables and m be the number of its clauses. We may suppose that n ≡ 3 (mod 6). If it is not the case, we can add up to 5 unused variables x with the trivial clause x ∨ x. This operation guarantees us we keep the hypotheses of 3-SAT (3). We can also assume that m + 1 ≡ 3 (mod 6). Indeed, if it not the case, we add 6 new unused variables x 1 , . . . , x 6 with the 6 trivial clauses x i ∨ x i , and the clause x 1 ∨ x 2 . This padding process keep both the 3-SAT(3) structure and n ≡ 3 (mod 6).

From F we construct a tournament T which is the concatenation of two tournaments T v and T c defined below.

In the following, let f be the reduction that maps an instance F of 3-SAT(3) to a tournament T we describe now.

The variable tournament T v . For each variable v i of F , we define a tournament V i of order 6 as follows: 1 is a representation of one variable gadget V i . One can notice that the minimum FAS of V i corresponds exactly to the set of its backward arcs. We now define V (T v ) be the union of the vertex sets of the V i s and we equip T v with the order σ 1 σ 2 . . . σ n . Thus, T v has 6n vertices. We also add the following backward arcs to T v . Since n ≡ 3 (mod 6), there is an S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi 23:5

σ i (V i ) = (r i , xi , x 1 i , s i , x 2 i , t i ) and A σ (V i ) = {s i r i , t i x 1 i }. Figure
r i xi x 1 i s i x 2 i t i
Figure 1 The variable gadget Vi. Only backward arcs are depicted, so all the remaining arcs are forward arcs.

edge-disjoint (undirected) triangle packing of K n covering all its edges with triangles that can be computed in polynomial time [33]. Let {u 1 , . . . , u n } be an arbitrary enumeration of the vertices of K n . Using a perfect triangle packing ∆ Kn of K n , we create a tournament

T Kn such that σ (T Kn ) = (u 1 , . . . , u n ) and A σ (T Kn ) = {u k u i : (u i , u j , u k ) is a triangle of ∆ Kn with i < j < k}. Now we set A σ (T v ) = {xy : x ∈ V (V i ), y ∈ V (V j ) for i = j and u j u i ∈ A σ (T Kn )} ∪ n i=1 A σ (V i ).
In some way, we "blew up" every vertex u i of T Kn into our variable gadget V i .

The clause tournament T c . For each of the m clauses c j of F , we define a tournament C j of order 3 as follows: σ(C j ) = (c 1 j , c 2 j , c 3 j ) and A σ (C j ) = ∅. In addition, we have a (m + 1) th tournament denoted by C m+1 and defined by σ

(C m+1 ) = (c 1 m+1 , c 2 m+1 , c 3 m+1 ) and A σ (C m+1 ) = {c 3 m+1 c 1 m+1 }, that is C m+1 is a triangle.
We call this triangle the dummy triangle , and its vertices the dummy vertices. We now define T c such that Now, we move on to proving the correctness of the reduction. First of all, observe that in each variable gadget V i , there are only four triangles: let δ 1 i , δ 2 i , δ 3 i and δ 4 i be the triangles

σ(T c ) is the concatenation of each ordering σ(C j ) in the natural order, that is σ(T c ) = (c 1 1 , c 2 1 , c 3 1 , . . . , c 1 m , c 2 m , c 3 m , c 1 m+1 , c 2 m+1 , c 3 m+1 ). So
(r i , xi , s i ), (r i , x 1 i , s i ), (x 1 i , s i , t i ) and (x 1 i , x 2 i , t i )
, respectively. Moreover, notice that there are only three maximal triangle packings of V i which are {δ 1 i , δ 3 i }, {δ 1 i , δ 4 i } and {δ 2 i , δ 4 i }. We call these packings ∆ i , ∆ i and ∆ ⊥ i , respectively.

Given a triangle packing ∆ of T and a subset X of vertices, we define for any x ∈ X C V I T 2 0 1 6

23:6

Packing Arc-Disjoint Cycles in Tournaments the ∆-local out-degree of the vertex x, denoted d + X\∆ (x), as the remaining out-degree of x in T [X] when we remove the arcs of the triangles of ∆. More formally, we set:

r 1 x1 x 1 1 s 1 x 2 1 t 1 r 2 x2 x 1 2 s 2 x 2 2 t 2 r 3 x3 x 1 3 s 3 x 2 3 t 3 c 1 1 c 2 1 c 3 1 c 1 2 c 2 2 c 3 2 c 1 3 c 2 3 c 3 3
d + X\∆ (x) = |{xa: a ∈ X, xa ∈ A[X], xa / ∈ A(∆)}|.
Remark. Given a variable gadget V i , we have:

(i) d + Vi\∆ i (x 1 i ) = d + Vi\∆ i (x 2 i ) = 1 and d + Vi\∆ i (x i ) = 3, (ii) d + Vi\∆ i (x 1 i ) = 1, d + Vi\∆ i (x 2 i ) = 0 and d + Vi\∆ i (x i ) = 3, (iii) d + Vi\∆ ⊥ i (x 1 i ) = d + Vi\∆ ⊥ i (x 2 i ) = 0 and d + Vi\∆ ⊥ i (x i ) = 4, (iv) none of xi x 1 i , xi x 2 i , xi t i belongs to ∆ i or ∆ ⊥ i .
Informally, we want to set the variable x i to true (resp. false) when one of the locallyoptimal ∆ i or ∆ i (resp. ∆ ⊥ i ) is taken in the variable gadget V i in the global solution. Now given a triangle packing ∆ of T , we partition ∆ into the following sets:

∆ V,V,V = {(a, b, c) ∈ ∆ : a ∈ V i , b ∈ V j , c ∈ V k with i < j < k}, ∆ V,V,C = {(a, b, c) ∈ ∆ : a ∈ V i , b ∈ V j , c ∈ C k with i < j}, ∆ V,C,C = {(a, b, c) ∈ ∆ : a ∈ V i , b ∈ C j , c ∈ C k with j < k}, ∆ C,C,C = {(a, b, c) ∈ ∆ : a ∈ C i , b ∈ C j , c ∈ C k with i < j < k}, ∆ 2V,C = {(a, b, c) ∈ ∆ : a, b ∈ V i , c ∈ C j }, ∆ V,2C = {(a, b, c) ∈ ∆ : a ∈ V i , b, c ∈ C j }, ∆ 3V = {(a, b, c) ∈ ∆ : a, b, c ∈ V i }, ∆ 3C = {(a, b, c) ∈ ∆ : a, b, c ∈ C i }.
Notice that in T , there is no triangle with two vertices in a variable gadget V i and its third vertex in a variable gadget V j with i = j since all the arcs between two variable gadgets are oriented in the same direction. We have the same observation for clauses.

In the two next lemmas, we prove some properties concerning the solution ∆, which imply the result of Lemma Since every triangle of T Kn becomes a K 6,6,6 in T v , we can find a triangle packing ∆ v which use all the arcs between disjoint variable gadgets. We use the same reasoning to prove that there exists a triangle packing ∆ c which use all the arcs available in T c between two distinct clause gadget.

Lemma 2. For any triangle packing ∆ of the tournament T , we have:

(i) |∆ V,V,V |+|∆ C,C,C |≤ 6n(n -1) + 3m(m + 1)/2, (ii) |∆ 2V,C |+|∆ V,2C |+|∆ V,C,C |+|∆ V,V,C |≤ |A vc (T )|, (iii) |∆ 3V |≤ 2n, (iv) |∆ 3C |≤ 1.
Therefore in total we have |∆|≤ 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1.

Proof. Let ∆ be a triangle packing of T . Recall that we have: As 3-SAT(3) is NP-hard [41,44], this implies the following theorem.

|∆|= |∆ V,V,V |+ |∆ V,V,C |+ |∆ V,C,C |+ |∆ C,C,C |+ |∆ 2V,C |+ |∆ V,2C
Theorem 4. MaxATT is NP-hard.

As mentioned in the introduction, packing arc-disjoint cycles is not necessarily equivalent to packing arc-disjoint triangles. Thus, we need to establish the following lemma to transfer the previous NP-hardness result to MaxACT. Finally, the size s of the required packing in Lemma 3 satisfies s = O((n + m) 2 ). Under the Exponential-time Hypothesis, the problem 3-SAT cannot be solved in 2 o(n+m) [17,31].

Then, using the linear reduction from 3-SAT to 3-SAT(3) [44], we also get the following result.

Theorem 9. Under the Exponential-time Hypothesis, ATT and ACT cannot be solved in

O (2 o( √ k) ) time.
In the framework of parameterizing above guaranteed values [39], the above results imply that ACT parameterized below the guaranteed value of the size of a minimal feedback arc set is fixed-parameter intractable.

Parameterized Complexity of ACT

The classical Erdős-Pósa theorem for cycles in undirected graphs states that for each nonnegative integer k, every undirected graph either contains k vertex-disjoint cycles or has a feedback vertex set consisting of f (k) = O(k log k) vertices [22]. An interesting consequence of this theorem is that it leads to an FPT algorithm for Vertex-Disjoint Cycle Packing

(see [38] for more details).

Analogous to these results, we prove an Erdős-Pósa type theorem for tournaments and show that it leads to an O (2 O(k log k) ) time algorithm and a linear vertex kernel for ACT.

First we obtain the following result.

either v i v j ∈ A(T ) or v j v i ∈ A(T ).
In any case, the arc e between v i and v j along with A(C) forms a cycle C of length less than with A(C ) \ {e} ⊂ A(C). By our choice of C, this implies that e is an arc in some other cycle C ∈ C. This property is true for the arc between any pair of non-consecutive vertices in C. Therefore, we have 2 -≤ (k -1) leading to

≤ 2k + 1.
This result essentially shows that it suffices to determine the existence of k arc-disjoint cycles in T each of length at most 2k + 1 in order to determine if (T, k) is an yes-instance of ACT. This immediately leads to a quadratic Erdős-Pósa bound. That is, for every non-negative integer k, every tournament T either contains k arc-disjoint cycles or has an FAS of size O(k 2 ). Next, we strengthen this result to arrive at a linear bound.

We will use the following lemma known from [15] in order to prove Theorem

D -F ) -F is acyclic. Thus F * = F ∪ F is an FAS of T satisfying |F * |≤ 5(k -1).
Next, we show how to obtain a linear kernel for ACT. This kernel is inspired by the linear kernelization described in [10] for FAST and uses Theorem 12. Let T be a tournament on n vertices. First, we apply the following reduction rule.

Reduction Rule 4.1. If a vertex v is in no cycle, then delete v from T .
This rule is clearly safe as our goal is to find k cycles and v cannot be in any of them.

To describe our next rule, we need to state a lemma known from [10]. An interval is a consecutive set of vertices in a linear representation (σ(T ), A(T )) of a tournament T . Our reduction rule that is based on this lemma is as follows. given a digraph D on n vertices and k ordered pairs (s 1 , t 1 ), . . . , (s k , t k ) of vertices of D, do there exist arc-disjoint paths P 1 , . . . , P k in D such that P i is a path from s i to t i for each i ∈ [k]? On directed acyclic graphs, Arc-Disjoint Paths is known to be NP-complete [23], W [1]-hard [43] with respect to k as parameter and solvable in n O(k) time [START_REF] Feige | Faster FAST(Feedback Arc Set in Tournaments)[END_REF]. Despite its fixed-parameter intractability, we will show that we can use the n O(k) algorithm and

Lemma 13 ([10]). Let T = (σ(T ), A(T )) be a tournament on which

Reduction Rule 4.2. Let T = (σ(T ), A(T )) be a tournament on which Reduction Rule

vertices. Suppose T has a set C = {C 1 , . . . , C k } of k arc-disjoint cycles. For each C ∈ C, we know that A(C) ∩ F = ∅ as F is an FAS of T . We can guess that subset F of F such that F = F ∩ A(C).
Then, for each cycle C i ∈ C, we can guess the arcs F i from F that it contains and also the order π i in which they appear. This information is captured as a partition F of

F into k sets, F 1 to F k and the set {π 1 , . . . , π k } of permutations where π i is a permutation of F i for each i ∈ [ k]. Any cycle C i that has F i ⊆ F contains a (v, x)-path between every pair (u, v), (x, y) of consecutive arcs of F i with arcs from A(D). That is, there is a path from h(π -1 i (j)) and t(π -1 i ((j + 1) mod |F i |)) with arcs from D for each j ∈ [|F i |].

23:11

The number of choices for F is 2 | F | and the number of choices for a partition

F = {F 1 , . . . , F k } of F and a set X = {π 1 , . . . , π k } of permutations is 2 O(| F |log| F |) .
Once such a choice is made, the problem of finding k arc-disjoint cycles in T reduces to the problem of

finding k arc-disjoint cycles C = {C 1 , . . . , C k } in T such that for each 1 ≤ i ≤ k and for each 1 ≤ j ≤ |F i |, C i has a path P ij between h(π -1 i (j)) and t(π -1 i ((j + 1) mod |F i |))

Parameterized Complexity of ATT

It is easy to obtain an O (2 O(k) ) time algorithm using the classical colour coding technique [5] for packing subgraphs of bounded size, and in particular for ATT. Moreover, using matching techniques, we also provide a kernel with a linear number of vertices.

In this section, we provide an FPT algorithm and a linear vertex kernel for ATT. First, it is easy to obtain an O (2 O(k) ) time algorithm using the classical colour coding technique [5] for packing subgraphs of bounded size. Next, we show that ATT has a linear vertex kernel.

Theorem 18. ATT admits a kernel with O(k) vertices.

Proof. Let X be a maximal collection of arc-disjoint triangles of a tournament T obtained greedily. Let V X denote the vertices of the triangles in X and A X denote the arcs of V X .

Let U be the remaining vertices of

V (T ), i.e., U = V (T ) \ V X . If |X |≥ k, then (T, k) is an yes-instance of ATT. Otherwise, |X |< k and |V X |< 3k. Moreover, notice that T [U ] is acyclic
and T does not contain a triangle with one vertex in V X and two in vertices in U (otherwise X would not be maximal).

Let B be the (undirected) bipartite graph defined by

V (B) = A X ∪ U and E(B) = {au: a ∈ A X , u ∈ U such that (t(a)
F . If U [F ] ⊆ U then (V X ∪ U , k)
is immediately a kernel. Suppose there exists a vertex x 0 such that

x 0 ∈ U [F ] ∩ U .
We will build a tree rooted in x 0 with edges alternating between F and M . For this let H 0 = {x 0 } and construct recursively the sets H i+1 such that

H i+1 = N F (H i ) if i is even, N M (H i ) if i is odd, where, given a subset S ⊆ U , N F (S) = {a ∈ A X : ∃s ∈ S s.t. (t(a), h(a), s) ∈ F and as / ∈ M } and given a subset S ⊆ A X , N M (S) = {u ∈ U : ∃a ∈ A X s.t. au ∈ M }. Notice that H i ⊆ U
when i is even and that H i ⊆ A X when i is odd, and that all the H i are distinct as F is a union of disjoint stars and M a matching in B. Moreover, for i ≥ 1 we call T i the set of edges between H i and H i-1 . Now we define the tree T such that V (T ) = i H i and E(T

) = i T i .
As T i is a matching (if i is even) or a union of vertex-disjoint stars with centres in

H i-1 (if i is odd), it is clear that T is a tree.
For i being odd, every vertex of H i is incident to an edge of M otherwise B would contain an augmenting path for M , a contradiction. So every leaf of T is in U and incident to an edge of M in T and T contains as many edges of M than edges of F . Now for every arc

a ∈ A X ∩ V (T )

Concluding Remarks

In this work, we studied the classical and parameterized complexity of packing arc-disjoint cycles and triangles in tournaments. We showed NP-hardness, fixed-parameter tractability and linear kernelization results. An interesting problem could be to find subclasses of tournaments where these problems are polynomial-time solvable. For instance, we show in the full version of the paper that it is the case for sparse tournaments, that is for tournaments which admit an FAS that is a matching. This class of tournaments is worthy of attention for these packing problems as packing vertex-disjoint triangles (and hence cycles) 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 and admits a polynomial kernel when parameterized by k. In particular, we show that ACT has a kernel with O(k) vertices and can be solved in 2 O(k log k) n O(1) time.

in
Then, we show that ATT too has a kernel with O(k) vertices and can be solved in 2

O(k) n 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 In this framework, each problem instance is associated with a non-negative integer k called parameter, and a problem is said to be fixed-parameter tractable (FPT) if it can be solved in 1) time for some computable function f , where n is the input size. For convenience, the running time f (k)n O (1) where f grows super-polynomially with k is denoted as O (f (k)).

f (k)n O(
A kernelization algorithm is a polynomial-time algorithm that transforms an arbitrary instance of the problem to an equivalent instance of the same problem whose size is bounded by some computable function g of the parameter of the original instance. The resulting instance is called a kernel and if g is a polynomial function, then it is called a polynomial kernel and we say that the problem admits a polynomial kernel. A decidable parameterized problem is FPT if and only if it has a kernel (not necessarily of polynomial size). Kernelization typically involves applying a set of rules (called reduction rules) to the given instance to produce another instance. A reduction rule is said to be safe if it is sound and complete, i.e., applying it to the given instance produces an equivalent instance. In order to classify parameterized problems as being FPT or not, the W-hierarchy is defined:

FPT ⊆ W[1] ⊆ W[2] ⊆ . . . ⊆ XP.
It is believed that the subset relations in this sequence are all strict, and a parameterized problem that is hard for some complexity class above FPT in this hierarchy is said to be fixed-parameter intractable. As mentioned before, the set of parameterized problems that admit a polynomial kernel is contained in the class FPT and it is believed that this subset relation is also strict. Further details on parameterized algorithms can be found in [21,24,29,31].

Vertex-Disjoint Cycle Packing in undirected graphs is FPT with respect to the solution size k [12,43] but has no polynomial kernel unless NP ⊆ coNP/poly [13]. In contrast,

Edge-Disjoint Cycle Packing in undirected graphs admits a kernel with O(k log k) vertices (and is therefore FPT) [13]. On directed graphs, these problems have many practical applications (for example in biology [14,23]) and they have been extensively studied [7,40,44].

It turns out that Vertex-Disjoint Cycle Packing and Arc-Disjoint Cycle Packing are equivalent and are W[1]-hard [39,[START_REF] Slivkins | Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs[END_REF]. Therefore, studying these problems on a subclass of directed graphs is a natural direction of research. Tournaments form a mathematically rich subclass of directed graphs with interesting structural and algorithmic properties [6,[START_REF] Moon | Topics on Tournaments[END_REF].

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Tournaments have several applications in modeling round-robin tournaments and in the study of voting systems and social choice theory [34,36,42]. Further, the combinatorics of inclusion relations of tournaments is reasonably well-understood [16]. A seminal result in the theory of undirected graphs is the Graph Minor Theorem (also known as the Robertson and Seymour theorem) that states that undirected graphs are well-quasi-ordered under the minor relation [START_REF] Robertson | Graph Minors. XX. Wagner's Conjecture[END_REF]. Developing a similar theory of inclusion relations of directed graphs has been a long-standing research challenge. However, there is such a result known for tournaments that states that tournaments are well-quasi-ordered under the strong immersion relation [16]. This is another reason why tournaments is one of the most well-studied classes of directed graphs. In fact, this result on containment theory also holds for a superclass of tournaments, namely, semicomplete digraphs [8]. A semicomplete digraph is a directed graph in which there is at least one arc between every pair of distinct vertices. Many results

(including some of the ones described in this work) for tournaments straightaway hold for semicomplete digraphs too.

Feedback Vertex Set and Feedback Arc Set are two well-explored algorithmic problems on tournaments. A feedback vertex (arc) set is a set of vertices (arcs) whose deletion results in an acyclic graph. Given a tournament, MinFAST and MinFVST are the problems of obtaining a feedback arc set and feedback vertex set of minimum size, respectively.

We refer to the corresponding decision version of the problems as FAST and FVST. The optimization problems MinFAST and MinFVST have numerous practical applications in the areas of voting theory [22,42], machine learning [18], search engine ranking [25] and have been intensively studied in various algorithmic areas. MinFAST and MinFVST are NP-hard [3,15,19,[START_REF] Speckenmeyer | On Feedback Problems in Digraphs[END_REF] while FAST and FVST are FPT when parameterized by the solution size k [4,[START_REF] Feige | Faster FAST(Feedback Arc Set in Tournaments)[END_REF]30,36,[START_REF] Raman | Parameterized Algorithms for Feedback Set problems and their Duals in Tournaments[END_REF]. Further, FAST has a kernel with O(k) vertices [11] and FVST has a kernel with O(k 1.5 ) vertices [41]. Surprisingly, the duals (in the linear programming sense) of MinFAST and MinFVST have not been considered in the literature until recently.

Any tournament that has a cycle also has a triangle [7]. Therefore, if a tournament has k vertex-disjoint cycles, then it also has k vertex-disjoint triangles. Thus, Vertex-Disjoint Cycle Packing in tournaments is just packing vertex-disjoint triangles. This problem is NP-hard [9]. A straightforward application of the colour coding technique [5] shows that this problem is FPT and a kernel with O(k 2 ) vertices is an immediate consequence of the quadratic element kernel known for 3-Set Packing [1]. Recently, a kernel with O(k 1.5 ) vertices was shown for this problem using interesting variants and generalizations of the popular expansion lemma [41].

It is easy to verify that a tournament that has k arc-disjoint cycles need not necessarily have k arc-disjoint triangles. This observation hints that packing arc-disjoint cycles could be significantly harder than packing vertex-disjoint cycles. Further, it also hints that the problems of packing arc-disjoint cycles and arc-disjoint triangles in tournaments could have different complexities. This is the starting point of our study. that is a matching). This class of tournaments is interesting for cycle packing problems and packing vertex-disjoint triangles (and hence cycles) in sparse tournaments is NP-complete [9].

In particular, we show the following results.

MaxATT Road Map. The paper is organized as follows. In Section 2, we give some definitions related to directed graphs, paths, cycles and tournaments. In Section 3, we show the result on the NP-hardness of the problems considered. In Section 4, we show the parameterized complexity results of ACT. Then, in Section 5, we show the parameterized complexity results of ATT.

Then, we show the polynomial-time solvability of MaxATT and MaxACT restricted to sparse tournaments in Section 6. Finally, we conclude with some remarks in Section 7.

Preliminaries

We denote the set {1, 2, . . . , n} of consecutive integers from 1 to n by [n].

Directed Graphs. A directed graph (or digraph) is a pair consisting of a set V of vertices and a set A of arcs. An arc is specified as an ordered pair of vertices (called its endpoints).

We will consider only simple unweighted digraphs. Tournaments. A tournament T is a digraph in which for every pair u, v of distinct vertices either uv ∈ A(T ) or vu ∈ A(T ) but not both. In other words, a tournament T on n vertices is an orientation of the complete graph K n . A tournament T can alternatively be defined by an ordering σ(T ) = (v 1 , . . . , v n ) of its vertices and a set of backward arcs A σ (T ) (which will be denoted A(T ) as the considered ordering is not ambiguous), where each arc a ∈ A(T ) is of the form v i1 v i2 with i 2 < i 1 . Indeed, given σ(T ) and A(T ), we define of a tournament T , a triangle C in T is a triple (v i1 , v i2 , v i3 ) with i l < i l+1 such that either

Paths and Cycles

. A path P in a digraph D is a sequence (v 1 , . . . , v k ) of distinct vertices such that for each i ∈ [k -1], v i v i+1 ∈ A(D).
i v i+1 : i ∈ [k -1]} ∪ {v k v 1 } is denoted by A(C). A cycle C = (v 1 , . . . , v k ) is called an induced (or chordless) cycle if A(C)
V (T ) = {v i : i ∈ [n]} and A(T ) = A(T ) ∪ A(T ) where A(T ) = {v i1 v i2 : (i 1 < i 2 ) and v i2 v i1 / ∈ A(T )}
v i3 v i1 ∈ A(T ), v i3 v i2 / ∈ A(T ) and v i2 v i1 / ∈ A(T ) (in this case we call C a triangle with backward arc v i3 v i1 ), or v i3 v i1 / ∈ A(T ), v i3 v i2 ∈ A(T ) and v i2 v i1 ∈ A(T ) (in

NP-hardness of MaxACT and MaxATT

This section contains our main results. We prove the NP-hardness of MaxATT using a reduction from 3-SAT(3). Recall that 3-SAT(3) corresponds to the specific case of 3-SAT where each clause has at most three literals, and each literal appears at most two times positively and exactly one time negatively. In the following, denote by F the input formula of an instance of 3-SAT(3). Let n be the number of its variables and m be the number of its clauses. We may suppose that n ≡ 3 (mod 6). If it is not the case, we can add up to 5 unused variables x with the trivial clause x ∨ x. This operation guarantees us we keep the hypotheses of 3-SAT(3). We can also assume that m + 1 ≡ 3 (mod 6). Indeed, if it not the case, we add 6 new unused variables x 1 , . . . , x 6 with the 6 trivial clauses x i ∨ x i , and the clause x 1 ∨ x 2 . This padding process keep both the 3-SAT(3) structure and n ≡ 3 (mod 6).

From F we construct a tournament T which is the concatenation of two tournaments T v and T c defined below.

C V I T 2 0 1 6

23:6

Packing Arc-Disjoint Cycles in Tournaments

r i xi x 1 i s i x 2 i t i
Figure 1 The variable gadget Vi. Only backward arcs are depicted, so all the remaining arcs are forward arcs.

In the following, let f be the reduction that maps an instance F of 3-SAT(3) to a tournament T we describe now.

The variable tournament T v . For each variable v i of F , we define a tournament V i of order 6 as follows: 1 is a representation of one variable gadget V i . One can notice that the minimum FAS of V i corresponds exactly to the set of its backward arcs. We now define V (T v ) be the union of the vertex sets of the V i s and we equip T v with the order σ 1 σ 2 . . . σ n . Thus, T v has 6n vertices. We also add the following backward arcs to T v . Since n ≡ 3 (mod 6), there is an edge-disjoint (undirected) triangle packing of K n covering all its edges with triangles that can be computed in polynomial time [37]. Let {u 1 , . . . , u n } be an arbitrary enumeration of the vertices of K n . Using a perfect triangle packing ∆ Kn of K n , we create a tournament

σ i (V i ) = (r i , xi , x 1 i , s i , x 2 i , t i ) and A σ (V i ) = {s i r i , t i x 1 i }. Figure
T Kn such that σ (T Kn ) = (u 1 , . . . , u n ) and A σ (T Kn ) = {u k u i : (u i , u j , u k ) is a triangle of ∆ Kn with i < j < k}. Now we set A σ (T v ) = {xy : x ∈ V (V i ), y ∈ V (V j ) for i = j and u j u i ∈ A σ (T Kn )} ∪ n i=1 A σ (V i ).
In some way, we "blew up" every vertex u i of T Kn into our variable gadget V i .

The clause tournament T c . For each of the m clauses c j of F , we define a tournament C j of order 3 as follows: σ(C j ) = (c 1 j , c 2 j , c 3 j ) and A σ (C j ) = ∅. In addition, we have a (m + 1) th tournament denoted by C m+1 and defined by σ(C m+1 ) = (c 1 m+1 , c 2 m+1 , c 3 m+1 ) and A σ (C m+1 ) = {c 3 m+1 c 1 m+1 }, that is C m+1 is a triangle. We call this triangle the dummy triangle , and its vertices the dummy vertices. We now define T c such that σ(T c ) is the concatenation of each ordering σ(C j ) in the natural order, that is

σ(T c ) = (c 1 1 , c 2 1 , c 3 1 , . . . , c 1 m , c 2 m , c 3 m , c 1 m+1 , c 2 m+1 , c 3 m+1 ).
So T c has 3(m + 1) vertices. Since m + 1 ≡ 3 (mod 6), we use the same trick as above to add arcs to A σ (T c ) coming from a perfect packing of undirected triangles of K m+1 . Once again, we "blew up" every vertex u j of T Km+1 into our clause gadget C j .

The tournament

(T ) = A σ (T v ) ∪ A σ (T c ) ∪ A vc (T ).
Notice that each xi has exactly four arcs a ∈ A σ (T ) such that h(a) = xi and t(a) is a vertex of T c . To finish the construction, notice also that T has 6n+3(m+1) vertices and can be computed in polynomial time. Figure 2 is an example of the tournament obtained from a trivial 3-SAT(3) instance.

r 1 x1 x 1 1 s 1 x 2 1 t 1 r 2 x2 x 1 2 s 2 x 2 2 t 2 r 3 x3 x 1 3 s 3 x 2 3 t 3 c 1 1 c 2 1 c 3 1 c 1 2 c 2 2 c 3 2 c 1 3 c 2 3 c 3 3
Now, we move on to proving the correctness of the reduction. First of all, observe that in each variable gadget V i , there are only four triangles: let δ 1 i , δ 2 i , δ 3 i and δ 4 i be the triangles

(r i , xi , s i ), (r i , x 1 i , s i ), (x 1 i , s i , t i ) and (x 1 i , x 2 i , t i )
, respectively. Moreover, notice that there are only three maximal triangle packings of V i which are

{δ 1 i , δ 3 i }, {δ 1 i , δ 4 i } and {δ 2 i , δ 4 i }. We call these packings ∆ i , ∆ i and ∆ ⊥ i , respectively.
Given a triangle packing ∆ of T and a subset X of vertices, we define for any x ∈ X the ∆-local out-degree of the vertex x, denoted d + X\∆ (x), as the remaining out-degree of x in T [X] when we remove the arcs of the triangles of ∆. More formally, we set:

d + X\∆ (x) = |{xa: a ∈ X, xa ∈ A[X], xa / ∈ A(∆)}|.
Remark. Given a variable gadget V i , we have:

(i) d + Vi\∆ i (x 1 i ) = d + Vi\∆ i (x 2 i ) = 1 and d + Vi\∆ i (x i ) = 3, (ii) d + Vi\∆ i (x 1 i ) = 1, d + Vi\∆ i (x 2 i ) = 0 and d + Vi\∆ i (x i ) = 3, (iii) d + Vi\∆ ⊥ i (x 1 i ) = d + Vi\∆ ⊥ i (x 2 i ) = 0 and d + Vi\∆ ⊥ i (x i ) = 4, (iv) none of xi x 1 i , xi x 2 i , xi t i belongs to ∆ i or ∆ ⊥ i .
Informally, we want to set the variable x i to true (resp. false) when one of the locallyoptimal ∆ i or ∆ i (resp. ∆ ⊥ i ) is taken in the variable gadget V i in the global solution. Now given a triangle packing ∆ of T , we partition ∆ into the following sets:

∆ V,V,V = {(a, b, c) ∈ ∆ : a ∈ V i , b ∈ V j , c ∈ V k with i < j < k}, ∆ V,V,C = {(a, b, c) ∈ ∆ : a ∈ V i , b ∈ V j , c ∈ C k with i < j}, ∆ V,C,C = {(a, b, c) ∈ ∆ : a ∈ V i , b ∈ C j , c ∈ C k with j < k}, ∆ C,C,C = {(a, b, c) ∈ ∆ : a ∈ C i , b ∈ C j , c ∈ C k with i < j < k}, ∆ 2V,C = {(a, b, c) ∈ ∆ : a, b ∈ V i , c ∈ C j }, ∆ V,2C = {(a, b, c) ∈ ∆ : a ∈ V i , b, c ∈ C j }, ∆ 3V = {(a, b, c) ∈ ∆ : a, b, c ∈ V i }, ∆ 3C = {(a, b, c) ∈ ∆ : a, b, c ∈ C i }.
Notice that in T , there is no triangle with two vertices in a variable gadget V i and its third vertex in a variable gadget V j with i = j since all the arcs between two variable gadgets are oriented in the same direction. We have the same observation for clauses.

In the two next lemmas, we prove some properties concerning the solution ∆. Proof. First recall that the tournament T v is constructed from a tournament T Kn which admits a perfect packing of n(n -1)/6 triangles. Then we replaced each vertex u i in T Kn by the variable gadget V i and kept all the arcs between two variable gadgets V i and V j in the same orientation as between u i and u j . Let u i u j u k be a triangle of the perfect packing of T Kn . We temporally relabel the vertices of V i , V j and V k respectively by {f i : i ∈ [6]},

{g i : i ∈ [6]} and {h i : i ∈ [6]
} and consider the tripartite tournament K 6,6,6 given by

V (K 6,6,6 ) = {f i , g i , h i : i ∈ [6]} and A(K 6,6,6 ) = {f i g j , g i h j , h i f j : i, j ∈ [6]}. Then it is easy to check that {(f i , g j , h i+j (mod 6) ): i, j ∈ [6]
} is a perfect triangle packing of K 6,6,6 . Since every triangle of T Kn becomes a K 6,6,6 in T v , we can find a triangle packing ∆ v which use all the arcs between disjoint variable gadgets. We use the same reasoning to prove that there exists a triangle packing ∆ c which use all the arcs available in T c between two distinct clause gadget.

Lemma 2. For any triangle packing ∆ of the tournament T , we have the following inequalities:

(i) |∆ V,V,V |+|∆ C,C,C |≤ 6n(n -1) + 3m(m + 1)/2, (ii) |∆ 2V,C |+|∆ V,2C |+|∆ V,C,C |+|∆ V,V,C |≤ |A vc (T )|, where |A vc (T )|= |A vc (T )|, (iii) |∆ 3V |≤ 2n, (iv) |∆ 3C |≤ 1.
Therefore in total we have |∆|≤ 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1.

Proof. Let ∆ be a triangle packing of T . Recall that we have: Proof. First, let suppose that there exists an assignment a of the variables which satisfies F , and let a (resp. a ⊥ ) be the set of variables set to true (resp. false).

|∆|= |∆ V,V,V |+ |∆ V,V,C |+ |∆ V,C,C |+ |∆ C,C,C |+ |∆ 2V,C |+ |∆ V,2C |+ |∆ 3V |+ |∆ 3C |.
We construct a triangle packing ∆ of T with the desired number of triangles. First, we pick all the disjoint triangles of ∆ v and ∆ c . By Lemma 2, if we also add the dummy triangle

(c 1 m+1 , c 2 m+1 , c 3 m+1 ) we have 6n(n -1) + 3m(m + 1)/2 + 1 triangles in ∆ until now.
Then, for any variable v i of the formula F , if v i ∈ a , then we add in ∆ the triangles ∆ i . Otherwise, we add ∆ ⊥ i . One can check that in both cases, these triangles are disjoint to the triangles we just added. Thus, in each V i , we made an locally-optimal solution, so we added 2n triangles in ∆. Now we add in ∆ the triangles (x i , t i , c 1 m+1 ), (x i , x 1 i , c 2 m+1 ) and (x i , x 2 i , c 3 m+1 ) which will consume all the dummy arcs of the tournament. Recall that in Remark 3 we mentioned that the vertices x 1 i and x 2 i (resp. xi ) have an ∆ i -local out-degree both equal to 1 (resp.

∆ ⊥ i -local out-degree equals to 4). Then given a clause c j , let be one literal which satisfies c j . Assume that the clause is of size 3, since the reasoning is the same for clauses of size 2. If is a positive literal, say v i , then let u be the number such that c 3 j x u i is a backward arc of T . By Remark 3, we know that there exists v ∈ V i such that the arc x u i v is available to make the triangle (x u i , v, c 3 j ). Otherwise, that is if is a negative literal, say vi , then we have

d + Vi\∆ ⊥ i (x i ) = 4.
Three of these four available arcs are used in the triangles which consume the dummy arcs, then we can still make the triangle (x i , s i , c 3 j ). Let also 1 and 2 be the two other literals of c j (which do not necessarily satisfy c j ). Denote by a 1 and a 2 the vertices of T v connected to c 3 j corresponding to the literals 1 and 2 , respectively. Then we add the two following triangles: (a 1 , c 1 j , c 3 j ) and (a 2 , c 2 j , c 3 j ). So we used all the backward arc from T c to T v , and there are no triangles which use two arcs of A vc (T ). Then in the packing ∆ there are in total 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1 triangles.

Conversely let ∆ be a triangle packing of T with |∆|= 6n(n -1) + 3m(m + 1)/2 + 2n +

|A vc (T )|+1. In the same way as we already did before, we partition ∆ into the different subsets we defined before. We have

|∆|= |∆ V,V,V |+|∆ V,V,C |+|∆ V,C,C |+|∆ C,C,C |+|∆ 2V,C |+|∆ V,2C | +|∆ 3V |+|∆ 3C |.
By Lemma 2 all the upper bounds described above are tight, that is:

|∆ V,V,V |+|∆ C,C,C |= 6n(n -1) + 3m(m + 1)/2, |∆ 2V,C |+|∆ V,2C |+|∆ V,C,C |+|∆ V,V,C |= |A vc (T )|, |∆ 3V |= 2n, |∆ 3C |= 1. Let us first prove that |∆ V,V,C |+|∆ V,C,C |= 0. Let x = |∆ V,V,C |+|∆ V,C,C |. Since each triangle of the sets ∆ V,V,C , ∆ V,C,C , ∆ 2V,C
and ∆ V,2C uses exactly one backward arc of Since |∆ 3V |= 2n and we have at most two arc-disjoint triangles in each variable gadget

A vc (T ), it implies that |∆ 2V,C |+|∆ V,2C |≤ |A vc (T )|-x. Moreover, if x = 0, then we have |∆ V,V,V |< |∆ v | or |∆ C,C,C |< |∆ c | because each triangle in ∆ V,V,C (resp. ∆ V,C,C )
V i , it implies that ∆[V i ] ∈ {∆ ⊥ i , ∆ i , ∆ i }.
In the following, we will simply write ∆ i instead of ∆[V i ]. Let us consider the following assignment a: for any variable v i , if ∆ i = ∆ ⊥ i , then a(v i ) = f alse and a(v i ) = true otherwise. Let us see that the assignment a satisfies the formula F . We have just proved that the backward arcs from T c to T v are all used in ∆ 2V,C and ∆ V,2C . As |∆ 3C |= 1 the dummy triangle C m+1 belongs to ∆. So every dummy arc c u m+1 xi is contained in a triangle of ∆ which uses an arc of V i . Therefore in each V i we have

d + Vi\∆i (x i ) ≥ 3.
Moreover, for each clause of size q with q ∈ {2, 3}, there are q triangles which use the backward arcs coming from the clause to variable gadgets. Let C j be a clause gadget of size 3 (we can do the same reasoning if C j has size 2). By construction the 3 triangles cannot all lie in ∆ V,2C . Thus, there is at least one of these triangles which is in ∆ 2V,C . Let t be one of them, V i be the variable gadget where t has two out of its three vertices and x be the vertex of V i which is also the head of the backward arc from C j to V i . By construction,

x corresponds to a literal in the clause c j . If is positive, then x = x 1 i or x = x 2 i . In both cases, since t has a second vertex in V i , we have d + Vi\∆i (x) > 0. Thus, using Figure 3 we cannot have ∆ i = ∆ ⊥ i so the assignment sets the positive literal to true, which satisfies c j .

Otherwise, is negative so x = xi . Since xi has to use three out-going arcs to consume the dummy arcs and one out-going arc to consume t, we have d + Vi\∆i (x i ) ≥ 4 and so ∆ i = ∆ ⊥ i by Figure 3. Therefore, c j is satisfied in that case too. Thus, the assignment a satisfies the whole formula F .

C V I T 2 0 1 6

23:10 Packing Arc-Disjoint Cycles in Tournaments

As 3-SAT(3) is NP-hard [START_REF] Papadimitriou | Computational Complexity[END_REF][START_REF] Tovey | A simplified NP-complete satisfiability problem[END_REF], this directly implies the following theorem.

Theorem 4. MaxATT is NP-hard.

As mentioned in the introduction, packing arc-disjoint cycles is not necessarily equivalent to packing arc-disjoint triangles. Thus, we need to establish the following lemma to transfer the previous NP-hardness result to MaxACT.

O V = {(v 1 , . . . , v p ) ∈ O: ∃i ∈ [n], ∀k ∈ [p], v k ∈ V i }, O C = {(v 1 , . . . , v p ) ∈ O: ∃j ∈ [m + 1], ∀k ∈ [p], v k ∈ C j }, O V * = {(v 1 , . . . , v p ) ∈ O: ∀k ∈ [p], ∃i ∈ [n], v k ∈ V i and (v 1 , . . . , v p ) / ∈ O V }, O C * = {(v 1 , . . . , v p ) ∈ O: ∀k ∈ [p], ∃j ∈ [m + 1], v k ∈ C j and (v 1 , . . . , v p ) / ∈ O C }, O V * ,C * = {(v 1 , . . . , v p ) ∈ O: ∃i ∈ [n], ∃j ∈ [m + 1], ∃k 1 , k 2 ∈ [p], v k1 ∈ V i , v k2 ∈ C j }.
As we did in the previous proof, we begin by finding upper bounds on each of these sets. First, recall that the FAS of each V i is 2. Thus, we have |O V |≤ 2n. By construction, we also have

|O C |≤ 1.
Secondly, notice that a cycle of O V * cannot belong to exactly two distinct variable gadgets since the arcs between them are all in the same direction. Thus, the cycles of O V * We now prove that given a V i , we can restructure every cycle of O As C m+1 is a triangle, we also get |F Cm+1 |≥ 1.

V [V i ] into triangles. Recall that O V [V i ]
= i . As F is FAS of T , F V V = i,i ∈[n],i =i F ViV i must
For any j ∈ [m], let u j ∈ {2, 3} be equal to the size of the clause j (we also have

u j = |{a ∈ A(T ): ∃i ∈ [n], h(a) ∈ V i and t(a) ∈ C j }|). Let L = {j ∈ [m]: |F * Cj ∪ F Cj |≥ u j }
be informally the set of clauses where F spends a large (in fact larger than the u j required) amount of arcs, and S = [m] \ L. Let us prove that for any j ∈ S, |F Cj |≥ u j -1. Let us first consider the case where u j = 3. Suppose by contradiction than F Cj = {a} (arguments will also hold for F Cj = ∅). Remember that σ(C j ) = (c 1 j , c 2 j , c

Case 2: x = x 1 i .If A xiVi ⊆ F then |F Vi ∪ F ViCm+1 |≥ 6.
Otherwise, as before we get A ViCm+1 ⊆ F , and as A x 1 i Vi is not an FAS of V i , F need another arc in V i , implying

|F Vi ∪ F ViCm+1 |≥ 6. Case 3: x = x 2 i .If A xiVi ⊆ F then as A x 2 i Vi ∪ A xiVi is not an FAS of V i , F need another arc in V i , implying |F Vi |≥ 6.
Otherwise, as before we get A ViCm+1 ⊆ F , and as A x 1 i Vi is not an

FAS of V i , F need two other arcs in V i , implying |F Vi ∪ F ViCm+1 |≥ 6.
Putting all the pieces together, we get the following. ). Next, we strengthen this result to arrive at a linear bound.

We will use the following lemma known from [17] in the process

A Linear Vertex Kernel

Next, we show that ACT has a linear vertex kernel. This kernel is inspired by the linear kernelization described in [11] for FAST and uses Theorem 13. Let T be a tournament on n vertices. First, we apply the following reduction rule.

vertices. Suppose T has a set C = {C 1 , . . . , C k } of k arc-disjoint cycles. For each C ∈ C, we know that A(C) ∩ F = ∅ as F is an FAS of T . We can guess that subset F of F such that F = F ∩ A(C).
Then, for each cycle C i ∈ C, we can guess the arcs F i from F that it contains and also the order π i in which they appear. This information is captured as a partition F of

Parameterized Complexity of ATT

In this section, we provide an FPT algorithm and a linear vertex kernel for ATT. First, it is easy to obtain an O (2 O(k) ) time algorithm using the classical colour coding technique [5] for packing subgraphs of bounded size. Next, we show that ATT has a linear vertex kernel.

Theorem 19. ATT admits a kernel with O(k) vertices.

Proof. Let X be a maximal collection of arc-disjoint triangles of a tournament T obtained greedily. Let V X denote the vertices of the triangles in X and A X denote the arcs of V X .

Let U be the remaining vertices of V (T ), i.e., U =

V (T ) \ V X . If |X |≥ k, then (T, k) is an yes-instance of ATT. Otherwise, |X |< k and |V X |< 3k. Moreover, notice that T [U ] is acyclic
and T does not contain a triangle with one vertex in V X and two in vertices in U (otherwise X would not be maximal).

Let B be the (undirected) bipartite graph defined by

V (B) = A X ∪ U and E(B) = {au: a ∈ A X , u ∈ U such that (t (
. If U [F ] ⊆ U then (V X ∪ U , k) is
immediately a kernel. Suppose there exists a vertex x 0 such that x 0 ∈ U [F ] ∩ U .

We will build a tree rooted in x 0 with edges alternating between F and M . For this let H 0 = {x 0 } and construct recursively the sets H i+1 such that

H i+1 = N F (H i ) if i is even, N M (H i ) if i is odd, where, given a subset S ⊆ U , N F (S) = {a ∈ A X : ∃s ∈ S s.t. (t(a), h(a), s) ∈ F and as / ∈ M } and given a subset S ⊆ A X , N M (S) = {u ∈ U : ∃a ∈ A X s.t. au ∈ M }. Notice that H i ⊆ U
when i is even and that H i ⊆ A X when i is odd, and that all the H i are distinct as F is a union of disjoint stars and M a matching in B. Moreover, for i ≥ 1 we call T i the set of edges between H i and H i-1 . Now we define the tree T such that V (T ) = i H i and E(T ) = i T i .

As T i is a matching (if i is even) or a union of vertex-disjoint stars with centres in H i-1 (if i is odd), it is clear that T is a tree.

For i being odd, every vertex of H i is incident to an edge of M otherwise B would contain an augmenting path for M , a contradiction. So every leaf of T is in U and incident to an

MaxACT and MaxATT in Sparse Tournaments

Recall that a tournament is sparse if it admits an FAS which is a matching. In this section, we show that MaxACT and MaxATT are polynomial-time solvable on sparse tournaments.

Note that packing vertex-disjoint triangles (and hence cycles) in sparse tournaments is NP-complete [9].

Let T be a sparse tournament according to the ordering of its vertices σ(T ), that is the set of its backward arcs A(T ) is a matching. If a backward arc xy of T lies between two consecutive vertices, then we can exchange the position of x and y in σ(T ) to obtain a sparse tournament with fewer backward arc. So we can assume that the backward arcs of T do not contain consecutive vertices. Moreover, if a vertex x of T is contained in no backward arc of T then call A (resp. B) the vertices of T which are before (resp. after) x in σ(T ). Let X 0 be the set of triangles made from a backward arc from B to A and the vertex x. As T is sparse it is clear that X 0 is a set of disjoint triangles. Moreover, it can easily be seen that there exists an optimal packing of triangles (resp. cycles) of T which is the union of an optimal packing of triangles (resp. cycles) of T Moreover, let G be the digraph with vertex set V = {e i : i ∈ [b]} and arc set A defined by: (e i e j ) ∈ A if (h(e i ), h(e j ), t(e i )) or (h(e i ), t(e j ), t(e i )) is a triangle of T . Let Π be the problem such that, given a digraph G = (V , A ), the objective is to find a maximum sized subset of A such that the digraph induced by the arcs of the subset is a functional and digon-free digraph. Remind that a functional digraph is a digraph such that any of its vertices has out-degree at most 1.

Let X be a solution (not necessary optimal) of Π (G ), and e i e j an arc of X. We denote by Π(e i e j ) the triangle (h(e i ), h(e j ), t(e i )) if i < j and otherwise. Given a triangle Π(e i e j ), let s(e j ) be the second vertex of Π(e i e j ); in other words, if Π(e i e j ) = (h(e i ), t(e j ), t(e i )), then s(e j ) = t(e j ) and s(e j ) = h(e j ) otherwise. Informally, Π(e i e j ) corresponds to the triangle formed by the backward arc e i and one vertex of e j , that vertex being s(e j ). In the same way, we define Π(X) = x∈X Π(x).

Claim 19.1. Let X be a solution of Π (G ). The set X is an optimal solution if and only if Π(X) is an optimal solution of Π(T ).

Proof. Let e i e j and e k e l be two distinct arcs of X. We cannot have e i = e k as X induces a functional digraph in G . Without loss of generality, we may assume that i < k, that is that S i is a terminal component of G . So we denote π i by (x 1 , x 2 , . . . , x l ) and notice that x 1 and x 2 are then forced to be the heads of backward arcs belonging to S i . If x 3 is also the head of backward arc of S i , then we obtain that the three corresponding backward arcs form a 3-cycle in G contradicting the fact that S i induces a digoned tree in G . Repeating the same argument we show that l is even and that the backward arcs corresponding to the elements of S i are exactly x 3 x 1 , x l x l-2 and x j x j-3 for all odd j ∈ [l] \ {1, 3}. In other words S i induces a 'digoned path' in G . Now consider ∆ an optimal cycle packing of T . Let X 1 be the set of backward arcs of A(T ) with head strictly before x 1 and tail strictly after x l in σ(T ). And let ∆ 1 be the cycles of ∆ using at least one arc of X 1 . It is easy to check that ∆ = (∆ \ ∆ 1 ) ∪ {(h(e), x 1 , t(e)): e ∈ X 1 } is also an optimal cycle packing of T . Now every cycle of ∆ which uses a backward arc of S i only uses backward arcs of S i (otherwise it must one arc of X 1 , which is not possible). Let ∆ i be the set of cycles of ∆ using backward arcs of S i . It is easy to see that {x This leads to the following main result of this section.

  [n]. Directed Graphs. A directed graph D (or digraph) is a pair consisting of a finite set V (D) of vertices of D and a set A(D) of arcs of D, which are ordered pairs of elements of V (D). For a vertex v ∈ V (D), its out-neighbourhood, denoted by N + (v), is the set {u ∈ V (D): vu ∈ A(D)} and its out-degree, denoted by d + (x), is |N + (v)|. For a set F of arcs, V (F ) denotes the union of the sets of endpoints of arcs in F . Given a digraph D and a subset X of vertices, we denote by D[X] the digraph induced by the vertices in X. Moreover, we denote by D \ X the digraph D[V (D) \ X] and say that this digraph is obtained by deletingX from D. . A path P in a digraph D is a sequence (v 1 , . . . , v k ) of distinct vertices such that for each i ∈ [k -1], v i v i+1 ∈ A(D). The set {v 1 , . . . , v k } is denoted by V (P ) and the set {v i v i+1 : i ∈ [k -1]} is denoted by A(P ). A cycle C in D is a sequence (v 1 , . . . , v k ) of distinct vertices such that (v 1 , . . . , v k ) is a path and v k v 1 ∈ A(D).The length of a path or cycle X is the number of vertices in it. A cycle on three vertices is called a triangle. A digraph is called a directed acyclic graph if it has no cycles. A feedback arc set (FAS) is a set of arcs whose deletion results in an acyclic graph. For a digraph D, let minfas(D) denote the size of a minimum FAS of D. Any directed acyclic graph D has an ordering σ(D) = (v 1 , . . . , v n ) called topological ordering of its vertices such that for each

  is the set of forward arcs of T in the given ordering σ(T ). The pair (σ(T ), A(T )) is called a linear representation of the tournament T . A tournament is called transitive if it is a directed acyclic graph and a transitive tournament has a unique topological ordering. Given two tournaments T 1 , T 2 defined by σ(T l ) and A(T l ) with l ∈ {1, 2}, we denote by T = T 1 T 2 the tournament called the concatenation of T 1 and T 2 , where

3 (

 3 T c has 3(m + 1) vertices. Since m + 1 ≡ mod 6), we use the same trick as above to add arcs to A σ (T c ) coming from a perfect packing of undirected triangles of K m+1 . Once again, we "blew up" every vertex u j of T Km+1 into our clause gadget C j .The tournamentT . To define our final tournament T let us begin with its ordering σ defined by σ(T ) = σ(T v )σ(T c ). Then we construct A vc (T ) the backward arcs between T c and T v . For any j ∈ [m], if the clause c j in F has three literals, that is c j = 1 ∨ 2 ∨ l 3 , then we add to A vc (T ) the three backward arcs c 3 j z u where u ∈ [3] and such that z u = xiu when u = viu , and z u ∈ {x 1 iu , x 2 iu } when u = v iu in such a way that for any i ∈ [n], there exists a unique arc a ∈ A vc (T ) with h(a) = x 1 i . Informally, in the previous definition, if x 1 iu is already "used" by another clause, we chose z u = x 2 iu . Such an orientation will always be possible since each variable occurs at most two times positively and once negatively in F . If the clause c j in F has only two literals, that is c j = 1 ∨ 2 , then we add in A vc (T ) the two backward arcs c 2 j z u where u ∈ [2] and such that z u = xiu when u = viu and z u ∈ {x 1 iu , x 2 iu } when u = v iu in such a way that for any i ∈ [n], there exists a unique arc a ∈ A vc (T ) with h(a) = x 1 i . Finally, we add in A vc (T ) the backward arcs c u m+1 xi for any u ∈ [3] and i ∈ [n]. These arcs are called dummy arcs. We set A σ (T ) = A σ (T v ) ∪ A σ (T c ) ∪ A vc (T ). Notice that each xi has exactly four arcs a ∈ A σ (T ) such that h(a) = xi and t(a) is a vertex of T c . To finish the construction, notice also that T has 6n+3(m+1) vertices and can be computed in polynomial time. Figure 2 is an example of the tournament obtained from a trivial 3-SAT(3) instance.

Figure 2

 2 Figure 2 Example of reduction obtained when F = {c1, c2} where c1 = v1 ∨ v2 ∨ v3 and c2 = v1 ∨ v2 ∨ v3. Forward arcs are not depicted. In addition to the depicted backward arcs, we have the 36 backward arcs from V3 to V1, and the 9 backward arcs from C3 to C1.

Lemma 5 .Theorem 6 .Lemma 7 .Theorem 8 .

 5678 Given a 3-SAT(3) instance F , and T the tournament constructed from F with the reduction f , we have a triangle packing ∆ of T of size 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1 if and only if there is a cycle packing O of the same size.The previous lemma and Theorem 4 imply the following theorem. MaxACT is NP-hard.Let us now define two special cases Tight-ATT (resp. Tight-ACT) where, given a tournament T and a linear ordering σ with k backward arcs, where k = minfas(T ), the goal is to decide if there is a triangle (resp. cycle) packing of size k. We call these special cases the "tight" versions of the classical packing problems because as the input admits an FAS of size k, any triangle (or cycle) packing has size at most k. We have the following result, directly implying the NP-hardness of Tight-ATT and Tight-ACT. Let T be a tournament constructed by the reduction f , and k be the threshold value defined in Lemma 3. Then, we have k = minfas(T ) and we can construct (in polynomial time) an ordering of T with k backward arcs. Tight-ATT and Tight-ACT are NP-hard.

12 1 .Theorem 12 .

 112 For a digraph D, let Λ(D) denote the number of non-adjacent pairs of vertices in D. That is, Λ(D) is the number of pairs u, v of vertices of D such that neither uv ∈ A(D) nor vu ∈ A(D).Lemma 11.[15] Let D be a triangle-free digraph in which for every pair u, v of distinct vertices, at most one of uv or vu is in A(D). Then, we can compute an FAS of size at most Λ(D) in polynomial time. For every non-negative integer k, every tournament T either contains k arc-disjoint triangles or has an FAS of size at most 5(k -1) that can be obtained in polynomial time.Proof. Let C be a maximal set of arc-disjoint triangles in T (that can be obtained greedily in polynomial time). If |C|≥ k, then we have the required set of triangles. Otherwise, let D denote the digraph obtained from T by deleting the arcs that are in some triangle in C. Clearly, D has no triangle and Λ(D) ≤ 3(k -1). Let F be an FAS of D obtained in polynomial time using Lemma 11. Then, we have |F |≤ 3(k -1). Next, consider a topological ordering σ of D -F . Each triangle of C contains at most 2 arcs which are backward in this ordering. If we denote by F the set of all the arcs of the triangles of C which are backward in σ, then we have |F |≤ 2(k -1) and (

  Reduction Rule 4.1 is not applicable. If |V (T )|≥ 2|A(T )|+1, then there exists a partition J of V (T ) into intervals (that can be computed in polynomial time) such that there are |A(T ) ∩ E|> 0 arc-disjoint cycles using only arcs in E where E denotes the set of arcs in T with endpoints in different intervals.

4. 1 Lemma 14 .TTheorem 15 .

 11415 is not applicable. Let J be a partition of V (T ) into intervals satisfying the properties specified inLemma 13. Reverse all arcs in A(T ) ∩ E and decrease k by |A(T ) ∩ E| where E denotes the set of arcs in T with endpoints in different intervals. Reduction Rule 4.2 is safe.Proof. Let T be the tournament obtained from T by reversing all arcs in A(T ) ∩ E. Suppose T has k -|A(T ) ∩ E| arc-disjoint cycles. Then, it is guaranteed that each such cycle is completely contained in an interval. This is due to the fact that T has no backward arc with endpoints in different intervals. Indeed, if a cycle in T uses a forward (backward) arc with endpoints in different intervals, then it also uses a back (forward) arc with endpoints in different intervals. It follows that for each arc uv ∈ E, neither uv nor vu is used in these k -|A(T ) ∩ E| cycles. Hence, these k -|A(T ) ∩ E| cycles in T are also cycles in T . Then, we can add a set of |A(T ) ∩ E| cycles obtained from the second property of Lemma 13 to these k -|A(T ) ∩ E| cycles to get k cycles in T . Conversely, consider a set of k cycles in . As argued earlier, we know that the number of cycles that have an arc that is in E is at most |A(T ) ∩ E|. The remaining cycles (at least k -|A(T ) ∩ E| of them) do not contain any arc that is in E, in particular, they do not contain any arc from A(T ) ∩ E. Therefore, these cycles are also cycles in T . Thus, we have the following result. ACT admits a kernel with O(k) vertices.Proof. Let (T, k) denote the instance obtained from the input instance by applying Reduction Rule 4.1 exhaustively. From Lemma 12, we know that either T has k arc-disjoint triangles or has an FAS of size at most 5(k -1) that can be obtained in polynomial time. In the first case, we return a trivial yes-instance of constant size as the kernel. In the second case, let F be the FAS of size at most 5(k -1) of T . Let (σ(T ), A(T )) be the linear representation of T where σ(T ) is a topological ordering of the vertices of the directed acyclic graph T -F . AsV (T -F ) = V (T ), |A(T )|≤ 5(k -1). If |V (T )|≥ 10k -9,then from Lemma 13, there is a partition of V (T ) into intervals with the specified properties. Therefore, Reduction Rule 4.2 is applicable (and the parameter drops by at least 1). When we obtain an instance where neither of the Reduction Rules 4.1 and 4.2 is applicable, it follows that the tournament in that instance has at most 10k vertices.Finally, we show that ACT can be solved in O (2 O(k log k) ) time. The idea is to reduce the problem to the following Arc-Disjoint Paths problem in directed acyclic graphs:

Theorems 12 and 15 Theorem 16 .

 1516 to describe an FPT algorithm for ACT. ACT can be solved in O (2 O(k log k) ) time. Proof. Consider an instance (T, k) of ACT. Using Theorem 15, we obtain a kernel I = ( T , k) such that T has O(k) vertices. Further, k ≤ k. By definition, (T, k) is an yes-instance if and only if ( T , k) is an yes-instance. Using Theorem 12, we know that T either contains k arc-disjoint triangles or has an FAS of size at most 5( k -1) that can be obtained in polynomial time. If Theorem 12 returns a set of k arc-disjoint triangles in T , then we declare that (T, k) is an yes-instance. Otherwise, let F be the FAS of size at most 5( k -1) returned by Theorem 12. Let D denote the (acyclic) digraph obtained from T by deleting F . Observe that D has O(k)

  The total number of such paths in these k cycles is O(|F |) and the arcs of these paths are contained in D which is a (simple) directed acyclic graph. S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi

  with arcs from D = T -F . This problem is essentially finding r = O(| F |) arc-disjoint paths in D and can be solved in |V (D)| O(r) time using the algorithm in [28]. Therefore, the overall running time of the algorithm is O (2 O(k log k) ) as |V (D)|= O(k) and r = O(k).

Theorem 17 .

 17 ATT can be solved in O (2 O(k) ) time. Proof. Consider an instance I = (T, k) of ATT. Let n denote |V (T )| and m denote |A(T )|. Let F denote the family of colouring functions c : A(T ) → [3k] of size 2 O(k) log 2 m that can be computed in O (2 O(k) ) time using 3k-perfect family of hash functions [?]. For each colouring function c in F, we colour A(T ) according to c and find a triangle packing of size k whose arcs use different colours. We use a standard dynamic programming routine to finding such a triangle packing. Clearly, if I is an yes-instance and C is a set of k arc-disjoint triangles in T , there is a colouring function in F that colours the 3k arcs in these triangles with distinct colours and our algorithm will find the required triangle packing. Given a colouring c ∈ F, we first compute for every set of 3 colours {a, b, c} whether the arcs coloured with a, b or c induce a triangle using 3 different colours or not. Then, for every set S of 3(p + 1) colours with p ∈ [k -1], we recursively test if the arcs coloured with the colours in S induce p + 1 arc-disjoint triangles whose arcs use all the colours of S. This is achieved by iterating over every subset {a, b, c} of S and checking if there is a triangle using colours a, b and c and a collection of p arc-disjoint triangles whose arcs use all the colours of S \ {a, b, c}. For a given S, we can find this collection of triangles in O(p 3 ) = O(k 3 ) time. Therefore, the overall running time of the algorithm is O (2 O(k) ).

  , h(a), u) forms a triangle in T }. Let M be a maximum matching of B and A (resp. U ) denote the vertices of A X (resp. U ) covered by M . Define A = A X \ A and U = U \ U . Disjoint Cycles in Tournaments We now prove that (V X ∪ U , k) is a linear kernel of (T, k). Let C be a maximum sized triangle packing that minimizes the number of vertices of U belonging to a triangle of C. By previous remarks, we can partition C into C X ∪ F where C X are the triangles of C included in T [V X ] and F are the triangles of C containing one vertex of U and two vertices of V X . It is clear that F corresponds to a union of vertex-disjoint stars of B with centres in U . Denote by U [F ] the vertices of U clause gadget g to a triangle of

  we replace the triangle of C containing a and corresponding to an edge of F by the triangle (t(a), h(a), u) where au ∈ M (and au is an edge of T ). This operation leads to another collection of arc-disjoint triangles with the same size as C but containing a strictly smaller number of vertices in U , yielding a contradiction. Finally V X ∪ U can be computed in polynomial time and we have |V X ∪ U |≤ |V X |+|M |≤ 2|V X |≤ 6k, which proves that the kernel has O(k) vertices.

  sparse tournaments is NP-complete[8]. To conclude, observe that very few problems on tournaments are known to admit an O (2 √ k )-time algorithm when parameterized by the standard parameter k [42] -FAST is one of them [4, 24]. To the best of our knowledge, outside bidimensionality theory, there are no packing problems that are known to admit such subexponential algorithms. In light of the 2 o( √ k) lower bound shown for ACT and ATT, it would be interesting to explore if these problems admit O (2 O( √ k) ) algorithms.

be solved in 2

 2 O( √ k) n O(1) time under the Exponential-Time Hypothesis. 2012 ACM Subject Classification F.2 Analysis of Algorithms and Problem Complexity 1 Introduction Given a (directed or undirected) graph G and a positive integer k, the Disjoint Cycle Packing problem is to determine whether G has k (vertex or arc/edge) disjoint (directed or undirected) cycles. Packing disjoint cycles is a fundamental problem in Graph Theory and Algorithm Design with applications in several areas. Since the publication of the classic Erdős-Pósa theorem in 1965 [26], this problem has received significant scientific attention in various algorithmic realms. In particular, Vertex-Disjoint Cycle Packing in undirected graphs is one of the first problems studied in the framework of parameterized complexity.

6 23: 4 Packing

 64 Subsequently, we refer to a set of pairwise arc-disjoint cycles as a cycle packing and a set of pairwise arc-disjoint triangles as a triangle packing. Given a tournament, MaxACT and MaxATT are the problems of obtaining a maximum set of arc-disjoint cycles and triangles, respectively. We refer to the corresponding decision version of the problems as ACT and ATT. Formally, given a tournament T and a positive integer k, ACT is the task of determining if T has k arc-disjoint cycles and ATT is the task of determining if T has k arc-disjoint triangles.MaxATT is a special case of 3-Set Packing, by creating the hypergraph on the arc set of the tournament and each triangle becomes a hyperedge. The 3-Set Packing problem admits a4 3 + ε approximation[20], implying the same result for MaxATT. From a structural point of view, the problem of partitioning the arc set of a directed graph into a collection of triangles has been studied for regular tournaments[START_REF] Yuster | Packing Triangles in Regular Tournaments[END_REF], almost regular tournaments[2] and complete digraphs[33]. In this work, we study the classical complexity of MaxACT andMaxATT and the parameterized complexity of ACT and ATT with respect to the solutionC V I T2 0 1 Arc-Disjoint Cycles in Tournaments size (i.e. the number k of cycles/triangles) as parameter. First, we show that MaxACT and MaxATT are NP-hard. Then, we show that ACT is FPT and admits a linear vertex kernel when parameterized by k. Next, we show that ATT is FPT and admits a linear vertex kernel when parameterized by k. Finally, we show that MaxACT and MaxATT are polynomial-time solvable on sparse tournaments (tournaments that have a feedback arc set

  For a digraph D, V (D) and A(D) denote the set of its vertices and the set of its arcs, respectively. Two vertices u, v are said to be adjacent in D if uv ∈ A(D) or vu ∈ A(D). For an arc e = uv, we define h(e) = v as the head of e and t(e) = u as the tail of e. For a vertex v ∈ V (D), its out-neighbourhood, denoted by N + (v), is the set {u ∈ V (D): vu ∈ A(D)} and its in-neighbourhood, denoted by N -(v), is the set {u ∈ V (D): uv ∈ A(D)}. For a set F of arcs, V (F ) denotes the union of the sets of endpoints of arcs in F . Given a digraph D and a subset X of vertices, we denote by D[X] the digraph induced by the vertices in X. Moreover, we denote by D \ X the digraph D[V (D) \ X] and say that this digraph is obtained by deleting X from D. For a set F ⊆ A(D), D -F denotes the digraph obtained from D by deleting F .

  are the only arcs of D[V (C)]. The length of a path or cycle X is the number of vertices in it and is denoted by |X|. For a set C of paths or cycles, V (C) denotes the set {v ∈ V (D): ∃C ∈ C, v ∈ V (C)} and A(C) denotes the set {e ∈ A(D): ∃C ∈ C, e ∈ A(C)}. A cycle on three vertices is called a triangle. A digraph is said to be triangle-free if it has no triangles. A set of pairwise arc-disjoint cycles is called a cycle packing and a set of pairwise arc-disjoint triangles is called a triangle packing. A digraph is called a directed acyclic graph if it has no cycles. A feedback arc set (FAS) is a set of arcs whose deletion results in an acyclic graph. For a digraph D, let minfas(D) denote the size of a minimum FAS of D. Any directed acyclic graph D has an ordering σ(D) = (v 1 , . . . , v n ) called topological ordering of its vertices such that for each v i v j ∈ A(D), i < j holds. Given an ordering σ and two vertices u and v, we write u < σ v if u is before v in σ.

  is the set of forward arcs of T in the given ordering σ(T ). The pair (σ(T ), A(T )) is called a linear representation of the tournament T . A tournament is called transitive if it is a directed acyclic graph and a transitive tournament has a unique topological ordering. It is clear that for any linear representation (σ(T ), A(T )) of T the set A(T ) is an FAS of T . A tournament is sparse if it admits an FAS which is a matching. Given a linear representation (σ(T ), A(T ))

  this case we call C a triangle with two backward arcs v i3 v i2 and v i2 v i1 ). Given two tournaments T 1 , T 2 defined by σ(T l ) and A(T l ) with l ∈ {1, 2}, we denote by T = T 1 T 2 the tournament called the concatenation of T 1 and T 2 , whereV (T ) = V (T 2 ) ∪ V (T 2 ), σ(T ) = σ(T 1 )σ(T 2) is the concatenation of the two sequences, and A(T ) = A(T 1 ) ∪ A(T 2 ).

  T . To define our final tournament T let us begin with its ordering σ defined by σ(T ) = σ(T v )σ(T c ). Then we construct A vc (T ) the backward arcs between T c and T v . For any j ∈ [m], if the clause c j in F has three literals, that is c j = 1 ∨ 2 ∨ 3 , then we add to A vc (T ) the three backward arcs c 3 j z u where u ∈[3] and such that z u = xiu when u = viu , andz u ∈ {x 1 iu , x 2 iu } when u = v iuin such a way that for any i ∈ [n], there exists a unique arc a ∈ A vc (T ) with h(a) = x 1 i . Informally, in the previous definition, if x 1 iu is already "used" by another clause, we chose z u = x 2 iu . Such an orientation will always be possible since each variable occurs at most two times positively and once negatively in F . If the clause c j in F has only two literals, that is c j = 1 ∨ 2 , then we add in A vc (T ) the two backward arcs c 2 j z u where u ∈ [2] and such that z u = xiu when u = viu and z u ∈ {x 1 iu , x 2 iu } when u = v iu in such a way that for any i ∈ [n], there exists a unique arc a ∈ A vc (T ) with h(a) = x 1 i . Finally, we add in A vc (T ) the backward arcs c u m+1 xi for any u ∈ [3] and i ∈ [n]. These arcs are called dummy arcs. We set A σ

Figure 2

 2 Figure 2 Example of reduction obtained when F = {c1, c2} where c1 = v1 ∨ v2 ∨ v3 and c2 = v1 ∨ v2 ∨ v3. Forward arcs are not depicted. In addition to the depicted backward arcs, we have the 36 backward arcs from V3 to V1, and the 9 backward arcs from C3 to C1.

Lemma 1 .

 1 There exists a triangle packing ∆ v (resp. ∆ c ) which uses exactly the arcs between distinct variable gadgets (resp. clause gadgets). Therefore, we have |∆ V,V,V |≤ 6n(n -1) and |∆ C,C,C |≤ 3m(m + 1)/2 and these bounds are tight.

  First, inequality (i) comes from Lemma 1. Then, we have |∆ 2V,C |+|∆ V,2C |+|∆ V,C,C |+|∆ V,V,C |≤ |A vc (T )| since every triangle of these sets consumes one backward arc from T c to T v . We have |∆ 3V |≤ 2n since we have at most 2 disjoint triangles in each variable gadget. Finally we also have |∆ 3C |≤ 1 since the dummy triangle is the only triangle lying in a clause gadget. These two lemmas allow us to prove the following. Lemma 3. F is satisfiable if and only if there exists a triangle packing ∆ of size 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1 in the tournament T .

  will use one arc between two distinct variable gadgets (resp. clause gadgets) and according to Lemma 1, ∆ v (resp. ∆ c ) uses all the arcs between distinct variable gadgets (resp. clause gadgets). Finally, we always have |∆ 3V |≤ 2n and |∆ 3C |≤ 1 by construction. Therefore, if x = 0, we have |∆|< |∆ v |+|∆ c |+x+(|A vc (T )|-x)+2n+1 that is |∆|< 6n(n-1)+3m(m+1)/2+2n+|A vc (T )|+1, which is impossible. So we must have x = 0, which implies ∆ V,V,C = ∆ V,C,C = ∅.

Lemma 5 .

 5 Given a 3-SAT(3) instance F , and T the tournament constructed from F with the reduction f , we have a triangle packing ∆ of T of size 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1 if and only if there is a cycle packing O of the same size. Proof. Given a cycle packing O of T of size 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1, we partition it into the following sets:

j c 3 j and c 2 j c 3

 3 have at least three vertices which implies |O V * |≤ 6n(n -1). We obtain |O C * |≤ 3m(m + 1)/2 using the same reasoning on O C * . Finally, we have |O V * ,C * |≤ |A vc (T )| since each cycle must have at least one backward arc. Putting these upper bounds together, we obtain that |O|≤ 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1 which implies that the bounds are tight. In particular, cycles of O V * (resp. O C * ) use exactly three arcs that are between distinct variable gadgets (resp. clause gadgets) and all these arcs are used. So we can construct a new cycle packing O where we replace the cycles of O V * and O C * by the triangle packings ∆ v and ∆ c defined in Lemma 1. The new solution uses a subset of arcs of O and has the same size. The cycles of O V * ,C * use exactly one backward arc of A vc (T ) due to the tight upper bound |A vc (T )|. Moreover, by the previous reasoning, two vertices of a cycle of O V * ,C * cannot belong to two different variable gadgets (resp. clause gadgets). Let C j be a clause gadget which has three literals (if it has only two literals, the reasoning is analogous). Let xi k ∈ V i k be the head of a backward arc from c 3 j where k ∈ [3]. By the previous arguments each arc c 3 j xi k is contained in a cycle o k of O for k ∈ [3]. There is at least one xi k whose next vertex in o k , say y, belongs to V i k since C j has only two other vertices in addition to c 3 j . Without loss of generality, we may assume that xi3 is that vertex. Then, we can replace o 1 and o 2 by the triangles (x i1 , c 1 j , c 3 j ) and (x i2 , c 2 j , c 3 j ). The arcs c 1 j cannot have already been used because C j is acyclic and we previously consumed all the arcs between clause gadgets. In the same way, we replace the cycle o 3 by the triangle (x i3 , y, c 3 j ). The arc yc 3 j is available since it could have been used only in the cycle o 3 .

  be an FAS of T v . As according to Lemma 1 there is a cycle packing of size 6n(n -1) in T v , we get |F V V |≥ 6n(n -1). The same arguments hold for the clause part, and thus with F CC = j,j ∈[m+1],j =j F Cj C j , we get |F CC |≥ 3m(m + 1)/2.

  The reverse direction of the claim holds trivially. Let us now prove the forward direction. Let C be a set of r arc-disjoint cycles in T that minimizes C∈C |C|. If every cycle in C is a triangle, then the claim trivially holds. Otherwise, let C be a longest cycle in C and let denote its length. Let v i , v j be a pair of non-consecutive vertices in C. Then, either v i v j ∈ A(T ) or v j v i ∈ A(T ). In any case, the arc e between v i and v j along with A(C) forms a cycle C of length less than with A(C ) \ {e} ⊂ A(C). By our choice of C, this implies that e is an arc in some other cycle C ∈ C. This property is true for the arc between any pair of non-consecutive vertices in C. Therefore, we have 2 -≤ (k -1) leading to≤ 2k + 1.This result essentially shows that it suffices to determine the existence of k arc-disjoint cycles in T each of length at most 2k + 1 in order to determine if (T, k) is an yes-instance of ACT. This immediately leads to a quadratic Erdős-Pósa bound. That is, for every non-negative integer k, every tournament T either contains k arc-disjoint cycles or has an FAS of size O(k 2

1 .Theorem 13 .

 113 For a digraph D, let Λ(D) denote the number of non-adjacent pairs of vertices in D. That is, Λ(D) is the number of pairs u, v of vertices of D such that neither uv ∈ A(D) nor vu ∈ A(D). Recall that for a digraph D, minfas(D) denotes the size of a minimum FAS of D.Lemma 12.[17] Let D be a triangle-free digraph in which for every pair u, v of distinct vertices, at most one of uv or vu is in A(D). Then, we can compute an FAS of size at mostΛ(D) in polynomial time.This leads to the following main result of this section. For every non-negative integer k, every tournament T either contains k arc-disjoint triangles or has an FAS of size at most 5(k -1) that can be obtained in polynomial time.Proof. Let C be a maximal set of arc-disjoint triangles in T (that can be obtained greedily in polynomial time). If |C|≥ k, then we have the required set of triangles. Otherwise, let D denote the digraph obtained from T by deleting the arcs that are in some triangle in C. Clearly, D has no triangle and Λ(D) ≤ 3(k -1). Let F be an FAS of D obtained in polynomial time using Lemma 12. Then, we have |F |≤ 3(k -1). Next, consider a topological ordering σ of D -F . Each triangle of C contains at most 2 arcs which are backward in this ordering. If we denote by F the set of all the arcs of the triangles of C which are backward in σ, then we have |F |≤ 2(k -1) and (D -F ) -F is acyclic. Thus F * = F ∪ F is an FAS of T satisfying |F * |≤ 5(k -1).

F

  into k sets, F 1 to F k and the set {π 1 , . . . , π k } of permutations where π i is a permutation of F i for each i ∈ [ k]. Any cycle C i that has F i ⊆ F contains a (v, x)-path between every pair (u, v), (x, y) of consecutive arcs of F i with arcs from A(D). That is, there is a path from h(π -1 i (j)) and t(π -1 i ((j + 1) mod |F i |)) with arcs from D for each j ∈ [|F i |]. The total number of such paths in these k cycles is O(|F |) and the arcs of these paths are contained in D which is a (simple) directed acyclic graph. The number of choices for F is 2 | F | and the number of choices for a partition F = {F 1 , . . . , F k } of F and a set X = {π 1 , . . . , π k } of permutations is 2 O(| F |log| F |) . Once such a choice is made, the problem of finding k arc-disjoint cycles in T reduces to the problem of finding k arc-disjoint cycles C = {C 1 , . . . , C k } in T such that for each 1 ≤ i ≤ k and for each 1 ≤ j ≤ |F i |, C i has a path P ij between h(π -1 i (j)) and t(π -1 i ((j + 1) mod |F i |)) with arcs from D = T -F . This problem is essentially finding r = O(| F |) arc-disjoint paths in D and can be solved in |V (D)| O(r) time using the algorithm in [32]. Therefore, the overall running time of the algorithm is O (2 O(k log k) ) as |V (D)|= O(k) and r = O(k).

Theorem 18 .

 18 ATT can be solved in O (2 O(k) ) time. Proof. Consider an instance I = (T, k) of ATT. Let n denote |V (T )| and m denote |A(T )|. Let F denote the family of colouring functions c : A(T ) → [3k] of size 2 O(k) log 2 m that can S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi 23:17 be computed in O (2 O(k)) time using 3k-perfect family of hash functions[START_REF] Schmidt | The Spatial Complexity of Oblivious k-Probe Hash Functions[END_REF]. For each colouring function c in F, we colour A(T ) according to c and find a triangle packing of size k whose arcs use different colours. We use a standard dynamic programming routine to finding such a triangle packing. Clearly, if I is an yes-instance and C is a set of k arc-disjoint triangles in T , there is a colouring function in F that colours the 3k arcs in these triangles with distinct colours and our algorithm will find the required triangle packing. Given a colouring c ∈ F, we first compute for every set of 3 colours {a, b, c} whether the arcs coloured with a, b or c induce a triangle using 3 different colours or not. Then, for every set S of 3(p + 1) colours with p ∈ [k -1], we recursively test if the arcs coloured with the colours in S induce p + 1 arc-disjoint triangles whose arcs use all the colours of S. This is achieved by iterating over every subset {a, b, c} of S and checking if there is a triangle using colours a, b and c and a collection of p arc-disjoint triangles whose arcs use all the colours of S \ {a, b, c}.For a given S, we can find this collection of triangles in O(p 3 ) = O(k 3 ) time. Therefore, the overall running time of the algorithm is O (2 O(k) ).

  a), h(a), u) forms a triangle in T }. Let M be a maximum matching of B and A (resp. U ) denote the vertices of A X (resp. U ) covered by M . Define A = A X \ A and U = U \ U . We now prove that (V X ∪ U , k) is a linear kernel of (T, k). Let C be a maximum sized triangle packing that minimizes the number of vertices of U belonging to a triangle of C. By previous remarks, we can partition C into C X ∪ F where C X are the triangles of C included in T [V X ] and F are the triangles of C containing one vertex of U and two vertices of V X . It is clear that F corresponds to a union of vertex-disjoint stars of B with centres in U . Denote by U [F ] the vertices of U which belong to a triangle of F

  edge of M in T and T contains as many edges of M than edges of F . Now for every arc a ∈ A X ∩ V (T ) we replace the triangle of C containing a and corresponding to an edge of F by the triangle (t(a), h(a), u) where au ∈ M (and au is an edge of T ). This operation leads to another collection of arc-disjoint triangles with the same size as C but containing a strictly smaller number of vertices in U , yielding a contradiction.Finally V X ∪ U can be computed in polynomial time and we have |V X ∪ U |≤ |V X |+|M |≤ 2|V X |≤ 6k, which proves that the kernel has O(k) vertices.

  [A], one of T [B] and X 0 . Thus to solve MaxATT or MaxACT on T we can solve the problem on T [A] and on T [B] and build the optimal solution for T . Therefore we can focus on the case where every vertex of T is the beginning or the end of a backward arc A(T ). We will call such a tournament a fully sparse tournament. So we focus on solving MaxATT in fully sparse tournaments. In the following, let Π be the problem of finding a collection of arc-disjoint triangles of maximum size on fully sparse tournament. Now order the arcs e 1 , . . . , e b of A(T ) such that for any i ∈ [b -1], h(e i ) < σ h(e i+1 ).

Lemma 21 .

 21 We can assume that G is connected otherwise we apply the result on every connected component of G and the disjoint union of the solutions produces an optimal solution on the whole digraph G .So assume that G is connected and let S be a terminal strong component of G . If X is an optimal solution of Π (G ) then the restriction of X to the arcs of G [S] is an optimal solution of Π (G [S]). Indeed otherwise we could replace this set of arcs in X by an optimal solution of Π (G [S]) and obtain a better solution for Π (G ), a contradiction. So by Claim 19.2 and Claim 19.4 the set X contains at most i=1,...,p |S i |-k arcs lying in a terminal component of G . Now as every vertex of G \ i=1,...,p S i is the beginning of at most one arc of X, the set X has size at most nk. Conversely by growing in-branchings in G from the union of the optimal solutions of Π (G [S i ]) for i = 1, . . . , p, by Claim 19.2 and 19.4 we obtain a solution of Π (G ) of size nk which is then optimal. Moreover, this solution can clearly be built in polynomial time. Using Claim 19.1 and Lemma 20 we can solve MaxATT in polynomial time. In a fully sparse tournament T the size of a maximum cycle packing is equal to the size of a maximum triangle packing. Proof. First if T has an optimal triangle packing of size |A(T )| then as A(T ) is an FAS of T , every optimal cycle packing of T has size |A(T )|. Otherwise, we build from T the digraph G as previously. By Lemma 20, G has some terminal components S 1 , . . . , S k which are either a single vertex or induces a digoned tree and every optimal triangle packing of T has size |A(T )|-k. Let see that no S i can be a single vertex. Indeed if S i = {e} where e is a backward arc of T , it means that no backward of T begins or ends between h(e) and t(e) in σ(T ). As T is fully sparse, it means that h(e) and t(e) are consecutive in σ(T ) what we forbid previously. Now consider a component S i which induces a digoned tree in G . Let π i be the order σ(T ) restricted to the heads and tails of the arcs of T corresponding to the vertices of S i . First notice that π i is an interval of the order σ(T ). Indeed otherwise there exists two backward arcs a and b of T such that a ∈ S i , b / ∈ S i and h(a) is before the head or the of b which is before t(a) in σ(T ). But in this case there is an arc in G from a to b contradicting the fact

1 .

 1 i x i+1 : i even and i ∈ [l -2]} is an FAS of T [{x 1 , . . . , x l }] and has size l/2 -1 = |S i |-1. So we have |∆ i |≤ |S i |-Repeating this argument for i = 1, . . . , k we obtain that |∆|≤ |A(T )|-k. Thus by Lemma 20 ∆ has the same size than an optimal triangle packing of T .

S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi 23:7 and

  3. Kn by the variable gadget V i and kept all the arcs between two variable gadgets V i V j in the same orientation as between u i and u j . Let u i u j u k be a triangle of the perfect packing of T Kn . We temporally relabel the vertices of V i , V j and V k respectively by {f i , i ∈ [6]}, {g i , i ∈ [6]} and {h i , i ∈ [6]} and consider the tripartite tournament K 6,6,6 given by V (K 6,6,6 ) = {f i , g i , h i , i ∈ [6]} and A(K 6,6,6 ) = {f i g j , g i h j , h i f j : i, j ∈ [6]}. Then it is

	Lemma 1. There exists a triangle packing ∆ v (resp. ∆ c ) which uses exactly the arcs between distinct variable gadgets (resp. clause gadgets). Therefore, we have |∆ V,V,V |≤ 6n(n -1) and |∆ C,C,C |≤ 3m(m + 1)/2 and these bounds are tight. Proof. First recall that the tournament T v is constructed from a tournament T Kn which admits a perfect packing of n(n -1)/6 triangles. Then we replaced each vertex u i in T easy to check that {(f i , g j , h i+j (mod 6) ) : i, j ∈ [6]} is a perfect triangle packing of K 6,6,6 .

  |+ |∆ 3V |+ |∆ 3C |. First, inequality (i) comes from Lemma 1. Then, we have |∆ 2V,C |+|∆ V,2C |+|∆ V,C,C |+|∆ V,V,C |≤ |A vc (T )| since every triangle of these sets consumes one backward arc from T c to T v . We have |∆ 3V |≤ 2n since we have at most 2 disjoint triangles in each variable gadget. Finally we also have |∆ 3C |≤ 1 since the dummy triangle is the only triangle lying in a clause gadget.

	Lemma 3. F is satisfiable if and only if there exists a triangle packing ∆ of size 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1 in the tournament T .

  and MaxACT are NP-hard (Theorems 4 and 6). As a consequence, we also show that ACT and ATT do not admit algorithms with O (2 o(

	√ k) ) running time under the Exponential-Time Hypothesis (Theorem 10). Moreover, deciding if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete (Theorem 9). A tournament T has k arc-disjoint cycles if and only if T has k arc-disjoint cycles each of length at most 2k + 1 (Theorem 11).

ACT can be solved in O (2 O(k log k) ) time (Theorem 17) and admits a kernel with O(k) vertices (Theorem 16). ATT can be solved in O (2 O(k) ) time (Theorem 18) and admits a kernel with O(k) vertices (Theorem 19).

MaxATT and MaxACT restricted to sparse tournaments is polynomial-time solvable (Theorem 22).

23:12 Packing Arc-Disjoint Cycles in Tournaments For

  have exactly 2 cycles, and notice that by construction one cannot have two cycles each having a size greater than 3. First, if the two cycles are triangles, we are done. Then O V [V i ] contains a triangle, say δ, and a cycle, say o, of size greater than 3. If o contains the backward arc s i r i , then by construction o = (r i , xi , x1 i , s i ). In that case, we necessary have δ = (x 1 i , x 2 i , t i ) and we can restructure o in the triangle (r i , x 1 i , s i ). The arc any i, i ∈[n], j, j ∈ [m + 1] and X ∈ {V i , C j , V i C j , V i V i , C j C j },we also define the corresponding sets F X in F , where for example F Vi = F ∩A Vi . In addition, for any j ∈ [m+1] we define F * Cj = i∈[n] F ViCj . Let T v be the directed graph (T v is not a tournament) obtained by starting from T v and only keeping arcs in A ViV i for any i, i ∈ [n] with i

  3 j ) (there are only forward arcs). As |F * Cj |≤ 1, there exists i ∈ [n] and two arcs a 1 , a 2 not in F such that t(a 1 ) = c 3 j , h(a 1 ) ∈ V i , t(a 2 ) = h(a 1 ), and h(a 2 ) = t(a). Thus, (t(a 1 ), t(a 2 ), h(a 2 )) is a triangle using no arc of F , a contradiction. As the same kind of arguments holds for the case where u j = 2, we get that for any j ∈ S, |F Cj |≥ u j -1 (implying also |F * Cj |= 0). Let us now prove that |S|≤ 1. Suppose by contradiction that |S|≥ 2. Let j 1 and j 2 be in S. For any l ∈ [2], let define a l such that there exists i l ∈ [n] with t(a l ) ∈ C j l and h(a 1 ) ∈ V i l . Notice that we may have i 1 = i 2 , but we always have h(a 1 ) = h(a 2 ). Moreover, as a i is the unique backward arc of T with t(a) ∈ j∈[m] C j , we get that a 3 = h(a 1 )t(a 2 ) and a 4 = h(a 2 )t(a 1 ) are forward arcs of T . As |F * Cj 1 |= |F * Cj 2 |= 0 we know that a l / ∈ F for l ∈ [4]. Thus, (t(a 1 ), h(a 1 ), t(a 2 ), h(a 2 ), t(a 1 )) is a cycle using no arc of F , a contradiction. Let L = {i ∈ [n]: ∃a ∈ T s.t. h(a) ∈ V i and t(a) ∈ C j , j ∈ S}. Notice that if S = ∅ then L = ∅, and otherwise |L |= u j0 , where S = {j 0 }. Let S = [n] \ L . For any i ∈ [n], let A ViCm+1 = A(T ) ∩ A ViCm+1 . Recall that A ViCm+1 = c u m+1 xi for u ∈ [3] where xi ∈ V i . Moreover, for any x ∈ {x i , x 1 i , x 2 i }, let A xVi = {a ∈ T : t(a) = x and h(a) ∈ V i }. Notice that |A xiVi |= 4, |A x 1 i Vi |= 2 and |A x 2 i Vi |= 1. Let us prove that for any i ∈ S , |F Vi ∪ F ViCm+1 |≥ 5. If A xiVi ⊆ F , then as F Vi must be an FAS of V i and A xiVi is not an FAS of V i , there exists at least another arc in F Vi and we get |F Vi |≥ 5. Otherwise, A ViCm+1 ⊆ F (if it is not the case, there is a cycle c u m+1 xi v where v ∈ V i is a out-neighbour of xi ). Then, as minfas(V i ) ≥ 2, |F Vi ∪ F ViCm+1 |≥ 5. Let us finally prove that for any i ∈ L , |F Vi ∪ F ViCm+1 |≥ 6. As i ∈ L , there is an arc a ∈ T with h(a) ∈ V i and t(a) ∈ C j0 where S = {j 0 }. Let x = h(a). Notice that x ∈ {x i , x 1 i , x 2 i }. As |F * Cj 0 |= 0 we get that A xVi ⊆ F Vi (otherwise there would be a cycle with one vertex in C j0 , x, and an out-neighbour of x in V i ). Vi must be an FAS of V i , F needs two other arcs in A Vi and we get |F Vi |≥ 6.

	Case 1: x = xi .As F

16 Packing Arc-Disjoint Cycles in Tournaments 4.3 An FPT Algorithm Finally

  , we show that ACT can be solved in O (2 O(k log k) ) time. The idea is to reduce the problem to the following Arc-Disjoint Paths problem in directed acyclic graphs: given a digraph D on n vertices and k ordered pairs (s 1 , t 1 ), . . . , (s k , t k ) of vertices of D, do there exist arc-disjoint paths P 1 , . . . , P k in D such that P i is a path from s i to t i for each i ∈ [k]? On directed acyclic graphs, Arc-Disjoint Paths is known to be NP-complete[27], W[1]-hard[START_REF] Slivkins | Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs[END_REF] with respect to k as parameter and solvable in n O(k) time[32]. Despite its fixed-parameter intractability, we will show that we can use the n O(k) algorithm and Theorems 13 and 16 to describe an FPT algorithm for ACT. ACT can be solved in O (2 O(k log k) ) time. Proof. Consider an instance (T, k) of ACT. Using Theorem 16, we obtain a kernel I = ( T , k) such that T has O(k) vertices. Further, k ≤ k. By definition, (T, k) is an yes-instance if and only if ( T , k) is an yes-instance. Using Theorem 13, we know that T either contains

	Theorem 17.

Reduction Rule 4.1. If a vertex v is not in any cycle, then delete v from T .

23:

k arc-disjoint triangles or has an FAS of size at most 5( k -1) that can be obtained in polynomial time. If Theorem 13 returns a set of k arc-disjoint triangles in T , then we declare that (T, k) is an yes-instance.

Otherwise, let F be the FAS of size at most 5( k -1) returned by Theorem 13. Let D denote the (acyclic) digraph obtained from T by deleting F . Observe that D has O(k)

The authors would like to thank F. Havet for pointing out that Lemma 11 was a consequence of a result of[15], as well for an improvement of the constant in Theorem 12.

The authors would like to thank F. Havet for pointing out that Lemma 12 was a consequence of a result of[17], as well for an improvement of the constant in Theorem 13.

Lemma 14 is Lemma

3.9 of[11] that has been rephrased to avoid the use of several definitions and terminology introduced in[11].

r i x 1 i is not contained in O since the only arcs inside V i we may have imposed until now are out-going arcs of x 1 i , x 2 i and xi . If o contains the backward arc t i x 1 i , then by construction o = (x 1 i , s i , x 2 i , t i ) and t = (r i , xi , s i ). In the same way, we can restructure o into (x 1 i , s i , t i ) whose all the arcs are available.

As O C is already a triangle, T finally has a triangle packing of size 6n(n -1) + 3m(m + 1)/2 + 2n + |A vc (T )|+1. The other direction of the equivalence is straightforward.

The previous lemma and Theorem 4 directly imply the following theorem.

Theorem 6. MaxACT is NP-hard.

Let us now define two special cases Tight-ATT (resp. Tight-ACT) where, given a tournament T and a linear ordering σ with k backward arcs (where k = minfas(T )), the goal is to decide if there is a triangle (resp. cycle) packing of size k. We call these special cases the "tight" versions of the classical packing problems because as the input admits an FAS of size k, any triangle (or cycle) packing has size at most k. We now prove that we can construct in polynomial time an ordering of T , the tournament of the reduction, with k backward arcs (where k is the threshold value defined in Lemma 3). . As all edges are used in O this defines an orientation for all edges. Thus, there is only |O| backward arcs in σ. Thus, when using the previous orientations T Kn to construct the variable tournament T v of the reduction (remember that we blow up each vertex u i into 6 vertices V i ), we get an ordering with 36n(n -1)/6 = 6n(n -1) backward arcs between

Following the same construction for the clause tournament T c we get an ordering with 3m(m + 1)/2 backward arcs between two distinct C j . Now, as there are two backward arcs in each V i , one backward arc in C m+1 , and |A vc (T )| backward arcs from T c to T v , the total number of backward arcs is k.

We also prove that k = minfas(T ).

Lemma 8. Let T = (V, A) be a tournament constructed by the reduction f and k be the threshold value defined in Lemma 3. Then, minfas(T ) ≥ k.

Proof. We suppose that T is equipped with the ordering defined in Lemma 7. Let F be an optimal FAS of T . Given an arc a, let v(a) = {t(a), h(a)}. Let us partition the arcs of T into the following sets. For any i ∈ [n], j ∈ [m + 1], let us define

Then, using Lemma 7 and Lemma 8, we get the NP-hardness of Tight-ATT and Tight-ACT.

Theorem 9. Tight-ATT and Tight-ACT are NP-hard.

Finally, the size s of the required packing in Lemma 3 satisfies s = O((n + m) 2 ). Under the Exponential-time Hypothesis, the problem 3-SAT cannot be solved in 2 o(n+m) [21,35].

Then, using the linear reduction from 3-SAT to 3-SAT(3) [START_REF] Tovey | A simplified NP-complete satisfiability problem[END_REF], we also get the following result.

Theorem 10. Under the Exponential-time Hypothesis, ATT and ACT cannot be solved

In the framework of parameterizing above guaranteed values [45], the above results imply that ACT parameterized below the guaranteed value of the size of a minimal feedback arc set is fixed-parameter intractable.

Parameterized Complexity of ACT

The classical Erdős-Pósa theorem for cycles in undirected graphs states that there exists a function f (k) = O(k log k) such that for each non-negative integer k, every undirected graph either contains k vertex-disjoint cycles or has a feedback vertex set consisting of f (k) vertices [26]. An interesting consequence of this theorem is that it leads to an FPT algorithm for Vertex-Disjoint Cycle Packing. It is well known that the treewidth (tw) of a graph is not larger than the size of its feedback vertex set, and that a naive dynamic programming scheme solves Vertex-Disjoint Cycle Packing in O (2 O(tw log tw) ) time (see, e.g., [21]). Thus, the existence of an O (2 O(k log 2 k) ) time algorithm can be viewed as a direct consequence of the Erdős-Pósa theorem (see [43] for more details). Analogous to these results, we prove an Erdős-Pósa type theorem for tournaments and show that it leads to an

) time algorithm and a linear vertex kernel for ACT.

An Erdős-Pósa Type Theorem

In this section, we show certain interesting combinatorial results on arc-disjoint cycles in tournaments.

23:15

This rule is clearly safe as our goal is to find k cycles and v cannot be in any of them.

To describe our next rule, we need to state a lemma known from [11]. An interval is a consecutive set of vertices in a linear representation (σ(T ), A(T )) of a tournament T .

Lemma 14 ([11]). h(e i ) < σ h(e k ). Moreover, we cannot have t(e i ) = t(e k ) without contradicting that T is a sparse tournament. As h(e i ) < σ h(e k ) the arc h(e i )s(e j ) is not an arc of Π(e k e l ). Thus if Π(e i e j ) and Π(e k e l ) share a common arc, it means that s(e j )t(e i ) = h(e k )s(e l ). But in this case e i = e l and e j = e k , implying {e i e j , e k e l } is a digon of G , which contradict the fact that X is a solution Π (G ). So, if X is a solution of Π (G ), then Π(X) is an solution of Π(T ). Notice that the size of the solution does not change.

On the other hand, if X is a subset of the arcs of G such that Π(X) is a solution of Π(T ). We cannot have a vertex e i of G such that d + X (e i ) > 1, since it would imply that the backward arc e i of T is covered by at least two triangles of Π(X). So X induces a functional subdigraph of G . As previously the digraph induced by X is also digon-free otherwise we would have two arc-disjoint triangles on only four vertices in Π(X), which is impossible.

Thus, X is a solution of Π (G ), and the solution of the same size.

The two problems Π and Π being both maximization problems, they have the same optimal solution. Now we show how to solve Π in polynomial time. Proof. We construct the arc set X as follows: we start by taking the arcs of C. Then, while there is a vertex x which is not covered by any arcs of X, we add to X the arcs of the shortest path from x to any vertex of X. By construction, every vertex x of every arc of X

Proof. The case |V (G )|= 1 is clear. So assume that G is a digoned tree and let X be a set of arcs of G corresponding to an optimal solution of Π (G ). Then X is acyclic and then

Concluding Remarks

In this work, we studied the classical and parameterized complexity of packing arc-disjoint cycles and triangles in tournaments. We showed NP-hardness, fixed-parameter tractability and linear kernelization results. We also showed that these problems are polynomial-time solvable