The Parameterized Complexity of Packing Arc-Disjoint Cycles
in Tournaments
R. Krithika1 , Abhishek Sahu1 , Saket Saurabh1,2 , and Meirav Zehavi3

arXiv:1802.07090v1 [cs.DS] 20 Feb 2018

1

The Institute of Mathematical Sciences, HBNI, Chennai, India. ,
{rkrithika|asahu|saket}@imsc.res.in
2
University of Bergen, Bergen, Norway
3
Ben-Gurion University, Beersheba, Israel. meiravze@bgu.ac.il

Abstract
Given a directed graph D on n vertices and a positive integer k, the Arc-Disjoint
Cycle Packing problem is to determine whether D has k arc-disjoint cycles. This
problem is known to be W[1]-hard in general directed graphs. In this paper, we initiate a systematic study on the parameterized complexity of the problem restricted to
tournaments. We show that the problem is fixed-parameter tractable and admits a
polynomial kernel when parameterized by the solution size k. In particular, we show
that it can be solved in 2O(k log k) nO(1) time and has a kernel with O(k) vertices. The
primary ingredient in both these results is a min-max theorem that states that every
tournament either contains k arc-disjoint triangles or has a feedback arc set of size at
most 6k. Our belief is that this combinatorial result is of independent interest and
could be useful in other problems related to cycles in tournaments.

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 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 Erdös-Pósa theorem
in 1965 [17], 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 f(k)nO(1) time
for some function f, where n is the input size. For convenience, the running time f(k)nO(1)
where f grows super-polynomially with k is denoted as O⋆ (f(k)). 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. 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
1

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 [15, 16, 19].
Vertex-Disjoint Cycle Packing in undirected graphs is FPT with respect to the
solution size k [10, 25] but has no polynomial kernel unless NP ⊆ coNP/poly [11]. In
contrast, Edge-Disjoint Cycle Packing in undirected graphs admits a kernel with
O(k log k) vertices (and is therefore FPT) [11]. On directed graphs, Vertex-Disjoint
Cycle Packing and Arc-Disjoint Cycle Packing are equivalent and turn out to be
W[1]-hard [23, 30]. 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 [5,26]. 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 theory and social choice theory. Further, the combinatorics of inclusion
relations of tournaments is reasonably well-understood [13]. 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
[29]. Developing a similar theory of inclusion relations of directed graphs has been a longstanding research challenge. However, there is such a result known for tournaments that
states that tournaments are well-quasi-ordered under the strong immersion relation [13]. In
fact, this result also holds for a superclass of tournaments, namely, semicomplete digraphs
[7]. 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. This is another
reason why tournaments is one of the most well-studied classes of directed graphs.
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 directed graph and a positive integer k, Feedback
Arc (Vertex) Set is the problem of determining if the graph has a set of at most k arcs
(vertices) whose deletion results in an acyclic graph. These problems are the dual problems
of Vertex-Disjoint Cycle Packing and Arc-Disjoint Cycle Packing, respectively.
They are known to be NP-hard on tournaments [2, 12, 14, 31] but are FPT when parameterized by k [3,20,22,28]. Further, Feedback Arc Set in Tournaments has a kernel with
O(k) vertices [9] and Feedback Vertex Set in Tournaments has a kernel with O(k1.5 )
vertices [24]. Though Feedback Arc Set and Feedback Vertex Set are intensively
studied in tournaments, their duals have surprisingly not been considered in the literature
until recently [8, 24]. Any tournament that has a cycle also has a triangle [6]. 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. A straightforward application of the color coding technique shows that this problem is
FPT and a kernel with O(k2 ) vertices is an immediate consequence of the quadratic element
kernel known for 3-Set Packing [1]. Recently, a kernel with O(k1.5 ) vertices was shown
for this problem using interesting variants and generalizations of the popular expansion
lemma [24].
Focusing on Arc-Disjoint Cycle Packing in tournaments, 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. This is the starting point of our study. In this paper, we investigate the parameterized complexity of Arc-Disjoint Cycle Packing in
tournaments.

2

Arc-Disjoint Cycle Packing in Tournaments (ACT)
Input: A tournament T and a positive integer k.
Question: Do there exist k arc-disjoint cycles in T ?

Parameter: k

We show that ACT is FPT and admits a polynomial kernel. En route, we discover an
interesting min-max relation analogous to the classical Erdös-Pósa theorem. In particular,
we show the following results.
• 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 (Lemma 1).
• Every tournament T either contains k arc-disjoint triangles or has a feedback arc set
of size at most 6(k − 1) (Theorem 4).
• ACT admits a kernel with O(k) vertices (Theorem 13).
• ACT can be solved in O⋆ (2O(k log k) ) time (Theorem 14).
The paper is organized as follows. In Section 2, we give some definitions related to directed
graphs, cycles and tournaments. In Section 3, we show the first two combinatorial results
about tournaments. In Section 4, we show that ACT is FPT and admits a polynomial
kernel. In Section 5, we describe an improved FPT algorithm and a linear vertex kernel for
ACT. Finally, we conclude with some remarks in Section 6.

2

Preliminaries

The set {1, 2, . . . , n} is denoted by [n]. 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. We
will consider only simple unweighted digraphs. 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 (u, v) ∈ A(D) or (v, u) ∈ A(D). For an arc e = (u, v), head(e) denotes
v and tail(e) denotes u. For a vertex v ∈ V(D), its out-neighborhood, denoted by N+ (v),
is the set {u ∈ V(D) | (v, u) ∈ A(D)} and its in-neighborhood, denoted by N− (v), is the
set {u ∈ V(D) | (u, v) ∈ A(D)}. For a set of arcs F, V(F) denotes the union of the sets of
endpoints of arcs in F. For a set X ⊆ V(D) ∪ E(D), D − X denotes the digraph obtained
from D by deleting X.
A path P in D is a sequence (v1 , . . . , vk ) of distinct vertices such that for each i ∈ [k − 1],
(vi , vi+1 ) ∈ A(D). The set {v1 , . . . , vk } is denoted by V(P) and the set {(vi , vi+1 ) | i ∈ [k − 1]}
is denoted by A(P). A path P is called an induced (or chordless) path if there is no arc in D
that is between two non-consecutive vertices of P. A cycle C in D is a sequence (v1 , . . . , vk )
of distinct vertices such that (v1 , . . . , vk ) is a path and (vk , v1 ) ∈ A(D). The set {v1 , . . . , vk }
is denoted by V(C) and the set {(vi , vi+1 ) | i ∈ [k − 1]} ∪ {(vk , v1 )} is denoted by A(C). A
cycle C = (v1 , . . . , vk ) is called an induced (or chordless) cycle if there is no arc in D that
is between two non-consecutive vertices of C with the exception of the arc (vk , v1 ). 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, 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 digraph is called a directed acyclic graph if it has no cycles. Any directed acyclic
graph D has an ordering σ called topological ordering of its vertices such that for each
(u, v) ∈ A(D), σ(u) < σ(v) holds. A feedback vertex (arc) set is a set of vertices (arcs)
whose deletion results in an acyclic graph. For a digraph D, let fas(D) denote the size of a
minimum feedback arc set of D. A tournament T is a digraph in which for every pair u, v
3

of distinct vertices either (u, v) ∈ A(T ) or (v, u) ∈ A(T ) but not both. A tournament is
called transitive if it is a directed acyclic graph and a transitive tournament has a unique
topological ordering.

3

An Erdös-Pósa Type Theorem

The classical Erdös-Pó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 [17]. 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 2O(tw log tw ) n time and
2
exponential space (see, e.g., [15]). Thus, the existence of a 2O(k log k) n time algorithm that
uses exponential space can be viewed as a direct consequence of the Erdös-Pósa theorem
(see [25] for more details).
In this section, we show that that there exists a function h(k) such that for each nonnegative integer k, every tournament either contains k arc-disjoint cycles or has a feedback
arc set consisting of h(k) arcs. First, we show that h(k) is O(k2 ) and then improve it to
O(k). The following result is crucial in proving the former.
Lemma 1. Let k and r be positive integers such that r ≤ k. If a tournament T contains a
set C of r arc-disjoint cycles, then it also contains a set C ∗ of r arc-disjoint cycles each of
length at most 2k + 1.
P
Proof. 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 vi , vj be a pair of non-consecutive vertices in C. Then, either
(vi , vj ) ∈ A(T ) or (vj , vi ) ∈ A(T ). In any case, the arc e between vi and vj along with A(C)
forms a cycle C ′ of length less than ℓ with A(C ′ ) \ {e} ⊂ A(C). By our choice of C, this
b ∈ C. This property is true for the arc between
implies that e is an arc in some other cycle C

any pair of non-consecutive vertices in C. Therefore, we have 2ℓ − ℓ ≤ ℓ(k − 1) leading to
ℓ ≤ 2k + 1.
This lemma 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 a yes-instance of
ACT. This leads to the following quadratic Erdös-Pósa bound. Recall that for a digraph
D, fas(D) denotes the size of a minimum feedback arc set of D.
Theorem 2. For every non-negative integer k, every tournament T either contains k arcdisjoint cycles or has a feedback arc set of size O(k2 ).
Proof. Suppose C is a maximal set of arc-disjoint cycles in T . If |C| ≥ k, then the claim holds.
Otherwise, from Lemma 1, we may assume that each cycle in C is of length at most 2k + 1.
Let D denote the digraph obtained from T by deleting the arcs that are in some cycle in C.
Clearly, D is acyclic as C is maximal. Then, it follows that fas(T ) ≤ (2k + 1)(k − 1).
Next, we strengthen this result to arrive at a linear min-max bound. We will use the
following lemma in the process. For a digraph D, let Λ(D) denote the number of nonadjacent pairs of vertices in D. That is, Λ(D) is the number of pairs u, v of vertices of D
such that neither (u, v) ∈ A(D) nor (v, u) ∈ A(D).

4

Lemma 3. Let D be a triangle-free digraph in which for every pair u, v of distinct vertices,
at most one of (u, v) or (v, u) is in A(D). Then, fas(D) ≤ Λ(D).
Proof. We will prove the claim by induction on |V(D)|. The claim trivially holds for
|V(D)| ≤ 2. Suppose |V(D)| ≥ 3. First, we apply a simple preprocessing rule on D. If
D has a vertex v that either has no in-neighbours or has no out-neighbours, then we delete
v from D to get the digraph D ′ . Clearly, there is no cycle in D that contains v and thus
fas(D) = fas(D ′ ). Therefore, subsequently, we may assume that for every vertex v ∈ V(D),
N+ (v) 6= ∅ and N− (v) 6= ∅.
For a vertex v ∈ V(D), we define first(v) to be the number of induced paths of length
3 with v as the first vertex. Similarly, we define mid(v) to
P be the number ofPinduced paths
of length 3 with v as the second vertex. We claim that v∈V(D) first(v) = v∈V(D) mid(v).
Consider an induced path P = (u, v, w) of length 3 in D. Then, P contributes 1 to first(u)
and does not contribute to first(x) for any x 6= u. Further, P contributes 1Pto mid(v) and
does P
not contribute to mid(x)P
for any x 6= v. Therefore,
P contributes 1 to v∈V(D) first(v)
P
and v∈V(D) mid(v). Hence, v∈V(D) first(v) = v∈V(D) mid(v). It now follows that there
is a vertex u ∈ V(D) such that first(u) ≤ mid(u).
Define the sets Iu , Ou and Ru as Iu = N− (v), Ou = N+ (v) and Ru = V(D) \ (Iu ∪ Ou ).
That is, Iu is the set of in-neighbours of u, Ou is the set of out-neighbours of u and Ru
is the set of vertices that are not adjacent with u. Observe that Iu 6= ∅ and Ou 6= ∅.
Let D1 and D2 be the subgraphs D[Iu ∪ Ru ] and D[Ou ], respectively. Then, as D1 and
D2 are vertex-disjoint induced subgraphs of D, we have Λ(D) ≥ Λ(D1 ) + Λ(D2 ). Now,
any induced path P = (x, u, y) of length 3 in D with u as the second vertex satisfies the
property that x ∈ V(D1 ) and y ∈ V(D2 ). Further, (x, y), (y, x) ∈
/ A(D) due to the facts
that P is an induced path and D is triangle-free. Then, mid(u) is the number of pairs x, y
of non-adjacent vertices with x ∈ Iu , y ∈ Ou . Therefore, Λ(D) ≥ Λ(D1 ) + Λ(D2 ) + mid(u)
as Iu ⊆ V(D1 ), Ou ⊆ V(D2 ) and V(D1 ) ∩ V(D2 ) = ∅.
Let E denote the set of arcs (x, y) in D with x ∈ Ou and y ∈ Ru . Let F1 and F2 be
feedback arc sets of D1 and D2 , respectively. We claim that F = F1 ∪ F2 ∪ E is a feedback
arc set of D. If there is a cycle C in the graph obtained from D by removing arcs in F, then
C has an arc (p, q) with p ∈ V(D1 ), q ∈ V(D2 ) and an arc (r, s) with r ∈ V(D2 ), s ∈ V(D1 ).
However, as D has no triangle, any arc (x, y) with x ∈ V(D2 ) and y ∈ V(D1 ) satisfies
x ∈ Ou and y ∈ Ru . That is, (r, s) ∈ E leading to a contradiction. Therefore, it follows that
fas(D) ≤ fas(D1 ) + fas(D2 ) + |E|. Note that |E| = first(u) as any induced path P = (u, v, w)
starting at u satisfies v ∈ Ou , w ∈ Ru and any arc (x, y) with x ∈ Ou , y ∈ Ru corresponds
to an induced path (u, x, y) starting at u. Also, by the choice of u, we have first(u) ≤
mid(u). Therefore, fas(D) ≤ fas(D1 ) + fas(D2 ) + mid(u). By induction hypothesis, we have
fas(D1 ) ≤ Λ(D1 ) and fas(D2 ) ≤ Λ(D2 ). Hence, fas(D) ≤ Λ(D1 ) + Λ(D2 ) + mid(u). As
Λ(D) ≥ Λ(D1 ) + Λ(D2 ) + mid(u), we have fas(D) ≤ Λ(D).
This leads to the following main result of this section.
Theorem 4. For every non-negative integer k, every tournament T either contains k arcdisjoint triangles or has a feedback arc set of size at most 6(k − 1) that can be obtained in
polynomial time.
Proof. Suppose C is a maximal set of arc-disjoint triangles in T with |C| ≤ k − 1. 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). From Lemma 3, we have fas(D) ≤ 3(k − 1).
Also, if F is a feedback arc set of D, then F ∪ A(C) is a feedback arc set of T . Therefore,
fas(T ) ≤ 6(k − 1).
5

We will use this result crucially in showing that ACT can be solved in O⋆ (2O(k log k) )
time and admits a kernel with O(k) vertices.

4

Fixed-Parameter Tractability and Kernelization Complexity

In this section, we show that ACT is FPT and admits a polynomial kernel. We show that
the first result is a direct consequence of Lemma 1 and the second follows from Theorem 4.

4.1

An FPT Algorithm

Consider an instance I = (T, k) of ACT. Let n denote |V(T )| and m denote |A(T )|. Suppose
I is a yes-instance and C is a set of k arc-disjoint cycles in T . From Lemma 1, we may
assume that the total number of arcs that are in cycles in C is at most (2k + 1)k. Using
this observation, we proceed as follows. We color the arcs of T uniformly at random from
the color set [ℓ] where ℓ = 2k2 + k. Let χ : A(T ) → [ℓ] denote this coloring.
Proposition 5 ( [4]). If E is a subset of A(T ) of size ℓ, then the probability that the arcs
in E are colored with pairwise distinct colors is at least e−ℓ .
Next, we define the notion of a colorful solution for our problem.
Definition 4.1. (Colorful set of cycles) A set C of arc-disjoint cycles in T that satisfies
the property that for any two (not necessarily distinct) cycles C, C ′ ∈ C and for any two
distinct arcs e ∈ A(C), e ′ ∈ A(C ′ ), χ(e) 6= χ(e ′ ) holds is said to be a colorful set of cycles.
Rephrasing Proposition 5 in the context of our problem, we have the following observation.
Observation 6. If C is a solution of I with the property that for each C ∈ C, |C| ≤ 2k + 1,
then C is a colorful set of cycles in T with probability at least e−ℓ .
Armed with the guarantee that a solution (if one exists) of I is colorful with sufficiently
high probability, we focus on finding a colorful set of cycles in T .
Lemma 7. If T has a colorful set of k cycles, then such a set can be obtained in ℓ!nO(1)
time.
Proof. Consider a permutation σ of [ℓ]. For each i ∈ [k], let Dσi denote the subgraph of T
with V(Dσi ) = V(T ) and A(Dσi ) = A(T ) ∩ {(u, v) ∈ A(T ) | 2(i − 1)k + i ≤ σ(χ((u, v))) ≤
2k + 2(i − 1)k + i}. That is, A(Dσ1 ) is the set of arcs of T that are colored with the first
2k + 1 colors, A(Dσ2 ) is the set of arcs of T that are colored with the next 2k + 1 colors
and so on. For each i ∈ [k], let Cσi denote a cycle (if one exists) in Dσi . Let Cσ denote the
set {Cσi | i ∈ [k]}. For each permutation σ of [ℓ], we compute the corresponding set Cσ . If
T has a colorful set of k cycles, then |Cπ | = k for some permutation π of [ℓ]. Therefore, by
computing Cπ for every permutation π of [ℓ], we can obtain a colorful set of k cycles in T
(if one exists).
Using the standard technique of derandomization of color coding based algorithms [4,
15, 27], we have the following result by taking m = |A(T )|.
Proposition 8 ( [4, 15, 27]). Given integers m, ℓ ≥ 1, there is a family Fm,ℓ of coloring
functions χ : A(T ) → [ℓ] of size eℓ ℓO(log ℓ) log m that can be constructed in eℓ ℓO(log ℓ) m log m
time satisfying the following property: for every set E ⊆ A(T ) of size ℓ, there is a function
χ ∈ Fm,ℓ such that χ(e) 6= χ(e ′ ) for any two distinct arcs e, e ′ ∈ E.
6

Then, we have the following result.
Theorem 9. ACT can be solved in O⋆ (2O(k

2

log k) )

time.

Proof. Consider an instance I = (T, k) of ACT. Let ℓ = 2k2 + k. First, we compute the
family Fm,ℓ of eℓ ℓO(log ℓ) log m coloring functions using Proposition 8 where m is the number
of arcs in T . Then, for each coloring function χ : A(T ) → [ℓ] in Fm,ℓ , we determine if T
has a colorful set of k cycles using Lemma 7. Due to the properties of Fm,ℓ guaranteed by
Proposition 8, it follows that I is a yes-instance if and only if T has a set of k cycles that
is colorful with respect to at least one of the coloring functions. The overall running time
2
is O⋆ (2O(k log k) ).
Observe that the running time of the algorithm to find a colorful set of k cycles can
be improved to 2ℓ nO(1) by employing a standard dynamic programming scheme. This will
2
result in an O⋆ (2O(k ) ) time algorithm for ACT. However, we skip the details of the same
as we will describe an O⋆ (2O(k log k) ) time algorithm for ACT in Section 5.

4.2

A Polynomial Kernel

Now, we show that ACT admits a polynomial kernel. We use Theorem 4 to describe a
quadratic vertex kernel.
Theorem 10. ACT admits a kernel with O(k2 ) vertices.
Proof. Let (T, k) denote an instance of ACT. From Theorem 4, we know that T has either
k arc-disjoint triangles or a feedback arc set F of size at most 6(k − 1). In the former case,
we return a trivial yes-instance of constant size as the kernel. In the latter case, S = V(F)
is a feedback vertex set of T of size at most 12k. Let D denote the transitive tournament
T − S and δ denote its unique topological ordering. Observe that for each v ∈ S, the
subtournament of T induced by V(D) ∪ {v} is also transitive. If there is a cycle in D ∪ {v},
then this cycle (which is also a cycle in T ) has no arc from F leading to a contradiction.
For each v ∈ S, let R(v) be the set of first (with respect to δ) 2k + 1 vertices in N+ (v).
Let T ′ be the subtournament of T induced by S ∪ {R(v) | v ∈ S}. Clearly, T ′ has O(k2 )
vertices. We claim that (T ′ , k) is the required kernel of (T, k). We need to show that T has
k arc-disjoint cycles if and only if T ′ has k arc-disjoint cycles. The reverse direction of the
claim holds trivially. Let us now prove the forward direction. Suppose
T has a set of k arcP
disjoint cycles. Among all such sets, let C be one that minimizes C∈C |V(C)∩(V(T )\V(T ′ ))|.
Suppose there is a cycle C in C that is not in T ′ . Then, there is a vertex vi ∈ V(C) that
is not in T ′ . As argued earlier, any cycle in T has at least two vertices from S. Let x and
y be two such vertices in C where (x, v1 , . . . , vi , . . . , vq , y) is a path in C from x to y with
internal vertices from V(D).
The subtournaments Tb = D ∪ {x} and Te = D ∪ {y} are transitive with unique topological
orderings σ and π, respectively. Observe that for all distinct u, v ∈ V(D), π(u) < π(v) if
and only if σ(u) < σ(v). As (x, v1 , . . . , vi , . . . , vq ) is a path in Tb, it follows that σ(x) < σ(vj )
for each j ∈ [q]. Similarly, as (v1 , . . . , vi , . . . , vq , y) is a path in Te, we have π(y) > π(vj ) for
each j ∈ [q]. As vi ∈
/ V(T ′ ), it follows that vi ∈
/ R(x) and |R(x)| = 2k + 1. Then, there is
at least one vertex z in R(x) such that the arcs (x, z) and (z, y) are not in any cycle in C.
Now, σ(z) < σ(vi ) as z, vi ∈ N+ (x), vi ∈
/ R(x) and z ∈ R(x). Thus, we have π(z) < π(vi ).
As π(vi ) < π(y), it follows that (z, y) ∈ A(T ) as π(z) < π(y). Then, by replacing the path
(x, v1P
, . . . , vi , . . . , vq , y) by (x, z, y), we
obtain another set C ′ of k arc-disjoint cycles such
P
that C∈C |V(C) ∩ (V(T ) \ V(T ′ ))| > C∈C ′ |V(C) ∩ (V(T ) \ V(T ′ ))|. However, this leads to
a contradiction by the choice of C.
7

5

An Improved FPT Algorithm and A Smaller Kernel

Next, we show that ACT can be solved in O⋆ (2O(k log k) ) time and admits a kernel with
O(k) vertices.

5.1

A Linear Vertex Kernel

We show that the linear kernelization described in [9] for Feedback Arc Set in Tournaments also leads to a linear kernelization for our problem. In order to describe the kernel,
we need to state some terminology defined in [9]. Let T be a tournament on n vertices.
First, we apply the following reduction rule.
Reduction Rule 5.1. If a vertex v is not in any 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 some terminology and a lemma known from [9]. For
an ordering σ of V(T ), let Tσ denote the tournament T whose vertices are ordered according
to σ. Clearly, V(Tσ ) = V(T ) and A(Tσ ) = A(T ) since T and Tσ denote the same tournament.
An arc (u, v) ∈ A(Tσ ) is called a back arc if σ(u) > σ(v) and it is called a forward arc
otherwise. An interval is a consecutive set of vertices in Tσ .
Lemma 11 ( [9]). 1 Let Tσ be an ordered tournament on which Reduction Rule 5.1 is not
applicable. Let B denote the set of back arcs in Tσ and E denote the set of arcs in Tσ with
endpoints in different intervals. If |V(Tσ )| ≥ 2|B| + 1, then there exists a partition J of
V(Tσ ) into intervals with the following properties that can be computed in polynomial time.
• There is at least one arc e = (u, v) ∈ A(T ) with e ∈ B ∩ E.
• There are |B ∩ E| arc-disjoint cycles using only arcs in E.
Our reduction rule that is based on this lemma is as follows.
Reduction Rule 5.2. Let Tσ be an ordered tournament on which Reduction Rule 5.1 is
not applicable. Let B denote the set of back arcs in Tσ and E denote the set of arcs in Tσ
with endpoints in different intervals. Let J be a partition of V(Tσ ) into intervals satisfying
the properties specified in Lemma 11. Reverse all arcs in B ∩ E and decrease k by |B ∩ E|.
Lemma 12. Reduction Rule 5.2 is safe.
Proof. Let Tσ′ be the tournament obtained from Tσ by reversing all arcs in B∩E. Suppose Tσ′
has k − |B ∩ 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 back arc with endpoints
in different intervals. Indeed, if a cycle in Tσ′ uses a forward (back) 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 (u, v) ∈ E, neither (u, v) nor (v, u) is used in these k − |B ∩ E|
cycles. Hence, these k − |B ∩ E| cycles in Tσ′ are also cycles in Tσ . Then, we can add a set of
|B ∩ E| cycles obtained from the second property of Lemma 11 to these k − |B ∩ E| cycles to
get k cycles in Tσ . Conversely, consider a set of k cycles in Tσ . As argued earlier, we know
that the number of cycles that have an arc that is in E is at most |B ∩ E|. The remaining
cycles (at least k − |B ∩ E| of them) do not contain any arc that is in E, in particular, they
do not contain any arc from B ∩ E. Therefore, these cycles are also cycles in Tσ′ .
1
Lemma 11 is Lemma 3.9 of [9] that has been rephrased to avoid the use of several definitions and
terminology introduced in [9].

8

Theorem 13. ACT admits a kernel with O(k) vertices.
Proof. Let (T, k) denote the instance obtained from the input instance by applying Reduction Rule 5.1 exhaustively. From Lemma 4, we know that either T has k arc-disjoint
triangles or has a feedback arc set of size at most 6(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 feedback arc set of size at most 6(k − 1) of T . Let σ denote a
topological ordering of the vertices of the directed acyclic graph T − F. As V(T − F) = V(T ),
σ is an ordering of V(T ) such that Tσ has at most 6(k − 1) back arcs. If |V(Tσ )| ≥ 12k − 11,
then from Lemma 11, there is a partition of V(Tσ ) into intervals with the specified properties. Therefore, Reduction Rule 5.2 is applicable (and the parameter drops by at least 1).
When we obtain an instance where neither of the Reduction Rules 5.1 and 5.2 is applicable,
it follows that the tournament in that instance has at most 12k vertices.

5.2

A Faster FPT Algorithm

Here, we show that ACT can be solved in O⋆ (2O(k log k) ) time. The idea is to reduce the
problem to the following Arc-Disjoint Paths problem in directed acyclic graphs.
Arc-Disjoint Paths
Parameter: k
Input: A digraph D on n vertices and k ordered pairs (s1 , t1 ), . . . , (sk , tk ) of vertices
of D.
Question: Do there exist arc-disjoint paths P1 , . . . , Pk in D such that Pi is a path from
si to ti for each i ∈ [k]?
On directed acyclic graphs, Arc-Disjoint Paths is known to be NP-complete [18],
W[1]-hard [30] and solvable in nO(k) time [21]. Despite its fixed-parameter intractability,
we will show that we can use the nO(k) algorithm to describe another (and faster) FPT
algorithm for ACT.
Theorem 14. ACT can be solved in O⋆ (2O(k log k) ) time.
b
Proof. Consider an instance (T, k) of ACT. Using Theorem 13, we obtain a kernel I = (Tb, k)
b
b
such that T has O(k) vertices. Further, k ≤ k. By definition, (T, k) is a yes-instance if and
only if (Tb, b
k) is a yes-instance. Using Theorem 4, we know that Tb either contains b
k arcb
disjoint triangles or has a feedback arc set of size at most 6(k − 1) that can be obtained in
polynomial time. If Theorem 4 returns a set of b
k arc-disjoint triangles in Tb, then we declare
that (T, k) is a yes-instance.
Otherwise, let b
F be the feedback arc set of size at most 6(b
k − 1) returned by Theorem
4. Let D denote the (acyclic) digraph obtained from Tb by deleting b
F. Observe that D has
b
b
O(k) vertices. Suppose T has a set C = {C1 , . . . , Cbk } of k arc-disjoint cycles. For each C ∈ C,
we know that A(C) ∩ b
F 6= ∅ as b
F is a feedback arc set of Tb. We can guess that subset F of b
F
b
such that F = F ∩ A(C). Then, for each cycle Ci ∈ C, we can guess the arcs Fi 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 b
k sets, F1 to Fbk and the set {σ1 , . . . , σbk } of permutations where σi is
a permutation of Fi for each i ∈ [b
k]. Any cycle Ci that has Fi ⊆ F contains a (v, x)-path
between every pair (u, v), (x, y) of consecutive arcs of Fi with arcs from A(D). That is,
−1
there is a path from head(σ−1
i (j)) and tail(σi ((j + 1) mod |Fi |)) with arcs from D for each
j ∈ [|Fi |]. The total number of such paths in these b
k cycles is O(|F|) and the arcs of these
paths are contained in D which is a (simple) directed acyclic graph.
b
The number of choices for F is 2|F| and the number of choices for a partition F =
b
b
{F1 , . . . , Fbk } of F and a set X = {σ1 , . . . , σbk } of permutations is 2O(|F| log |F|) . Once such a
9

choice is made, the problem of finding b
k arc-disjoint cycles in Tb reduces to the problem of
k and for each
k arc-disjoint cycles C = {C1 , . . . , Cbk } in Tb such that for each 1 ≤ i ≤ b
finding b
−1
−1
1 ≤ j ≤ |Fi |, Ci has a path Pij between head(σi (j)) and tail(σi ((j + 1) mod |Fi |)) with
arcs from D = Tb − b
F. This problem is essentially finding r = O(|b
F|) arc-disjoint paths in
D and can be solved in |V(D)|O(r) time using the algorithm in [21]. Therefore, the overall
running time of the algorithm is O⋆ (2O(k log k) ) as |V(D)| = O(k) and r = O(k).

6

Concluding Remarks

We initiated the parameterized complexity study of the Arc-Disjoint Cycle Packing
problem on tournaments. We showed that it is FPT when parameterized by the solution
size and admits a linear vertex kernel. However, the classical complexity status of the
problem is still open, i.e, we do not know if it is NP-hard or not. Resolving the same is a
natural future research direction. We conjecture that it is indeed NP-hard. Note that the
classical complexity status of the dual problem (Feedback Arc Set in Tournaments)
was a long-standing open problem until it was shown to be NP-hard [2, 12, 14].

References
[1] F. N. Abu-Khzam. An Improved Kernelization Algorithm for r-Set Packing. Information Processing Letters, 110(16):621–624, 2010.
[2] N. Alon. Ranking Tournaments. SIAM Journal of Discrete Mathematics, 20(1):137–
142, 2006.
[3] N. Alon, D. Lokshtanov, and S. Saurabh. Fast FAST. In 36th International Colloquium
on Automata, Languages, and Programming (ICALP) Proceedings, Part I, pages 49–58,
2009.
[4] N. Alon, R. Yuster, and U. Zwick. Color-Coding. Journal of the ACM, 42(4):844–856,
1995.
[5] J. Bang-Jensen and G. Gutin. Paths, Trees and Cycles in Tournaments. Congressus
Numerantium, 115:131–170, 1996.
[6] J. Bang-Jensen and G. Gutin.
Springer-Verlag London, 2009.

Digraphs: Theory, Algorithms and Applications.

[7] F. Barbero, C. Paul, and M. Pilipczuk. Strong Immersion is a Well-quasi-ordering for
Semi-complete Digraphs. CoRR, abs/1707.03563, 2017.
[8] S. Bessy, M. Bougeret, and J. Thiebaut. Triangle Packing in (sparse) Tournaments:
Approximation and Kernelization. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA), pages 1–23, 2017.
[9] S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh, and S. Thomassé.
Kernels for Feedback Arc Set in Tournaments. Journal of Computer and System Sciences, 77(6):1071–1078, 2011.
[10] H. L. Bodlaender. On Disjoint Cycles. International Journal of Foundations of Computer Science, 5(1):59–68, 1994.

10

[11] H. L. Bodlaender, S. Thomassé, and A. Yeo. Kernel Bounds for Disjoint Cycles and
Disjoint Paths. Theoretical Computer Science, 412(35):4570–4578, 2011.
[12] P. Charbit, S. Thomassé, and A. Yeo. The Minimum Feedback Arc Set Problem
is NP-Hard for Tournaments. Combinatorics, Probability and Computing, 16(1):1–4,
2007.
[13] M. Chudnovsky and P. Seymour. A Well-quasi-order for Tournaments. Journal of
Combinatorial Theory, Series B, 101(1):47–53, 2011.
[14] V. Conitzer. Computing Slater Rankings Using Similarities Among Candidates. In
21st National Conference on Artificial Intelligence - Volume 1, pages 613–619, 2006.
[15] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk,
M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
[16] R. G. Downey and M. R. Fellows.
Springer-Verlag London, 2013.

Fundamentals of Parameterized Complexity.

[17] P. Erdös and L. Pósa. On Independent Circuits Contained in a Graph. Canadian
Journal of Mathematics, 17:347–352, 1965.
[18] S. Even, A. Itai, and A. Shamir. On the Complexity of Timetable and Multicommodity
Flow Problems. SIAM Journal on Computing, 5(4):691–703, 1976.
[19] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006.
[20] F. V. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh. Fast Local Search Algorithm
for Weighted Feedback Arc Set in Tournaments. In Proceedings of the 24th AAAI
Conference on Artificial Intelligence, pages 65–70, 2010.
[21] S. Fortune, J. Hopcroft, and J. Wyllie. The Directed Subgraph Homeomorphism
Problem. Theoretical Computer Science, 10(2):111–121, 1980.
[22] M. Karpinski and W. Schudy. Faster Algorithms for Feedback Arc Set Tournament,
Kemeny Rank Aggregation and Betweenness Tournament. In 21st International Symposium on Algorithms and Computation (ISAAC), pages 3–14. Springer Berlin Heidelberg, 2010.
[23] M. Krivelevich, Z. Nutov, M. R. Salavatipour, J. V. Yuster, and R. Yuster. Approximation Algorithms and Hardness Results for Cycle Packing Problems. ACM Transactions
on Algorithms, 3(4), 2007.
[24] T. Le, D. Lokshtanov, S. Saurabh, S. Thomassé, and M. Zehavi. Subquadratic Kernels
for Implicit 3-Hitting Set and 3-Set Packing Problems. In Proceedings of the 29th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 331–342, 2018.
[25] D. Lokshtanov, A. Mouawad, S. Saurabh, and M. Zehavi. Packing Cycles Faster
Than Erdös-Pósa. In 44th International Colloquium on Automata, Languages, and
Programming (ICALP), pages 71:1–71:15, 2017.
[26] J.W. Moon. Topics on Tournaments. Holt, Rinehart and Winston, New York, 1968.
[27] M. Naor, L. J. Schulman, and A. Srinivasan. Splitters and Near-optimal Derandomization. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages
182–191, 1995.
11

[28] V. Raman and S. Saurabh. Parameterized Algorithms for Feedback Set problems and
their Duals in Tournaments. Theoretical Computer Science, 351(3):446–458, 2006.
[29] N. Robertson and P.D. Seymour. Graph Minors. XX. Wagner’s Conjecture. Journal
of Combinatorial Theory, Series B, 92(2):325–357, 2004.
[30] A. Slivkins. Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic
Graphs. SIAM Journal on Discrete Mathematics, 24(1):146–157, 2010.
[31] E. Speckenmeyer. On Feedback Problems in Digraphs. In 15th International Workshop
on Graph-Theoretic Concepts in Computer Science, pages 218–231. Springer Berlin
Heidelberg, 1990.

12

