<figure><img src="image_1.png" /></figure>

HAL
open science

# Triangle packing in (sparse) tournaments: approximation and kernelization

Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut

► To cite this version:

Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut. Triangle packing in (sparse) tournaments: approximation and kernelization. ESA 2017 - 25th Annual European Symposium on Algorithms, Sep 2017, Vienne, Austria. pp.14:1–14:13, 10.4230/LIPIcs.ESA.2017.14 . lirmm-01550313

HAL Id: lirmm-01550313

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01550313

Submitted on 29 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Triangle packing in (sparse) tournaments: approximation and kernelization*.

Stéphane Bessy¹, Marin Bougeret², and Jocelyn Thiebaut³

1 Université de Montpellier - CNRS, LIRMM bessy@lirmm.fr

2 Université de Montpellier - CNRS, LIRMM bougeret@lirmm.fr

3 Université de Montpellier - CNRS, LIRMM thiebaut@lirmm.fr

## Abstract

Given a tournament $\mathcal{T}$ and a positive integer $k$, the $C_3$-PACKING-T problem asks if there exists a least $k$ (vertex-)disjoint directed 3-cycles in $\mathcal{T}$. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly $C_3$-PACKING-T did not receive a lot of attention in the literature. We show that it does not admit a PTAS unless P=NP, and so is NP-complete, even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. Focusing on sparse tournaments we provide a $(1+\frac{6}{c-1})$ approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have “length” at least $c$. Concerning kernelization, we show that $C_3$-PACKING-T admits a kernel with $O(m)$ vertices, where $m$ is the size of a given feedback arc set. In particular, we derive a $O(k)$ vertices kernel for $C_3$-PACKING-T when restricted to sparse instances. On the negative size, we show that $C_3$-PACKING-T does not admit a kernel of (total bit) size $O(k^{2-\epsilon})$ unless NP $\subseteq$ coNP/Poly. The existence of a kernel in $O(k)$ vertices for $C_3$-PACKING-T remains an open question.

**1998 ACM Subject Classification** G.2.2 Graph Theory - Graph algorithms

**Keywords and phrases** Tournament, triangle packing, feedback arc set, approximation and parameterized algorithms

**Digital Object Identifier** 10.4230/LIPICs.ESA.2017.

# 1 Introduction and related work

## Tournament

A tournament $\mathcal{T}$ on $n$ vertices is an orientation of the edges of the complete undirected graph $K_n$. Thus, given a tournament $\mathcal{T} = (V, A)$, where $V = \{v_i, i \in [n]\}$, for each $i, j \in [n]$, either $v_i v_j \in A$ or $v_j v_i \in A$. A tournament $\mathcal{T}$ can alternatively be defined by an ordering $\sigma(\mathcal{T}) = (v_1, \dots, v_n)$ of its vertices and a set of backward arcs $\overleftarrow{A}_{\sigma(\mathcal{T})}$ (which will be denoted $\overleftarrow{A}(\mathcal{T})$ as the considered ordering is not ambiguous), where each arc $a \in \overleftarrow{A}(\mathcal{T})$ is of the form $v_{i_1} v_{i_2}$ with $i_2 < i_1$. Indeed, given $\sigma(\mathcal{T})$ and $\overleftarrow{A}(\mathcal{T})$, we can define $V = \{v_i, i \in [n]\}$ and $A = \overleftarrow{A}(\mathcal{T}) \cup \overrightarrow{A}(\mathcal{T})$ where $\overrightarrow{A}(\mathcal{T}) = \{v_{i_1} v_{i_2} : (i_1 < i_2) \text{ and } v_{i_2} v_{i_1} \notin \overleftarrow{A}(\mathcal{T})\}$ is the set of forward arcs of $\mathcal{T}$ in the given ordering $\sigma(\mathcal{T})$. In the following, $(\sigma(\mathcal{T}), \overleftarrow{A}(\mathcal{T}))$ is called a linear representation of the tournament $\mathcal{T}$. For a backward arc $e = v_j v_i$ of $\sigma(\mathcal{T})$ the span value of $e$ is $j - i - 1$. Then $\minspan(\sigma(\mathcal{T}))$ (resp. $\maxspan(\sigma(\mathcal{T}))$) is simply the minimum (resp. maximum) of the span values of the backward arcs of $\sigma(\mathcal{T})$.

<figure><img src="image_3.png" /></figure>

<footnote>* This is the extended version of the corresponding ESA 2017 conference paper</footnote>
## XX:2 Triangle packing in (sparse) tournaments: approximation and kernelization.

A set $A' \subseteq A$ of arcs of $\mathcal{T}$ is a feedback arc set (or FAS) of $\mathcal{T}$ if every directed cycle of $\mathcal{T}$ contains at least one arc of $A'$. It is clear that for any linear representation $(\sigma(\mathcal{T}), \tilde{A}(\mathcal{T}))$ of $\mathcal{T}$ the set $\tilde{A}(\mathcal{T})$ is a FAS of $\mathcal{T}$. A tournament is *sparse* if it admits a FAS which is a matching. We denote by $C_3$-PACKING-T the problem of packing the maximum number of vertex disjoint triangles in a given tournament, where a triangle is a directed 3-cycle. More formally, an input of $C_3$-PACKING-T is a tournament $\mathcal{T}$, an output is a set (called a *triangle packing*) $S = \{t_i, i \in [|S|]\}$ where each $t_i$ is a triangle and for any $i \neq j$ we have $V(t_i) \cap V(t_j) = \emptyset$, and the objective is to maximize $|S|$. We denote by $\text{opt}(\mathcal{T})$ the optimal value of $\mathcal{T}$. We denote by $C_3$-PERFECT-PACKING-T the decision problem associated to $C_3$-PACKING-T where an input $\mathcal{T}$ is positive iff there is a triangle packing $S$ such that $V(S) = V(\mathcal{T})$ (which is called a *perfect triangle packing*).

### Related work

We refer the reader to Appendix where we recall the definitions of the problems mentioned below as well as the standard definitions about parameterized complexity and approximation. A first natural related problem is 3-SET-PACKING as we can reduce $C_3$-PACKING-T to 3-SET-PACKING by creating an hyperedge for each triangle.

**Classical complexity / approximation.** It is known that $C_3$-PACKING-T is polynomial if the tournament does not contain the three forbidden sub-tournaments described in [5]. From the point of view of approximability, the best approximation algorithm is the $\frac{4}{3}+\epsilon$ approximation of [7] for 3-SET-PACKING, implying the same result for $K_3$-PACKING and $C_3$-PACKING-T. Concerning negative results, it is known [10] that even $K_3$-PACKING is MAX SNP-hard on graphs with maximum degree four. We can also mention the related "dual" problem FAST and FVST that received a lot of attention with for example the NP-hardness and PTAS for FAS in [6] and [13] respectively, and the $\frac{7}{3}$ approximation and inapproximability results for FVST in [14].

**Kernelization.** We precise that the implicitly considered parameter here is the size of the solution. There is a $O(k^2)$ vertex kernel for $K_3$-PACKING in [15], and even a $O(k^2)$ vertex kernel for 3-SET-PACKING in [1], which is obtained by only removing vertices of the ground set. This remark is important as it directly implies a $O(k^2)$ vertex kernel for $C_3$-PACKING-T (see Section 4). Let us now turn to negative results. There is a whole line of research dedicated to finding lower bounds on the size of polynomial kernels. The main tool involved in these bounds is the weak composition introduced in [11] (whose definition is recalled in Appendix). Weak composition allowed several almost tight lower bounds, with for example the $O(k^{d-\epsilon})$ for $d$-SET-PACKING and $O(k^{d-4-\epsilon})$ for $K_d$-PACKING of [11]. These results where improved in [8] to $O(k^{d-\epsilon})$ for PERFECT $d$-SET-PACKING, $O(k^{d-1-\epsilon})$ for $K_d$-PACKING, and leading to $O(k^{2-\epsilon})$ for PERFECT $K_3$-PACKING. Notice that negative results for the "perfect" version of problems (where parameter $k = \frac{n}{d}$, where $d$ is the number of vertices of the packed structure) are stronger than for the classical version where $k$ is arbitrary. Kernel lower bound for these "perfect" versions is sometimes referred as sparsification lower bounds.

### Our contributions

Our objective is to study the approximability and kernelization of $C_3$-PACKING-T. On the approximation side, a natural question is a possible improvement of the $\frac{4}{3}+\epsilon$ approximation implied by 3-SET-PACKING. We show that, unlike FAST, $C_3$-PACKING-T does not admit
a PTAS unless P=NP, even if the tournament is sparse. We point out that, surprisingly, we were not able to find any reference establishing a negative result for $C_3$-PACKING-T, even for the NP-hardness. As these results show that there is not much room for improving the approximation ratio, we focus on sparse tournaments and followed a different approach by looking for a condition that would allow ratio arbitrarily close to 1. In that spirit, we provide a $(1 + \frac{6}{c-1})$ approximation algorithm for sparse tournaments having a linear representation with minspan at least c. Concerning kernelization, we complete the panorama of sparsification lower bounds of [12] by proving that $C_3$-PERFECT-PACKING-T does not admit a kernel of (total bit) size $O(n^{2-\epsilon})$ unless NP $\subseteq$ coNP/Poly. This implies that $C_3$-PACKING-T does not admit a kernel of (total bit) size $O(k^{2-\epsilon})$ unless NP $\subseteq$ coNP/Poly. We also prove that $C_3$-PACKING-T admits a kernel of $O(m)$ vertices, where $m$ is the size of a given FAS of the instance, and that $C_3$-PACKING-T restricted to sparse instances has a kernel in $O(k)$ vertices (and so of total size bit $O(k \log(k)))$. The existence of a kernel in $O(k)$ vertices for the general $C_3$-PACKING-T remains our main open question.

## 2 Specific notations and observations

Given a linear representation $(\sigma(\mathcal{T}), \overleftarrow{A}(\mathcal{T}))$ of a tournament $\mathcal{T}$, a triangle $t$ in $\mathcal{T}$ is a triple $t = (v_{i_1}, v_{i_2}, v_{i_3})$ with $i_l < i_{l+1}$ such that either $v_{i_3}v_{i_1} \in \overleftarrow{A}(\mathcal{T})$, $v_{i_3}v_{i_2} \notin \overleftarrow{A}(\mathcal{T})$ and $v_{i_2}v_{i_1} \notin \overleftarrow{A}(\mathcal{T})$ (in this case we call $t$ a triangle with backward arc $v_{i_3}v_{i_1}$), or $v_{i_3}v_{i_1} \notin \overleftarrow{A}(\mathcal{T})$, $v_{i_3}v_{i_2} \in \overleftarrow{A}(\mathcal{T})$ and $v_{i_2}v_{i_1} \in \overleftarrow{A}(\mathcal{T})$ (in this case we call $t$ a triangle with two backward arcs $v_{i_3}v_{i_2}$ and $v_{i_2}v_{i_1}$).

Given two tournaments $\mathcal{T}_1, \mathcal{T}_2$ defined by $\sigma(\mathcal{T}_l)$ and $\overleftarrow{A}(\mathcal{T}_l)$ we denote by $\mathcal{T} = \mathcal{T}_1\mathcal{T}_2$ the tournament called the concatenation of $\mathcal{T}_1$ and $\mathcal{T}_2$, where $\sigma(\mathcal{T}) = \sigma(\mathcal{T}_1)\sigma(\mathcal{T}_2)$ is the concatenation of the two sequences, and $\overleftarrow{A}(\mathcal{T}) = \overleftarrow{A}(\mathcal{T}_1) \cup \overleftarrow{A}(\mathcal{T}_2)$. Given a tournament $\mathcal{T}$ and a subset of vertices $X$, we denote by $\mathcal{T} \setminus X$ the tournament $\mathcal{T}[V(\mathcal{T}) \setminus X]$ induced by vertices $V(\mathcal{T}) \setminus X$, and we call this operation *removing $X$ from $\mathcal{T}$*. Given an arc $a = uv$ we define $h(a) = v$ as the head of $a$ and $t(a) = u$ as the tail of $a$. Given a linear representation $(V(\mathcal{T}), \overleftarrow{A}(\mathcal{T}))$ and an arc $a \in \overleftarrow{A}(\mathcal{T})$, we define $s(a) = \{v : h(a) < v < t(a)\}$ as the *span* of $a$. Notice that the span value of $a$ is then exactly $|s(a)|$.

Given a linear representation $(V(\mathcal{T}), \overleftarrow{A}(\mathcal{T}))$ and a vertex $v \in V(\mathcal{T})$, we define the degree of $v$ by $d(v) = (a, b)$, where $a = |\{vu \in \overleftarrow{A}(\mathcal{T}) : u < v\}|$ is called the *left degree* of $v$ and $b = |\{uv \in \overleftarrow{A}(\mathcal{T}) : u > v\}|$ is called the *right degree* of $v$. We also define $V_{(a,b)} = \{v \in V(\mathcal{T}) | d(v) = (a, b)\}$. Given a set of pairwise distinct pairs $D$, we denote by $C_3$-PACKING-T$^D$ the problem $C_3$-PACKING-T restricted to tournaments such that there exists a linear representation where $d(v) \in D$ for all $v$. Notice that when $D_M = \{(0,1), (1,0), (0,0)\}$, instances of $C_3$-PACKING-T$^D$ are the sparse tournaments.

Finally let us point out that it is easy to decide in polynomial time if a tournament is sparse or not, and if so, to give a linear representation whose FAS is a matching. The corresponding algorithm is detailed in Appendix in Lemma 23. Thus, in the following, when considering a sparse tournament we will assume that a linear ordering of it where backward arcs form a matching is also given.

## 3 Approximation for sparse tournaments

### 3.1 APX-hardness for sparse tournaments

In this subsection we prove that $C_3$-PACKING-T$^D$ is APX-hard by providing a $L$-reduction (see Definition 17 in appendix) from Max 2-SAT(3), which is known to be APX-hard [2, 3].
XX:4 Triangle packing in (sparse) tournaments: approximation and kernelization.

Recall that in the MAX 2-SAT(3) problem where each clause contains exactly 2 variables and each variable appears in at most 3 clauses (and at most twice positively and once negatively).

**Definition of the reduction** Let $\mathcal{F}$ be an instance of MAX 2-SAT(3). In the following, we will denote by $n$ the number of variables in $\mathcal{F}$ and $m$ the number of clauses. Let $\{x_i, 1 \in [n]\}$ be the set of variables of $\mathcal{F}$ and $\{C_j, j \in [m]\}$ its set of clauses.

We now define a reduction $f$ which maps an instance $\mathcal{F}$ of MAX 2-SAT(3) to an instance $\mathcal{T}$ of $C_3$-PACKING-$T^{D_M}$. For each variable $x_i$ with $i \in [n]$, we create a tournament $L_i$ as follows and we call it *variable gadget*. We refer the reader to Figure 1 where an example of variable gadget is depicted. Let $\sigma(L_i) = (X_i, X'_i, \overline{X}_i, \overline{X}'_i, \{\beta_i\}, \{\beta'_i\}, A_i, B_i, \{\alpha_i\}, A'_i, B'_i)$. We define $C = \{X_i, X'_i, \overline{X}_i, \overline{X}'_i, A_i, B_i, A'_i, B'_i\}$. All sets of $C$ have size 4. We denote $X_i = (x_i^1, x_i^2, x_i^3, x_i^4)$, and we extend the notation in a straightforward manner to the other others sets of $C$. Let us now define $\overleftarrow{A}(L_i)$. For each set of $C$, we add a backward arc whose head is the first element and the tail is the last element (for example for $X_i$ we add the arc $x_i^4x_i^1$). Then, we add to $\overleftarrow{A}(L_i)$ the set $\{e_1, e_2, e_3, e_4\}$ where $e_1 = x_i^3a_i^3$, $e_2 = x_i'^3a_i'^3$, $e_3 = x_i^3b_i^3$, $e_4 = \overline{x_i'^3b_i'^3}$ and the set $\{m_1, m_2\}$ where $m_1 = a_i'^2a_i^2$, $m_2 = b_i'^2b_i^2$ called the two *medium arcs* of the variable gadget. This completes the description of tournament $L_i$. Let $L = L_1 \dots L_n$ be the concatenation of the $L_i$.

<figure><img src="image_4.png" /><figcaption>Figure 1 Example of a variable gadget $L_i$.</figcaption></figure>

For each clause $C_j$ with $j \in [1, m]$, we create a tournament $K_j$ with ordering $\sigma(K_j) = (\theta_j, d_j^1, c_j^1, c_j^2, d_j^2)$ and $\overleftarrow{A}(K_j) = \{d_j^2d_j^1\}$. We also define $K = K_1 \dots K_m$. Let us now define $\mathcal{T} = LK$. We add to $\overleftarrow{A}(\mathcal{T})$ the following backward arcs from $V(K)$ to $V(L)$. If $C_j = l_{i_1} \lor l_{i_2}$ is a clause in $\mathcal{F}$ then we add the arcs $c_j^1v_{i_1}, c_j^2v_{i_2}$ where $v_{i_c}$ is the vertex in $\{x_{i_c}^2, x_{i_c}'^2, \overline{x_{i_c}^2}\}$ corresponding to $l_{i_c}$: if $l_{i_c}$ is a positive occurrence of variable $i_c$ we chose $v_{i_c} \in \{x_{i_c}^2, x_{i_c}'^2\}$, otherwise we chose $v_{i_c} = \overline{x_{i_c}^2}$. Moreover, we chose vertices $v_{i_c}$ in such a way that for any $i \in [n]$, for each $v \in \{x_i^2, x_i'^2, \overline{x_i^2}\}$ there exists a unique arc $a \in \overleftarrow{A}(\mathcal{T})$ such that $h(a) = v$. This is always possible as each variable has at most two positive occurrences and one negative occurrence. Thus, $x_i^2$ represent the first positive occurrence of variable $i$, and $x_i'^2$ the second one. We refer the reader to Figure 2 where an example of the connection between variable and clause gadget is depicted.

<figure><img src="image_5.png" /><figcaption>Figure 2 Example showing how a clause gadget is attached to variable gadgets.</figcaption></figure>
Notice that vertices of $\overline{X}'_i$ are never linked to the clauses gadget. However, we need this set to keep the variable gadget symmetric so that setting $x_i$ to true or false leads to the same number of triangles inside $L_i$. This completes the description of $\mathcal{T}$. Notice that the degree of any vertex is in $\{(0,1), (1,0), (0,0)\}$, and thus $\mathcal{T}$ is an instance of $C_3$-PACKING-$\mathcal{T}^{D_M}$.

Let us now distinguish three different types of triangles in $\mathcal{T}$. A triangle $t = (v_1, v_2, v_3)$ of $\mathcal{T}$ is called an outer triangle iff $\exists j \in [m]$ such that $v_2 = \theta_j$ and $v_3 = c_j^l$ (implying that $v_1 \in V(L)$), variable inner iff $\exists i \in [n]$ such that $V(t) \subseteq V(L_i)$, and clause inner iff $\exists j \in [m]$ such that $V(t) \subseteq V(K_j)$. Notice that a triangle $t = (v_1, v_2, v_3)$ of $\mathcal{T}$ which is neither outer, variable or clause inner has necessarily $v_3 = c_j^l$ for some $j$, and $v_2 \neq \theta_j$ ($v_2$ could be in $V(L)$ or $V(K)$). In the following definition, for any $Y \in C$ (where $C = \{X_i, X'_i, \overline{X_i}, \overline{X}'_i, A_i, B_i, A'_i, B'_i\}$) with $Y = (y^1, y^2, y^3, y^4)$, we define $t_Y^2 = (y^1, y^2, y^4)$ and $t_Y^3 = (y^1, y^3, y^4)$. For example, $t_{X'_i}^2 = (x'_i, x''_i, x'''_i)$. For any $i \in [n]$, we define $P_i$ and $\overline{P}_i$, two sets of vertex disjoint variable inner triangles of $V(L_i)$, by:

$$ \mathbf{P}_i = \{t_{X_i}^3, t_{X'_i}^3, t_{\overline{X}_i}^2, t_{\overline{X}'_i}^2, t_{A_i}^3, t_{B_i}^2, t_{A'_i}^3, t_{B'_i}^2, (h(e_3), \beta_i, t(e_3)), (h(e_4), \beta'_i, t(e_4)), (h(m_1), \alpha_i, t(m_1))\} $$

$$ \overline{P}_i = \{t_{X_i}^2, t_{X'_i}^2, t_{\overline{X}_i}^3, t_{\overline{X}'_i}^3, t_{A_i}^2, t_{B_i}^3, t_{A'_i}^2, t_{B'_i}^3, (h(e_1), \beta_i, t(e_1)), (h(e_2), \beta'_i, t(e_2)), (h(m_2), \alpha_i, t(m_2))\} $$

Notice that $P_i$ (resp. $\overline{P}_i$) uses all vertices of $L_i$ except $\{x_i^2, x_i^{2'}\}$ (resp. $\{\overline{x}_i^2, \overline{x}_i^{2'}\}$). For any $j \in [m]$, and $x \in [2]$ we define the set of clause inner triangle of $K_j$, that is $Q_j^x = \{(d_j^1, c_j^x, d_j^2)\}$.

Informally, setting variable $x_i$ to true corresponds to create the 11 triangles of $\overline{P}_i$ in $L_i$ (as leaving vertices $\{x_i^2, x_i^{2'}\}$) available allows to create outer triangles corresponding to satisfied clauses), and setting it to false corresponds to create the 11 triangles of $\overline{P}_i$. Satisfying a clause $j$ using its $x^h$ literal (represented by a vertex $v \in V(L)$) corresponds to create triangle in $Q_j^{3-x}$ as it leaves $c_j^x$ available to create the triangle $(v, \theta_j, c_j^x)$. Our final objective (in Lemma 4) is to prove that satisfying $k$ clauses is equivalent to find $11n + m + k$ vertex disjoint triangles.

**Restructuration lemmas** Given a solution $S$, let $I_i^L = \{t \in S : V(t) \subseteq V(L_i)\}$, $I_j^K = \{t \in S : V(t) \subseteq V(K_j)\}$, $I^L = \cup_{i \in [n]} I_i^L$ be the set of variable inner triangles of $S$, $I^K = \cup_{j \in [m]} I_j^K$ be the set of clause inner triangles of $S$, and $O = \{t \in S : t$ is an outer triangle $\}$ be the set of outer triangles of $S$. Notice that a priori $I^L, I^K, O$ does not necessarily form a partition of $S$. However, we will show in the next lemmas how to restructure $S$ such that $I^L, I^K, O$ becomes a partition.

**Lemma 1.** For any $S$ we can compute in polynomial time a solution $S' = \{t'_i, l \in [k]\}$ such that $|S'| \ge |S|$ and for all $j \in [m]$ there exists $x \in [2]$ such that $I_j^{K'} = Q_j^x$ and

either $S'$ does not use any other vertex of $K_j$ ($V(S') \cap V(K_j) = V(Q_j^x)$)

either $S'$ contains an outer triangle $t'_l = (v, \theta_j, c_j^{3-x})$ with $v \in V(L)$ (implying $V(S') \cap V(K_j) = V(K_j)$)

**Proof.** Consider a solution $S = \{t_l, l \in [k]\}$. Let us suppose that $S$ does not verify the desired property. We say that $j \in [m]$ satisfies $(\star)$ iff there exists $x \in [2]$ such that $I_j^K = Q_j^x$ and either $S$ does not use any other vertex of $K_j$, or $S$ contains an outer triangle $t_l = (v, \theta_j, c_j^{3-x})$ with $v \in V(L)$.

Let us restructure $S$ to increase the number of $j$ satisfying $(\star)$, which will be sufficient to prove the lemma. Consider the largest $j \in [m]$ which does not satisfy $(\star)$. Let $c = |I_j^K|$. Notice that the only possible triangle of $I_j^K$ contains $a = d_j^2 d_j^1$, implying $c \le 1$.

If $c = 1$, let $t \in I_j^K$ and $v_0 = \{c_j^1, c_j^2\} \setminus V(t)$. If $v_0 \notin V(S)$, then let us prove that $\theta_j \notin V(S)$. Indeed, by contradiction if $\theta_j \in V(S)$, let $t' \in S$ such that $\theta_j \in V(t')$. As $d(\theta_j) = (0,0)$ we necessarily have $t' = (u, \theta_j, w)$ with $w = c_{j'}^{x'}$ with $j' \ge j$, which contradicts the maximality
XX:6 Triangle packing in (sparse) tournaments: approximation and kernelization.

of $j$. Otherwise ($v_0 \in V(S)$), then denoting by $t'$ the triangle of $S$ which contains $v_0$ we must have $t' = (u, v, v_0)$. Indeed, we cannot have (for some $u', v'$) $t' = (v_0, u', v')$ as there is no backward arc $a$ with $h(a) = v_0$ and we cannot have either $t' = (u', v_0, v')$ as this would imply $v' = c_j^x$ for $j' > j$ and again contradict the definition of $j$. As, again, by maximality of $j$ we get $\theta_j \notin V(S)$ (and since $u\theta_j$ and $\theta_j v_0$ are forward arcs), we can replace $t'$ by the triangle $(u, \theta_j, v_0)$ which is disjoint to the other triangles of $S$.

If $c = 0$. Notice first that by maximality of $j$, $d_j^2 \notin V(S)$ as $d_j^2$ could only be used in a triangle $t = (v, d_j^2, c_{j'}^x)$ with $j' > j$. Let $Z = V(S) \cap \{c_j^1, c_j^2\}$. If $|Z| = 0$, then by maximality of $j$ we get $d_j^1 \notin V(S)$ and $\theta_j \notin V(S)$, and thus we add to $S$ triangle $(d_j^1, c_j^1, d_j^2)$. If $|Z| = 1$, let $c_j^x \in Z$ and $t \in S$ such that $c_j^x \in V(t)$. By maximality of $j$ we necessarily have $t = (u, v, c_j^x)$ for some $u, v$. If $v \neq \theta_j$ then by maximality of $j$ we have $\theta_j \notin V(S)$, and thus we swap $v$ and $\theta_j$ in $t$ and now suppose that $\theta_j \in V(t)$. This implies that $d_j^1 \notin V(S)$ (before the swap we could have had $v = d_j^1$, but now by maximality of $j$ we know that $d_j^1$ is unused), and we add $(d_j^1, c_j^{3-x}, d_j^2)$ to $S$. It only remains now case where $|Z| = 2$. If there exists $t \in S$ with $Z \subseteq V(t)$, then $t = (u, c_j^1, c_j^2)$. Using the same arguments as above we get that $\{\theta_j, d_j^1\} \cap V(S) = \emptyset$, and thus we swap $c_j^1$ by $\theta_j$ in $t$ and add $(d_j^1 c_j^1, d_j^2)$ to $S$. Otherwise, let $t_x \in S$ such that $c_j^x \in V(t_x)$ for $x \in [2]$. This implies that $t_x = (u_x, v_x, c_j^x)$. If $\theta_j \notin V(t_1) \cup V(t_2)$ then $\theta_j \notin V(S)$ and we swap $v_1$ with $\theta_j$. Therefore, from now on we can suppose that $\theta_j \in V(t_x)$ for $x \in [2]$. Then, if $d_j^1 \notin V(t_{3-x})$ then $d_j^1 \notin V(S)$ and thus we swap $v_{3-x}$ with $d_j^1$ and we now assume that $d_j^1 \in V(t_{3-x})$. Finally, we remove $t_{3-x}$ from $S$ and add instead $(d_j^1, c_j^{3-x}, d_j^2)$. $\quad$

**Corollary 2.** For any $S$ we can compute in polynomial time a solution $S'$ such that $|S'| \ge |S|$, and $S'$ only contains outer, variable inner, and clause inner triangles. Indeed, in the solution $S'$ of Lemma 1, given any $t \in S'$, either $V(t)$ intersects $V(K_j)$ for some $j$ and then $t$ is an outer or a clause inner triangle, or $V(t) \subseteq V(L_i)$ for $i \in [n]$ as there is no backward arc $uv$ with $u \in V(L_{i_1})$ and $v \in V(L_{i_2})$ with $i_1 \neq i_2$.

**Lemma 3.** For any $S$ we can compute in polynomial time a solution $S'$ such that $|S'| \ge |S|$, $S'$ satisfies Lemma 1, and for every $i \in [n]$, $I_i^{L} = P_i$ or $I_i^{L} = \bar{P}_i$.

**Proof.** Let $S_0$ be an arbitrary solution, and $S$ be the solution obtained from $S_0$ after applying Lemma 1. By Corollary 2, we partition $S$ into $S = I^L \cup I^K \cup O$. Let us say that $i \in [n]$ satisfies $(\star)$ if $I_i^L = P_i$ or $I_i^L = \bar{P}_i$. Let us suppose that $S$ does not verify the desired property, and show how to restructure $S$ to increase the number of $i$ satisfying $(\star)$ while still satisfying Lemma 1, which will prove the lemma.

Let $Lft_i = X_i \cup X_i' \cup \bar{X}_i \cup \bar{X}_i'$ and $Rgt_i = A_i \cup B_i \cup \{\alpha_i\} \cup A_i' \cup B_i'$ be two subset of vertices of $V(L_i)$. Given any solution $\tilde{S}$ satisfying Lemma 1, we define the following sets. Let $\tilde{S}^{Lft_i} = \{t \in \tilde{I}_i^L : V(t) \subseteq Lft_i\}$, $\tilde{S}^{Rgt_i} = \{t \in \tilde{I}_i^L : V(t) \subseteq Rgt_i\}$, and $\tilde{S}^{Lft_i Rgt_i} = \{t \in \tilde{I}_i^L : V(t) \cap Lft_i \neq \emptyset \text{ and } V(t) \cap Rgt_i \neq \emptyset \}$. Observe that these three sets define a partition of $\tilde{I}_i^L$, and that triangles of $\tilde{S}^{Lft_i}$ are even included in $W$ with $W \in \{X_i, X_i', \bar{X}_i, \bar{X}_i'\}$. Let $\tilde{S}^{O_i} = \{t \in \tilde{O} : V(t) \cap V(L_i) \neq \emptyset\}$ be the set of outer triangles of $\tilde{S}$ intersecting $L_i$. We also define $g_i(\tilde{S}) = (|\tilde{S}^{Lft_i}|, |\tilde{S}^{Lft_i Rgt_i}|, |\tilde{S}^{Rgt_i}|, |\tilde{S}^{O_i}|)$ and $h_i(\tilde{S}) = |\tilde{S}^{Lft_i}| + |\tilde{S}^{Lft_i Rgt_i}| + |\tilde{S}^{Rgt_i}| + |\tilde{S}^{O_i}| = |\tilde{I}_i^L \cup \tilde{S}^{O_i}|$.

Our objective is to restructure $S$ into a solution $S'$ with $S' = (S \setminus (I_i^L \cup S^{O_i})) \cup (I_i'^L \cup S'^{O_i})$. We will define $I_i'^L$ and $S'^{O_i}$ verifying the following properties ($\triangle$):
$\triangle_1$ : $I_i'^L = P_i$ or $I_i'^L = \bar{P}_i$,
$\triangle_2$ : $S'^{O_i} \subseteq S^{O_i}$,
$\triangle_3$ : $|(I_i'^L \cup S'^{O_i})| \ge |(I_i^L \cup S^{O_i})|$ (which is equivalent to $h_i(S') \ge h_i(S)$),
$\triangle_4$ : triangles of $I_i'^L \cup S'^{O_i}$ are vertex disjoint.
Notice that $\triangle_2$ and $\triangle_4$ imply that all triangles of $S'$ are still vertex disjoint. Indeed, as $S$ satisfies Lemma 1, the only triangles of $S$ intersecting $L_i$ are $I_i^L \cup S^{O_i}$, and thus replacing them with $I_i^{L'} \cup S^{O_i}$ satisfying the above property implies that all triangles of $S'$ are vertex disjoint. Moreover, $S'$ will still satisfy Lemma 1 even with $S^{O_i} \subseteq S^{O_i}$ as removing outer triangles cannot violate property of Lemma 1. Finally $\triangle_3$ implies that $|S'| \ge |S|$. Thus, defining $I_i^{L'}$ and $S^{O_i}$ satisfying $(\triangle)$ will be sufficient to prove the lemma. Let us now state some useful properties.

$$p_1: |S^{Lft_i}| \le 4$$

$$p_2: |S^{Lft_i Rgt_i}| \le 4 \text{ as for any } t \in S^{Lft_i Rgt_i} \text{ there exists } l \in [4] \text{ such that } V(t) \supseteq V(e_l).$$

$$p_3: |S^{Rgt_i}| \le 5 \text{ (as } |V(S^{Rgt_i})| = 17). \text{ Let } Z = V(S^{Lft_i Rgt_i}) \cap Rgt_i. \text{ Let us also prove that if } Z \supseteq \{a_i^3, b_i^3\}, Z \supseteq \{a_i^{l'}, b_i^{l'}\}, Z \supseteq \{a_i^3, b_i^3\} \text{ or } Z \supseteq \{a_i^{l'}, b_i^{l'}\} \text{ then } |S^{Rgt_i}| \le 4. \text{ For any } W \in \{A_i, B_i, A'_i, B'_i\}, \text{ let } s_W \text{ be the unique arc } a \text{ of } \mathcal{T} \text{ such that } V(a) \subseteq W \text{ and let } m_W \text{ be the unique medium arc } a \text{ such that } V(a) \cap W \ne \emptyset. \text{ Let us call the } \{s_W\} \text{ the four small arcs of the tournament induced by } Rgt_i. \text{ Let } \tilde{A}(S^{Rgt_i}) = \{a \in \tilde{A}(L_i) : \exists t \in S^{Rgt_i} \text{ such that } V(a) \subseteq V(t)\} \text{ be the set of backward arcs used by } S^{Rgt_i}. \text{ Observe that arcs of } \tilde{A}(S^{Rgt_i}) \text{ are small or medium arcs. Let us bound } |\tilde{A}(S^{Rgt_i})| = |S^{Rgt_i}|. \text{ Notice that for any } W \in \{A_i, B_i, A'_i, B'_i\}, W \cap Z \ne \emptyset \text{ implies that } \tilde{A}(S^{Rgt_i}) \text{ cannot contain both } s_W \text{ and } m_W. \text{ If } S^{Rgt_i} \text{ contains the 4 small arcs then by previous remark } S^{Rgt_i} \text{ cannot contain any medium arc, and thus } |S^{Rgt_i}| \le 4. \text{ If } S^{Rgt_i} \text{ contains 3 small arcs then it can only contain one medium arc, implying } |S^{Rgt_i}| \le 4. \text{ Obviously, if } |S^{Rgt_i}| \text{ contains 2 or less small arcs then } |S^{Rgt_i}| \le 4.$$

$$p_4: \text{property } p_3 \text{ implies that if } |S^{Lft_i Rgt_i}| \ge 3, \text{ or if } |S^{Lft_i Rgt_i}| = 2 \text{ and triangles of } S^{Lft_i Rgt_i} \text{ contain } \{e_1, e_3\}, \{e_1, e_4\}, \{e_2, e_3\} \text{ or } \{e_2, e_4\}, \text{ then } |S^{Rgt_i}| \le 4 \text{ (where triangles of } S^{Lft_i Rgt_i} \text{ contains } \{e_i, e_j\} \text{ means that there exist } t_1, t_2 \text{ in } S^{Lft_i Rgt_i} \text{ such that } V(t_1) \supseteq V(e_i) \text{ and } V(t_2) \supseteq V(e_j)\).}$$

$$p_5: |S^{O_i}| \le 3. \text{ Moreover, if } |S^{Lft_i}| = 4 \text{ then } |S^{O_i}| \le 4 - |S^{Lft_i Rgt_i}|, \text{ and if } |S^{Lft_i}| = 3 \text{ and } |S^{Lft_i Rgt_i}| = 4 \text{ then } |S^{O_i}| \le 1. \text{ The last two inequalities come from the fact that for any } W \in \{X_i, X'_i, \bar{X}_i, \bar{X}'_i\}, \text{ we cannot have both } t_1 \in S^{O_i}, t_2 \in S^{Lft_i Rgt_i} \text{ and } t_3 \in S^{Lft_i} \text{ with } V(t_i) \cap W \ne \emptyset.$$

Notice that if a solution $S'$ satisfies $I_i^{L'} = P_i$ or $I_i^{L'} = \bar{P}_i$ then $g_i(S') = (4, 2, 5, z)$ where $z \in [2]$, and $h_i(S') = 11 + z$. In the following we write $(u_1^1, u_2^1, u_3^1, u_4^1) \le (u_1^2, u_2^2, u_3^2, u_4^2)$ iff $u_i^1 \le u_i^2$ for any $i \in [4]$. Let us describe informally the following argument which will be used several times. Let $z = |S^{O_i}|$. If $z \le 1$ or if $z = 2$ but the two corresponding outer triangles do not use one vertex in $X_i \cup X'_i$ and one vertex in $\bar{X}_i$, then we will be able to "save" all these outer triangles (while creating the optimal number of variable inner triangles in $L_i$), meaning that $S^{O_i} = S^{O_i}$, as either $P_i$ or $\bar{P}_i$ will leave vertices of $S^{O_i} \cap Lft_i$ available for outer triangles. Let us proceed by case analysis according to the value $|S^{Lft_i Rgt_i}|$. Remember that $|S^{Lft_i Rgt_i}| \le 4$ according to $p_2$.

**Case 1:** $|S^{Lft_i Rgt_i}| \le 1$. According to $p_1, p_3$ we get $g_i(S) \le (4, 1, 5, z)$ where $z \in [3]$. In this case, $S^{O_i} = S^{O_i} \setminus \{t \in S : V(t) \supseteq \bar{x}_i^2\}$ and $I_i^{L'} = P_i$ verify $(\triangle)$. In particular, we have $h_i(S') \ge h_i(S)$ as $g_i(S') \ge (4, 2, 5, z - 1)$.

**Case 2:** $|S^{Lft_i Rgt_i}| = 2$. Let $g_i(S) = (x, 2, y, z)$. If $x \le 3$, then $g_i(S) \le (3, 2, 5, z)$ by $p_3$ and we set $S^{O_i} = S^{O_i} \setminus \{t \in S : V(t) \supseteq \bar{x}_i^2\}$ and $I_i^{L'} = P_i$. This satisfies $(\triangle)$ as in particular we have $h_i(S') \ge h_i(S)$ as $g_i(S') \ge (4, 2, 5, z - 1)$. Let us now turn to case where $x = 4$. Let $S^{Lft_i Rgt_i} = \{t_1, t_2\}$. Let us first suppose that triangles of $S^{Lft_i Rgt_i}$ contain $\{e_i, e_j\}$ with $\{e_i, e_j\} \in \{{\{e_1, e_3\}}, \{e_1, e_4\}, \{e_2, e_3\}, \{e_2, e_4\}\}$. By $p_4$ we get $y \le 4$, implying $g_i(S) \le (4, 2, 4, z)$. In this case, $S^{O_i} = S^{O_i} \setminus \{t \in S : V(t) \supseteq \bar{x}_i^2\}$ and $I_i^{L'} = P_i$ verify $(\triangle)$.
XX:8 Triangle packing in (sparse) tournaments: approximation and kernelization.

In particular, we have $h_i(S') \ge h_i(S)$ as $g_i(S') = (4, 2, 5, z-1)$. Let us suppose now that $t_1$ contains $e_1$ and $t_2$ contains $e_2$ (case (2a)), or $t_1$ contains $e_3$ and $t_2$ contains $e_4$ (case (2b)). In both cases we have $g_i(S) \le (4, 2, 5, z)$ where $z \in [2]$ by $p_5$. More precisely, $p_5$ implies that $\{W \in \{X_i, X'_i, \bar{X}_i, \bar{X}'_i\} : W \cap V(S^{O_i}) \ne \emptyset\}$ is included in $\{X, X'_i\}$ (case 2b) or in $\bar{X}_i$ (case 2a). Thus, in case (2a) we define $S'^{O_i} = S^{O_i}$ and $I'^L_i = \bar{P}_i$. In case (2b) we define $S^{O_i} = S^{O_i}$ and $I'^L_i = P_i$. In both cases these sets verify $(\triangle)$ as in particular $g_i(S') = (4, 2, 5, z)$.

Case 3: $|S^{Lft_i Rgt_i}| = 3$. In this case $g_i(S) \le (x, 3, 4, z)$ by $p_4$. If $x \le 3$, the sets $S^{O_i} = S^{O_i} \setminus \{t \in S : V(t) \ni \bar{x}_i^2\}$ and $I'^L_i = P_i$ verify $(\triangle)$. In particular, we have $h_i(S') \ge h_i(S)$ as $g_i(S') \ge (4, 2, 5, z-1)$. If $x=4$ then $z \le 1$ by $p_5$. Thus, we define $I'^L_i = P_i$ if $V(S^{O_i}) \cap (X_i \cup X'_i) \ne \emptyset$, and $I'^L_i = \bar{P}_i$ otherwise, and $S^{O_i} = S^{O_i}$. These sets satisfy $(\triangle)$ as in particular $g_i(S') = (4, 2, 5, z)$.

Case 4: $|S^{Lft_i Rgt_i}| = 4$. Let $g_i(S) = (x, 4, y, z)$. If $x=4$ then $z \le 0$ by $p_5$ and $y \le 3$ as $x+4+y \le \frac{|V(L_i)|}{3}$.

Thus, we set $S^{O_i} = S^{O_i} = \emptyset$, $I'^L_i = P_i$ (which is arbitrary in this case), and we have property $(\triangle)$ as $g_i(S') \ge (4, 2, 5, 0)$. If $x=3$ (this case is depicted Figure 3) then $y \le 4$ by $p_3$ and $z \le 1$ by $p_5$, implying $g_i(S) = (3, 4, 4, z)$. Thus, we define $I'^L_i = P_i$ if $V(S^{O_i}) \cap (X_i \cup X'_i) \ne \emptyset$, and $I'^L_i = \bar{P}_i$ otherwise, and $S^{O_i} = S^{O_i}$. These sets satisfy $(\triangle)$ as in particular $g_i(S') = (4, 2, 5, z)$. Finally, if $x \le 2$ then $g_i(S) \le (2, 4, 4, z)$ by $p_3$. In this case, $S^{O_i} = S^{O_i} \setminus \{t \in S : V(t) \ni \bar{x}_i^2\}$ and $I'^L_i = P_i$ verify $(\triangle)$. In particular, we have $h_i(S') \ge h_i(S)$ as $g_i(S') \ge (4, 2, 5, z-1)$.

<figure><img src="image_6.png" /><figcaption>Figure 3 Example showing a "bad shaped" solution of case 4 with $g_i(S) = (3, 4, 4, 1)$. We have $S^{Lft_i Rgt_i} = \{t_1, t_2, t_3, t_4\}$, $S^{O_i} = \{t_5\}$, $S^{Lft_i} = \{t_6, t_7, t_8\}$ and $S^{Rgt_i} = \{t_9, t_{10}, t_{11}, t_{12}\}$. The three vertices of triangle $t_l$ are annotated with label $l$.</figcaption></figure>

<figure><img src="image_7.png" /></figure>

**Proof of the L-reduction** We are now ready to prove the main lemma (recall that $f$ is the reduction from $\text{Max 2-SAT}(3)$ to $C_3$-PACKING-$T^{DM}$ described in Section 3.1), and also the main theorem of the section.

**Lemma 4.** Let $\mathcal{F}$ be an instance of $\text{Max 2-SAT}(3)$. For any $k$, there exists an assignment $a$ of $\mathcal{F}$ satisfying at least $k$ clauses if and only if there exists a solution $S$ of $f(\mathcal{F})$ with $|S| \ge 11n+m+k$, where $n$ and $m$ are respectively the number of variables and clauses in $\mathcal{F}$. Moreover, in the $\Leftarrow$ direction, assignment $a$ can be computed from $S$ in polynomial time.

**Proof.** For any $i \in [n]$, let $A_i = P_i$ if $x_i$ is set to true in $a$, and $A_i = \bar{P}_i$ otherwise. We first add to $S$ the set $\cup_{i \in [n]} A_i$. Then, let $\{C_{jl}, l \in [k]\}$ be $k$ clauses satisfied by $a$. For any $l \in [k]$, let $i_l$ be the index of a literal satisfying $C_{jl}$, let $x \in [2]$ such that $c_{jl}^x$ corresponds to this literal, and let $Z_l = \{x_{i_l}^2, x_{i_l'}^2\}$ if literal $i_l$ is positive, and $Z_l = \{\bar{x}_{i_l}^2\}$ otherwise. For any $j \in [m]$, if $j = i_l$ for some $l$ (meaning that $j$ corresponds to a satisfied clause), we add to $S$ the triangle in $Q_j^{3-x}$, and otherwise we arbitrarily add the triangle $Q_j^1$. Finally, for any
$l \in [k]$ we add to $S$ triangle $t_l = (y_l, \theta_{j_l}, c_{j_l}^x)$ where $y_l \in Z_l$ is such that $y_l$ is not already used in another triangle. Notice that such an $y_l$ always exists as triangles of $A_i$, $i \in [n]$ do not intersect $Z_l$ (by definition of the $A_i$), and as there are at most two clauses that are true due to positive literal, and one clause that is true due to a negative literal. Thus, $S$ has $11n + m + k$ vertex disjoint triangles.

Conversely, let $S$ a solution of $f(\mathcal{F})$ with $|S| \ge 11n+m+k$. By Lemma 3 we can construct in polynomial time a solution $S'$ from $S$ such that $|S'| \ge |S|$, $S'$ only contains outer, variable or clause inner triangles, for each $j \in [m]$ there exists $x \in [2]$ such that $I_j^K = Q_j^x$, and for each $i \in [n]$, $I_i^L = P_i$ or $I_i^L = \bar{P}_i$. This implies that the $k' \ge k$ remaining triangles must be outer triangles. Let $\{t_l', l \in [k']\}$ be these $k'$ outer triangles with $t_l' = (y_l, \theta_{j_l}, c_{j_l}^{x_l})$. Let us define the following assignation $a$: for each $i \in [n]$, we set $x_i$ to true if $I_i^L = P_i$, and false otherwise. This implies that $a$ satisfies at least clauses $\{C_{j_l}, l \in [k']\}$. $\quad$

**Theorem 5.** $C_3$-PACKING-$T^{DM}$ is APX-hard, and thus does not admit a PTAS unless $P = \mathrm{NP}$.

**Proof.** Let us check that Lemma 4 implies a $L$-reduction (whose definition is recalled in Definition 17 of appendix). Let $OPT_1$ (resp. $OPT_2$) be the optimal value of $\mathcal{F}$ (resp. $f(\mathcal{F})$). Notice that Lemma 4 implies that $OPT_2 = OPT_1 + 11n + m$. It is known that $OPT_1 \ge \frac{3}{4}m$ (where $m$ is the number of clauses of $\mathcal{F}$). As $n \le m$ (each variable has at least one positive and one negative occurrence), we get $OPT_2 = OPT_1 + 11n + m \le \alpha OPT_1$ for an appropriate constant $\alpha$, and thus point (a) of the definition is verified. Then, given a solution $S'$ of $f(\mathcal{F})$, according to Lemma 4 we can construct in polynomial time an assignment $a$ satisfying $c(a)$ clauses with $c(a) \ge S' - 11n - m$. Thus, the inequality (b) of Definition 17 with $\beta = 1$ becomes $OPT_1 - c(a) \le OPT_2 - S' = OPT_1 + 11n + m - S'$, which is true. $\quad$

Reduction of Theorem 5 does not imply the NP-hardness of $C_3$-PERFECT-PACKING-$T$ as there remain some unused vertices. However, it is straightforward to adapt the reduction by adding backward arcs whose head (resp. tail) are before (resp. after) $\mathcal{T}$ to consume the remaining vertices. This leads to the following result.

**Theorem 6.** $C_3$-PERFECT-PACKING-$T^{DM}$ is NP-hard.

**Proof.** Let $(\mathcal{F}, k)$ be an instance of the decision problem of $\mathrm{MAX} - 2 - \mathrm{SAT}(3)$ and let $\mathcal{T} = f(\mathcal{F})$ be the tournament defined in Section 3.1. Recall that we have $\mathcal{T} = \mathrm{LK}$. Let $N = |V(\mathcal{T})| = 35n+5m, x^* = 33n+3m+3k$ and $n' = N - x^*$. We now define $\mathcal{T}'$ by adding $2n'$ new vertices in $\mathcal{T}$ as follows: $V(\mathcal{T}') = R_1V(\mathcal{T})R_2$ with $R_i = \{r_i^l, l \in [n']\}$. We add to $\overleftarrow{A}(\mathcal{T}')$ the set of arcs $R = \{(r_2^l r_1^l), l \in [n']\}$ which are called the dummy arcs. We say that a triangle $t = (u, v, w)$ is dummy iff $(wu)inR$ and $v \in V(\mathcal{T})$. Let us prove that there are at least $k$ clauses satisfiable in $\mathcal{F}$ iff there exists a perfect packing in $\mathcal{T}'$.

⇒

Given an assignement satisfying $k$ clause we define a solution $S$ with $V(S) \subseteq V(\mathcal{T})$ as in Lemma 4 (triangles of $P_i$ or $\bar{P}_i$ for each $i \in [n]$, a triangle $Q_j^x$ for each $j \in [m]$, and an outer triangle $t_l$ with $l \in [k]$ for each satisfied clause. We have $|S| = 11n + m + k$. This implies that $|V(\mathcal{T}) \setminus V(S)| = n'$, and thus we use $n'$ remaining vertices of $V(\mathcal{T})$ by adding to $S$ $n'$ dummy triangles.

$\Leftarrow$

Let $S'$ be a perfect packing of $\mathcal{T}'$. Let $S = \{t \in S' : V(t) \subseteq V(\mathcal{T})\}$. Let $X = V(\mathcal{T}) \setminus V(S)$. As $S'$ is a perfect packing of $\mathcal{T}'$, vertices of $X$ must be used by $|X|$ dummy triangles of $S'$, implying $|X| \le n'$ and $|S| \ge 11n + m + k$. As $S$ is set of vertex disjoint triangles of $\mathcal{T}$ of size at least $11n + m + k$, this implies by Lemma 4 that at least $k$ clauses are satisfiable in $\mathcal{F}$.
◀

To establish the kernel lower bound of Section 4, we also need the NP-hardness of $C_3$-PERFECT-PACKING-T where instances have a slightly simpler structure (to the price of losing the property that there exists a FAS which is a matching).

**Theorem 7.** $C_3$-PERFECT-PACKING-T remains NP-hard even restricted to tournament $\mathcal{T}$ admitting the following linear ordering.

■ $\mathcal{T} = \text{LK}$ where $L$ and $K$ are two tournaments

■ tournaments $L$ and $K$ are "fixed":

■ $K = K_1 \dots K_m$ for some $m$, where for each $j \in [m]$ we have $V(K_j) = (\theta_j, c_j)$

■ $L = R_1 L_1 \dots L_n R_2$, where each $L_i$ has a copy of the variable gadget of Section 3.1, $R_i = \{r_i^l, l \in [n']\}$ where $n' = 2n-m$, and in addition $\overleftarrow{L}$ also contains $R = \{(r_2^l r_1^l), l \in [n']\}$ which are called the dummy arcs.

**Proof.** We adapt the reduction of Section 3.1, reducing now from 3-SAT(3) instead of MAX 2-SAT(3). Given $\mathcal{F}$ be an instance of 3-SAT(3) with $n$ variables $\{x_i\}$ and $m$ clauses $\{C_j\}$. For each variable $x_i$ with $i \in [n]$, we create a tournament $L_i$ exactly as in Section 3.1 and we define $L = L_1 \dots L_n$. For each clause $C_j$ with $j \in [m]$, we create a tournament $K_j$ with $V(K_j) = (\theta_j, c_j)$, and we define $K = K_1 \dots K_m$. Let us now define $\mathcal{T} = \text{LK}$. Now, we add to $\overleftarrow{A}(\mathcal{T})$ the following backward arcs from $V(K)$ to $V(L)$ (again, we follow the construction of Section 3.1 except that now each $c_j$ has degree (3,0)). If $C_j = l_{i_1} \lor l_{i_2} \lor l_{i_3}$ is a clause in $\mathcal{F}$ then we add the arcs $c_j v_{i_1}, c_j v_{i_2}, c_j v_{i_3}$ where $v_{i_c}$ is the vertex in $\{x_{i_c}^2, x_{i_c}^{l'}, x_{i_c}^{l2}\}$ corresponding to $l_{i_c}$: if $l_{i_c}$ is a positive occurrence of variable $i_c$ we chose $v_{i_c} \in \{x_{i_c}^2, x_{i_c}^{l'}, x_{i_c}^{l2}\}$, otherwise we chose $v_{i_c} = \overline{x_{i_c}^2}$. Moreover, we chose vertices $v_{i_c}$ in such a way that for any $i \in [n]$, for each $v \in \{x_i^2, x_i^{l'}, x_i^{l2}\}$ there exists a unique arc $a \in \overleftarrow{A}(\mathcal{T})$ such that $h(a) = v$. This is always possible as each variable has at most 2 positive occurrences and 1 negative one.

Finally, we add $2n'$ new vertices in $\mathcal{T}$ as follows: $V(T) = R_1 V(L) R_2 V(K)$, $R_i = \{r_i^l, l \in [n']\}$ where $n' = 2n-m$. We add to $\overleftarrow{A}(\mathcal{T})$ the set of arcs $R = \{(r_2^l r_1^l), l \in [n']\}$ which are called the dummy arcs. Notice that $\mathcal{T}$ satisfies the claimed structure (defining the left part as $R_1 L R_2$ and not only $L$). We define an outer and variable inner triangle as in Section 3 (there are no more clause inner triangle), and in addition we say that a triangle $t = (u, v, w)$ is dummy iff $(wu) \in R$ and $v \in V(L)$. Let us prove that there is an assignment satisfying the $m$ clauses of $\mathcal{F}$ iff $\mathcal{T}$ has a perfect packing.

⇒

Given an assignment satisfying the $m$ clauses we define a solution $S$ containing only outer, variable inner and dummy triangles. The variable inner triangle are defined as in Lemma 4 (triangles of $P_i$ or $\overline{P}_i$ for each $i \in [n]$). For each clause $j \in [m]$ satisfied by a literal $l_{i_x}$ we create an outer triangle $(v_{i_x}, \theta_j, c_j)$. It remains now $2n - m = n'$ vertices of $L$, that we use by adding $n'$ dummy triangles to $S$.

←=

Let $S$ be a perfect packing of $\mathcal{T}'$. Notice that restructuration lemmas of Section 3 do not directly remain true because of the dummy arcs. However, we can adapt in a straightforward manner arguments of these lemmas, using the fact that $S$ is even a perfect packing. Given a solution $S$, we define as in Section 3 set $I_i^L = \{t \in S : V(t) \subseteq V(L_i)$, $I_i^L = \cup_{i \in [n]} I_i^L$, $O = \{t \in S : t$ is an outer triangle $\}$, and $D = \{t \in S : t$ is a dummy triangle $\}$. Again, we do not claim (at this point) that $S$ does not contain other triangles. Given any perfect packing $S$ of $\mathcal{T}$, we can prove the following properties.
- $S$ must contain exactly $m$ outer triangles ($|O| = m$). Indeed, for any $j$ from $m$ to 1, the only way to use $\theta_j$ is to create an outer triangle $(u_j, \theta_j, c_j)$. This implies that triangles of $O$ consume exactly $m$ disjoint vertices in $L$.

- for any $i \in [n]$, we must have $|I_i^L| = 11$. Indeed, let $x$ be the number of vertices of $L$ used in $S$ (as $S$ is a perfect packing we know that $x = |L| = 35n$). The only triangles of $S$ that can use a vertex of $L$ are the outer, the variable inner and the dummy triangles, implying $x \le (\sum_{i \in [n]} |I_i^L|) + m + n'$ as $|D| \le n'$. As $|V(L_i)| = 35$ we have $|I_i^L| \le 11$ and thus we must have $|I_i^L| = 11$ for any $i$.

Let us now consider the tournament $\mathcal{T}_0 = \mathcal{T}[V(\mathcal{T}) \setminus V(R)]$ without the dummy arcs, and $S_0 = \{t \in S : V(t) \subseteq V(\mathcal{T}_0)\}$. We adapt in a straightforward way the notion of variable inner and outer triangle in $\mathcal{T}_0$. Observe that the variable inner and outer triangles of $S$ and $S_0$ are the same, and thus are both denoted respectively $I_i^L$ and $S_0^{O_i}$. In particular, $S_0$ still contains $m$ outer triangle of $\mathcal{T}_0$. Now we simply apply proof of Lemma 3 on $S_0$. More precisely, Lemma 3 restructures $S_0$ into a solution $S'_0$ with $S'_0 = (S_0 \setminus (I_i^L \cup S_0^{O_i})) \cup (I_i'^L \cup S_0^{O_i})$, where $I_i'^L$ and $S_0^{O_i}$ satisfy properties $(\triangle)$. In particular, as $|I_i^L| = |I_i'^L| = 11$, $\triangle_3$ implies that $|S_0^{O_i}| \ge |S_0^{O_i}|$, and thus that $|S_0^{O_i}| \ge |S_0^{O_i}| = m$. Thus, $S'_0$ satisfies $I_i^L = P_i$ or $I_i^L = \bar{P}_i$ for any $i$, and has $m$ outer triangles. We can now define as in Lemma 4 from $S'_0$ an assignment satisfying the $m$ clauses. $\blacksquare$

## 3.2 $(1 + \frac{6}{c-1})$-approximation when backward arcs have large minspan

Given a set of pairwise distinct pairs $D$ and an integer $c$, we denote by $C_3$-PACKING-$T_{\ge c}^D$ the problem $C_3$-PACKING-$T^D$ restricted to tournaments such that there exists a linear representation of minspan at least $c$ and where $d(v) \in D$ for all $v$. In all this section we consider an instance $\mathcal{T}$ of $C_3$-PACKING-$T_{\ge c}^{D_M}$ with a given linear ordering $(V(\mathcal{T}), \overleftarrow{A}(\mathcal{T}))$ of minspan at least $c$ and whose degrees belong to $D_M$. The motivation for studying the approximability of this special case comes from the situation of MAX-SAT(c) where the approximability becomes easier as $c$ grows, as the derandomized uniform assignment provides a $\frac{2^c}{2^c-1}$ approximation algorithm. Somehow, one could claim that MAX-SAT(c) becomes easy to approximate for large $c$ as there many ways to satisfy a given clause. As the same intuition applies for tournament admitting an ordering with large minspan (as there are $c-1$ different ways to use a given backward in a triangle), our objective was to find a polynomial approximation algorithm whose ratio tends to 1 when $c$ increases.

Let us now define algorithm $\Phi$. We define a bipartite graph $G = (V_1, V_2, E)$ with $V_1 = \{v_1^a : a \in \overleftarrow{A}(\mathcal{T})\}$ and $V_2 = \{v_1^2 : v_1 \in V_{(0,0)}\}$. Thus, to each backward arc we associate a vertex in $V_1$ and to each vertex $v_l$ with $d(v_l) = (0,0)$ we associate a vertex in $V_2$. Then, $\{v_1^a, v_1^2\} \in E$ iff $(h(a), v_l, t(a))$ is a triangle in $\mathcal{T}$.

In phase 1, $\Phi$ computes a maximum matching $M = \{e_l, l \in [|M|]\}$ in $G$. For every $e_l = \{v_{ij}^1, v_l^2\} \in M$ create a triangle $t_l^1 = (v_j, v_l, v_i)$. Let $S^1 = \{t_l^1, l \in [|M|]\}$. Notice that triangles of $S^1$ are vertex disjoint. Let us now turn to phase 2. Let $\mathcal{T}^2$ be the tournament $\mathcal{T}$ where we removed all vertices $V(S^1)$. Let $(V(\mathcal{T}^2), \overleftarrow{A}(\mathcal{T}^2))$ be the linear ordering of $\mathcal{T}^2$ obtained by removing $V(S^1)$ in $(V(\mathcal{T}), \overleftarrow{A}(\mathcal{T}))$. We say that three distinct backward edges $\{a_1, a_2, a_3\} \subseteq \overleftarrow{A}(\mathcal{T}^2)$ can be packed into triangles $t_1$ and $t_2$ iff $V(\{t_1, t_2\}) = V(\{a_1, a_2, a_3\})$ and the $t_i$ are vertex disjoint. For example, if $h(a_1) < h(a_2) < t(a_1) < h(a_3) < t(a_2) < t(a_3)$, then $\{a_1, a_2, a_3\}$ can be packed into $(h(a_1), h(a_2), t(a_1))$ and $(h(a_3), t(a_2), t(a_3))$ (recall that when $\overleftarrow{A}(\mathcal{T})$ form a matching, $(u, v, w)$ is triangle iff $wu \in \overleftarrow{A}(\mathcal{T})$ and $u < v < w$), and if $h(a_1) < h(a_2) < t(a_2) < h(a_3) < t(a_3) < t(a_1)$, then $\{a_1, a_2, a_3\}$ cannot be packed into two
XX:12 Triangle packing in (sparse) tournaments: approximation and kernelization.

triangles. In phase 2, while it is possible, $\Phi$ finds a triplet of arcs of $Y \subseteq \overleftarrow{A}(\mathcal{T}^2)$ that can be packed into triangles, create the two corresponding triangles, and remove $V(Y)$. Let $S^2$ be the triangle created in phase 2 and let $S = S^1 \cup S^2$.

**Observation 8.** For any $a \in \overleftarrow{A}(\mathcal{T})$, either $V(a) \subseteq V(S)$ or $V(a) \cap V(S) = \emptyset$. Equivalently, no backward arc has one endpoint in $V(S)$ and the other outside $V(S)$.

According to Observation 8, we can partition $\overleftarrow{A}(\mathcal{T}) = \overleftarrow{A}_0 \cup \overleftarrow{A}_1 \cup \overleftarrow{A}_2$, where for $i \in \{1, 2\}$, $\overleftarrow{A}^i = \{a \in \overleftarrow{A}(\mathcal{T}) : V(a) \subseteq V(S^i)\}$ is the set of arcs used in phase $i$, and $\overleftarrow{A}_0 =_{def} \{b_i, i \in [x]\}$ are the remaining unused arcs. Let $\overleftarrow{A}_{\Phi} = \overleftarrow{A}_1 \cup \overleftarrow{A}_2$, $m_i = |\overleftarrow{A}_i|$, $m = m_0 + m_1 + m_2$ and $m_{\Phi} = m_1 + m_2$ the number of arcs (entirely) consumed by $\Phi$. To prove the $1 + f(\frac{6}{c-1})$ desired approximation ratio, we will first prove in Lemma 9 that $\Phi$ uses at most all the arcs ($m_A \ge (1 - \epsilon(c))m$), and in Theorem 10 that the number of triangles made with these arcs is "optimal". Notice that the latter condition is mandatory as if $\Phi$ used its $m_{\Phi}$ arcs to only create $\frac{2}{3}(m_{\Phi})$ triangles in phase 2 instead of creating $m' \approx m_{\Phi}$ triangle with $m'$ backward arcs and $m'$ vertices of degree (0,0), we would have a $\frac{3}{2}$ approximation ratio.

**Lemma 9.** For any $c \ge 2$, $m_{\Phi} \ge (1 - \frac{6}{c+5})m$

**Proof.** In all this proof, the span $s(a)$ is always considered in the initial input $\mathcal{T}$, and not in $\mathcal{T}^2$. For any $i \in [x]$, let us associate to each $b_i \in \overleftarrow{A}_0$ a set $B_i \subseteq \overleftarrow{A}_{\Phi}$ defined as follows (see Figure 4 for an example). Let $b_j \in \overleftarrow{A}_0$ such that $s(b_j) \subseteq s(b_i)$ and there does not exist a $b_k \in \overleftarrow{A}_0$ such that $s(b_k)$ included in $s(b_j)$ (we may have $b_j = b_i$). Let $Z = V(\overleftarrow{A}_0) \cap s(b_j)$. Notice that $|Z| \le 1$, meaning that there is at most one endpoint of a $b_l, l \ne j$ in $s(b_j)$, as otherwise we would be three arcs in $\overleftarrow{A}_0$ that could be packed in two triangles. If there exists $a \in \overleftarrow{A}_{\Phi}$ with $s(a) \subseteq s(b_j)$ we define $a_0 = a$, and otherwise we define $a_0 = b_j$. Now, let $v \in s(a_0) \setminus Z$. Observe that $V(\mathcal{T})$ is partitioned into $V(\overleftarrow{A}_0) \cup V(\overleftarrow{A}_{\Phi}) \cup V_{(0,0)}$. If $v \in V_{(0,0)}$, then there exists $t_l^1 = (u, v, w)$ with $wu \in \overleftarrow{A}_1$ (as otherwise the matching in phase 1 would not be maximal and we could add $b_j$ and $v$), and we add $wu$ to $B_i$. Otherwise, $v \in V(a)$ with $a \in \overleftarrow{A}_{\Phi}$ (this arcs could have been used in phase 1 or phase 2), and we add $a$ to $B_i$. Notice that as $a_0$ does not properly contains another arc of $\overleftarrow{A}_{\Phi}$, all the added arcs are pairwise distinct, and thus $|B_i| = |s(a_0) \setminus Z| \ge c - 1$.

<figure><img src="image_8.png" /><figcaption>■ **Figure 4** On this example white vertices represent $V(\mathcal{T}) \setminus V(S)$ (vertices not used by $\Phi$), and black ones represent $V(S)$. In this case we have $B_i = \{a_l, l \in [3]\}$. Indeed, each $v_l \in s(a_0) \setminus Z$, for $l \in [3]$, brings $a_l$ in $B_i$. In particular $v_2 \in V_{(0,0)}$ and was used with $a_2$ to create a triangle in phase 1.</figcaption></figure>

Given $a \in \overleftarrow{A}_{\Phi}$, let $B(a) = \{B_i, a \in B_i\}$. Let us prove that $|B(a)| \le 6$ for any $a \in \overleftarrow{A}_{\Phi}$. For any $v \in V(S)$, let $d_B(v) = |\{b_i : v \in s(b_i)\}|$. Observe that $d_B(v) \le 2$, as otherwise any
<figure><img src="image_9.png" /><figcaption>Figure 5 Example where $|B(a)| = 6$ for $a \in \tilde{A}_{\Phi}$, where $B(a) = \{b_l, l \in [6]\}$.</figcaption></figure>

triplet of arcs containing $v$ in their span could be packed into two triangles (there are only 6 cases to check according to the 3! possible ordering of the tail of these 3 arcs). For any $a \in \overleftarrow{A}_1$, let $V'(a) = V(t^a)$ where $t^a \in S$ is the triangle containing $a$, and for any $a \in A_2$, let $V'(a) = V(a)$. Observe that by definition of the $B_i$, $a \in B_i$ implies that $b_i$ contributes to the degree $d_B(v)$ for a $v \in V'(a)$. As in particular $d_B(v)$ for any $v \in V'(a)$, this implies by pigeonhole principle that $|B(a)| \le 6$ (notice that this bound is tight as depicted Figure 5). Thus, if we consider the bipartite graph with vertex set $(\overleftarrow{A}_0, \overleftarrow{A}_{\Phi})$ and an edge between $b_i \in \overleftarrow{A}_0$ and $a \in \overleftarrow{A}_{\Phi}$ iff $a \in B_i$, the number of edges $x$ of this graph satisfies $|\overleftarrow{A}_0|(c-1) \le x \le 6|\overleftarrow{A}_{\Phi}|$, implying the desired inequality as $m_{\Phi} = m - m_0$. ◀

**Theorem 10.** For any $c \ge 2$, $\Phi$ is a polynomial $(1 + \frac{6}{c-1})$ approximation algorithm for $C_3$-PACKING-$T_{\ge c}^{D_M}$.

**Proof.** Let $OPT$ be an optimal solution. Let us define set $OPT_i \subseteq OPT$ and $\overleftarrow{A}_i^* \subseteq \overleftarrow{A}(T)$ as follows. Let $t = (u, v, w) \in OPT$. As the FAS of the instance is a matching, we know that $wu \in \overleftarrow{A}(T)$ as we cannot have a triangle with two backward arcs. If $d(v) = (0, 0)$ then we add $t$ to $OPT_1$ and $wu$ to $\overleftarrow{A}_1^*$. Otherwise, let $v'$ be the other endpoint of the unique arc $a$ containing $v$. If $v' \notin V(OPT)$, then we add $t$ to $OPT_3$ and $\{wu, a\}$ to $\overleftarrow{A}_3^*$. Otherwise, let $t' \in OPT$ such that $v' \in V(t')$. As the FAS of the instance is a matching we know that $v'$ is the middle point of $t'$, or more formally that $t' = (u', v', w')$ with $u'w' \in \overleftarrow{A}(T)$. We add $\{t, t'\}$ to $OPT_2$ and $\{wu, a, w'u'\}$ to $\overleftarrow{A}_2^*$. Notice that the $OPT_i$ form a partition of $OPT$, and that the $\overleftarrow{A}_i^*$ have pairwise empty intersection, implying $|\overleftarrow{A}_1^*| + |\overleftarrow{A}_2^*| + |\overleftarrow{A}_3^*| \le m$. Notice also that as triangles of $OPT_1$ correspond to a matching of size $|OPT_1|$ in the bipartite graph defined in phase 1 of algorithm $\Phi$, we have $|OPT_1| = |\overleftarrow{A}_1^*| \le |\overleftarrow{A}_1|$.

Putting pieces together we get (recall that $S$ is the solution computed by $\Phi$): $|OPT| = |OPT_1| + |OPT_2| + |OPT_3| = |\overleftarrow{A}_1^*| + \frac{2}{3}|\overleftarrow{A}_2^*| + \frac{1}{2}|\overleftarrow{A}_3^*| \le |\overleftarrow{A}_1^*| + \frac{2}{3}(|\overleftarrow{A}_2^*| + |\overleftarrow{A}_3^*|) \le |\overleftarrow{A}_1^*| + \frac{2}{3}(m - |\overleftarrow{A}_1^*|) \le \frac{1}{3}(|\overleftarrow{A}_1| + \frac{2}{3}m$ and $|S| = |S^1| + |S^2| = |\overleftarrow{A}_1| + \frac{2}{3}|\overleftarrow{A}_2| \ge |\overleftarrow{A}_1| + \frac{2}{3}((1 - \frac{6}{c+5})m - |\overleftarrow{A}_1|) = \frac{1}{3}|\overleftarrow{A}_1| + \frac{2}{3}(1 - \frac{6}{c+5})m$ which implies the desired ratio. ◀

# 4 Kernelization

In all this section we consider the decision problem $C_3$-PACKING-$T$ parameterized by the size of the solution. Thus, an input is a pair $I = (T, k)$ and we say that $I$ is positive iff there exists a set of $k$ vertex disjoint triangles in $T$.

## 4.1 Positive results for sparse instances

Observe first that the kernel in $O(k^2)$ vertices for 3-Set PACKING of [1] directly implies a kernel in $O(k^2)$ vertices for $C_3$-PACKING-$T$. Indeed, given an instance $(T = (V, A), k)$ of
XX:14 Triangle packing in (sparse) tournaments: approximation and kernelization.

$C_3$-PACKING-T, we create an instance $(I' = (V, C), k)$ of 3-SET PACKING by creating an hyperedge $c \in C$ for each triangle of $\mathcal{T}$. Then, as the kernel of $[1]$ only removes vertices, it outputs an induced instance $(\bar{I}' = I'[V'], k')$ of $I$ with $V' \subseteq V$, and thus this induced instance can be interpreted as a subtournament, and the corresponding instance $(\mathcal{T}[V'], k')$ is an equivalent tournament with $\mathcal{O}(k^2)$ vertices.

As shown in the next theorem, as we could expect it is also possible to have kernel bounded by the number of backward arcs.

**Theorem 11.** $C_3$-PACKING-T admits a polynomial kernel with $\mathcal{O}(m)$ vertices, where $m$ is the number of arcs in a given FAS of the input.

**Proof.** Let $I = (\mathcal{T}, k)$ be an input of the decision problem associated to $C_3$-PACKING-T. Observe first that we can build in polynomial time a linear ordering $\sigma(\mathcal{T})$ whose backward arcs $\bar{A}(\mathcal{T})$ correspond to the given FAS. We will obtain the kernel by removing useless vertices of degree (0,0). Let us define a bipartite graph $G = (V_1, V_2, E)$ with $V_1 = \{v_a^1 : a \in \bar{A}(\mathcal{T})\}$ and $V_2 = \{v_l^2 : v_l \in V_{(0,0)}\}$. Thus, to each backward arc we associate a vertex in $V_1$ and to each vertex $v_l$ with $d(v_l) = (0,0)$ we associate a vertex in $V_2$. Then, $\{v_a^1, v_l^2\} \in E$ iff $(h(a), v_l, t(a))$ is a triangle in $\mathcal{T}$. By Hall's theorem, we can in polynomial time partition $V_1$ and $V_2$ into $A_1 \cup A_2$, $V_2 = B_0 \cup B_1 \cup B_2$ such that $N(A_2) \subseteq B_2$, $|B_2| \le |A_2|$, and there is a perfect matching between vertices of $A_1$ and $B_1$ ($B_0$ is simply defined by $B_0 = V_2 \setminus (B_1 \cup B_2)$).

For any $i, 0 \le i \le 2$, let $X_i = \{v_l \in V_{(0,0)} : v_l^2 \in B_i\}$ be the vertices of $\mathcal{T}$ corresponding to $B_i$. Let $V_{\ne (0,0)} = V(\mathcal{T}) \setminus V_{(0,0)}$. Notice that $|V_{\ne (0,0)}| \le 2m$. We define $\mathcal{T}' = \mathcal{T}[V_{\ne (0,0)} \cup X_1 \cup X_2]$ the sub-tournament obtained from $\mathcal{T}$ by removing vertices of $X_0$, and $I' = (\mathcal{T}', k)$. We point out that this definition of $\mathcal{T}'$ is similar to the final step of the kernel of $[1]$ as our partition of $V_1$ and $V_2$ (more precisely $(A_1, B_0 \cup B_1)$) corresponds in fact to the crown decomposition of $[1]$. Observe that $|V(\mathcal{T}')| \le 2m + |A_1| + |A_2| \le 3m$, implying the desired bound of the number of vertices of the kernel.

It remains to prove that $I$ and $I'$ are equivalent. Let $k \in \mathbb{N}$, and let us prove that there exists a solution $S$ of $\mathcal{T}$ with $|S| \ge k$ iff there exists a solution $S'$ of $\mathcal{T}'$ with $|S'| \ge k$. Observe that the $\leftarrow$ direction is obvious as $\mathcal{T}'$ is a subtournament of $\mathcal{T}$. Let us now prove the $\Rightarrow$ direction. Let $S$ be a solution of $\mathcal{T}$ with $|S| \ge k$. Let $S = S_{(0,0)} \cup S_1$ with $S_{(0,0)} = \{t \in S : t = (h(a), v, t(a))$ with $v \in V_{(0,0)}$, $a \in \bar{A}(\mathcal{T})\}$ and $S_1 = S \setminus S_{(0,0)}$. Observe that $V(S_1) \cap V_{(0,0)} = \emptyset$, implying $V(S_1) \subseteq V_{\ne (0,0)}$. For any $i \in [2]$, let $S_i^{(0,0)} = \{t \in S_{(0,0)} : t = (h(a), v, t(a))$ with $v \in V_{(0,0)}$, $v_a^1 \in A_i\}$ be a partition of $S_{(0,0)}$. We define $S' = S_1 \cup S_{(0,0)}^2 \cup S_{(0,0)}^{\prime 1}$, where $S_{(0,0)}^{\prime 1}$ is defined as follows. For any $v_a^1 \in A_1$, let $v_{\mu(a)}^2 \in B_1$ be the vertex associated to $v_a^1$ in the $(A_1, B_1)$ matching. To any triangle $t = (h(a), v, t(a)) \in S_{(0,0)}^{\prime 1}$ we associate a triangle $f(t) = (h(a), v_{\mu(a)}, t(a)) \in S_{(0,0)}^{\prime 1}$, where by definition $v_{\mu(a)} \in X_1$. For the sake of uniformity we also say that any $t \in S_1 \cup S_{(0,0)}^2$ is associated to $f(t) = t$.

Let us now verify that triangles of $S'$ are vertex disjoint by verifying that triangles of $S_{(0,0)}^{\prime 1}$ do not intersect another triangle of $S'$. Let $f(t) = (h(a), v_{\mu(a)}, t(a)) \in S_{(0,0)}^{\prime 1}$. Observe that $h(a)$ and $t(a)$ cannot belong to any other triangle $f(t')$ of $S'$ as for any $f(t'') \in S'$, $V(f(t'')) \cap V_{\ne (0,0)} = V(t'') \cap V_{\ne (0,0)}$ (remember that we use the same notation $V_{\ne (0,0)}$ to denote vertices of degree (0,0) in $\mathcal{T}$ and $\mathcal{T}'$). Let us now consider $v_{\mu(a)}$. For any $f(t') \in S_1$, as $V(f(t')) \cap V_{(0,0)} = \emptyset$ we have $v_{\mu(a)} \notin V(f(t'))$. For any $f(t') = (h(a'), v_l, t(a')) \in S_{(0,0)}^2$, we know by definition that $v_a^1 \in A_2$, implying that $v_l^2 \in B_2$ (and $v_l \in X_2$) as $N(A_2) \subseteq B_2$ and thus that $v_l \ne v_{\mu(a)}$. Finally, for any $f(t') = (h(a'), v_l, t(a')) \in S_{(0,0)}^{\prime 1}$, we know that $v_l = v_{\mu(a')}$, where $a \ne a'$, leading to $v_l \ne v_{\mu(a)}$ as $\mu$ is a matching. $\quad$
Using the previous result we can provide a $O(k)$ vertices kernel for $C_3$-PACKING-T restricted to sparse tournaments.

**Theorem 12.** *C<sub>3</sub>-PACKING-T restricted to sparse tournaments admits a polynomial kernel with O(k) vertices, where k is the size of the solution.*

**Proof.** Let $I = (\mathcal{T}, k)$ be an input of the decision problem associated to $C_3$-PACKING-T such that $\mathcal{T}$ is a sparse tournament. We say that an arc $a$ is a consecutive backward arc of $\sigma(\mathcal{T})$ if it is a backward arc of $\mathcal{T}$ and $a = v_{i+1}v_i$ with $v_i$ and $v_{i+1}$ being consecutive in $\sigma(\mathcal{T})$. If $\mathcal{T}$ admits a consecutive backward arc $v_iv_{i+1}$ then we can exchange $v_i$ and $v_{i+1}$ in $\mathcal{T}$. The backward arcs of the new linear ordering is exactly $\overleftarrow{A}(\mathcal{T}) \setminus v_{i+1}v_i$ and so is still a matching. Hence we can assume that $\mathcal{T}$ does not contain any consecutive backward arc. Now if $|\overleftarrow{A}(\mathcal{T})| < 5k$ then by Theorem 11 we have a kernel with $O(k)$ vertices. Otherwise, if $|\overleftarrow{A}(\mathcal{T})| \ge 5k$ we will prove that $T$ is a YES instance of $C_3$-PACKING-T. Indeed we can greedily produce a family of $k$ vertex disjoint triangles in $T$. For that consider a backward arc $v_jv_i$ of $\mathcal{T}$, with $i < j$. As $v_jv_i$ is not consecutive there exists $l$ with $i < l < j$ and we select the triangle $v_iv_jv_l$ and remove the vertices $v_i$, $v_l$ and $v_j$ from $\mathcal{T}$. Denote by $\mathcal{T}'$ the resulting tournament and let $\sigma(\mathcal{T}')$ be the order induced by $\sigma(\mathcal{T})$ on $\mathcal{T}'$. So we loose at most 2 backward arcs in $\sigma(\mathcal{T}')$ ($v_jv_i$ and a possible backward arc containing $v_l$) and create at most 3 consecutive backward arcs by the removing of $v_i$, $v_l$ and $v_j$. Reducing these consecutive backward arcs as previously, we can assume that $\sigma(\mathcal{T}')$ does not contain any consecutive backward arc and satisfies $|\overleftarrow{A}(\mathcal{T}')| \ge |\overleftarrow{A}(\mathcal{T})| - 5 \ge 5(k-1)$. Finally repeating inductively this arguments, we obtain the desired family of $k$ vertex-disjoint triangles in $\mathcal{T}$, and $\mathcal{T}$ is a YES instance of $C_3$-PACKING-T.

◀

## 4.2 No (generalised) kernel in $O(k^{2-\epsilon})$

In this section we provide an OR-cross composition (see Definition 21 in Appendix) from $C_3$-PERFECT-PACKING-T restricted to instances of Theorem 7 to $C_3$-PERFECT-PACKING-T parameterized by the total number of vertices.

**Definition of the instance selector** The next lemma builds a special tournament, called an *instance selector* that will be useful to design the cross composition.

**Lemma 13.** For any $\gamma = 2^{\gamma'}$ and $\omega$ we can construct in polynomial time (in $\gamma$ and $\omega$) a tournament $P_{\omega,\gamma}$ such that

- there exists $\gamma$ subsets of $\omega$ vertices $X^i = \{x_j^i : j \in [\omega]\}$, that we call the distinguished set of vertices, such that

- the $X^i$ have pairwise empty intersection

- for any $i \in [\gamma]$, there exists a packing $S$ of triangles of $P_{\omega,\gamma}$ such that $V(P_{\omega,\gamma}) \setminus V(S) = X^i$ (using this packing of $P_{\omega,\gamma}$ corresponds to select instance $i$)

- for any packing $S$ of triangles of $P_{\omega,\gamma}$ with $|V(S)| = |V(P_{\omega,\gamma})| - \omega$ there exists $i \in [\gamma]$ such that $V(P_{\omega,\gamma}) \setminus V(S) \subseteq X^i$

- $|V(P_{\omega,\gamma})| = O(\omega\gamma)$.

**Proof.** Let us first describe vertices of $P_{\omega,\gamma}$. For any $i \in [\gamma - 1]_0$ (where $[x]_0$ denotes $\{0, \dots, x\}$) let $X^i = \{x_j^i : j \in [\omega]\}$, and let $X = \cup_{i \in [\gamma-1]_0} X^i$. For any $l \in [\gamma' - 1]_0$, let $V^l = \{v_k^l, k \in [|V^l|]\}$ be the vertices of level $l$ with $|V^l| = \omega\gamma/2^l + 2$, and $V = \cup_{l \in [\gamma'-1]_0} V^l$. Finally, we add a set $\alpha = \{\alpha^l : l \in [\gamma' - 1]_0\}$ containing one dummy vertex for each level and finally set $V(P_{\omega,\gamma}) = X \cup V \cup \alpha$. Observe that $|V(P_{\omega,\gamma})| = \omega\gamma + \sum_{l \in [\gamma'-1]_0} (|V^l| + 1) =$
<figure><img src="image_10.png" /><figcaption>Figure 6 An example of the instance selector, where $\omega = 3$ and $\gamma = 4$. All depicted arcs are backward arcs.</figcaption></figure>

$\mathcal{O}(\omega\gamma)$. Let us now describe $\sigma(P_{\omega,\gamma})$ and $\overleftarrow{A}(P_{\omega,\gamma})$ recursively. Let $P_{\omega,\gamma}^0$ be the tournament such that $\sigma(P_{\omega,\gamma}^0) = (v_1^0, x_1^0, v_2^0, x_1^1, \dots, v_\gamma^0, x_1^{\gamma-1})$ ($v_{\gamma+1}^0, x_2^0, \dots, v_{2\gamma}^0, x_2^{\gamma-1}$) $\dots$ $(v_{(\omega-1)\gamma+1}^0, x_\omega^0, \dots, v_{\omega\gamma}^0, x_\omega^{\gamma-1})$ ($v_{\omega\gamma+1}^0, \alpha^1, v_{\omega\gamma+2}^0$) and $\overleftarrow{A}(P_{\omega,\gamma}^0) = Z_P^0$ where $Z_P^0 = A_P^0 \cup A'_P^0$ with $A_P^0 = \{v_{k+1}^0, v_k^0 : k \in [|V^0| - 2]\}$ and $A'_P^0 = \{v_{|V^0|}^0, v_{|V^0|-1}^0, v_{|V^0|}^0, v_1^0\}$.

Then, given a tournament $P_{\omega,\gamma}^l$ with $0 \le l < \gamma' - 1$, we construct the tournament $P_{\omega,\gamma}^{l+1}$ such that the vertices of $P_{\omega,\gamma}^{l+1}$ are those of $P_{\omega,\gamma}^l$ to which are added the set $V^{l+1}$. For $j \in [|V^{l+1}| - 2]$, we add the vertex $v_j^{l+1}$ of $V^{l+1}$ just after the vertex $v_{2j-1}^l$ in the order of $P_{\omega,\gamma}^{l+1}$, and we for $i \in \{0,1\}$ we add vertex $v_{|V^{l+1}|-i}^l$ just after $v_{|V^l|-i}^l$. Similarly, we add the vertex $\alpha^{l+1}$ just after the vertex $\alpha^l$. The backward arcs of $P_{\omega,\gamma}^{l+1}$ are defined by: $\overleftarrow{A}(P_{\omega,\gamma}^{l+1}) = \overleftarrow{A}(P_{\omega,\gamma}^l) \cup Z_P^{l+1}$ where $Z_P^{l+1} = A_P^{l+1} \cup A'_P^{l+1}$ are called the *arcs of level $l$*, with $A_P^{l+1} = \{v_{k+1}^{l+1}v_k^{l+1} : k \in [|V^{l+1}| - 2]\}$ and $A'_P^{l+1} = \{v_{|V^{l+1}|}^{l+1}v_{|V^{l+1}|-1}^{l+1}, v_{|V^{l+1}|}^{l+1}v_1^{l+1}\}$. We can now define our gadget tournament $P_{\omega,\gamma}$ as the tournament corresponding to $P_{\omega,\gamma}^{\gamma'-1}$. We refer the reader to Figure 6 where an example of the gadget is depicted, where $\omega = 3$ and $\gamma = 4$.

In all the following given $i \in [\gamma - 1]_0$ we call the last $x$ bits (resp. the $x^{th}$ bit) $i$ its $x$ right most (resp. the $x^{th}$, starting from the right) bits in the binary representation of $i$. Let us now state the following observations.

Δ₁ The vertices of $X$ have degree (0,0) in $P_{\omega,\gamma}$.

Δ₂ For any $l \in [\gamma' - 1]_0$, the extremities of the arcs of level $l$ are exactly $V^l$ ($V(Z_P^l) = V^l$) and the arcs of $Z_P^l$ induce an even circuit on $V^l$.

Δ₃ For any $a \in A_P^l$, the span of $a$ contains $2^l$ consecutive vertices of $X$, more precisely $s(a) \cap X = \{x_j^i, \dots, x_j^{i+2^l-1}\}$ for $j \in [m]$ and $i$ such that the $l-1$ last bits of $i$ are equal to 0.

Δ₄ There is a unique partition $Z_P^l = Z_P^{l,0} \cup Z_P^{l,1}$ such that $|Z_P^{l,0}| = |Z_P^{l,1}| = \mu^l$, the size of a maximum matching of backward arcs in $P_{\omega,\gamma}[V^l]$, such that each $Z_P^{l,x}$ is a matching (for any $a, a' \in Z_P^{l,x}, V(a) \cap V(a') = \emptyset$), and such that $\cup_{a \in Z_P^{l,x} \setminus A_P^{l'}} s(a) \cap X$ is the set of all vertices $x_j^i$ of $X$ whose $l^{th}$ bit of $i$ is $x$.

Now let us first prove that for any $i \in [\gamma - 1]_0$, there exists an packing $S$ of $P_{\omega,\gamma}$ such that $V(P_{\omega,\gamma}) \setminus V(S) = X^i$. Let $(x_{\gamma'-1}, \dots, x_0)$ be the binary representation of $i$. Let us define recursively $S = \cup_{l \in [\gamma'-1]_0} S_l$ in the following way. We maintain the invariant that for any $l$, the remaining vertices of $X$ after defining $\cup_{z \in [l]_0} S_z$ are all the vertices of $X$ having their $l$ last bits equal to $(x_{l-1}, \dots, x_0)$. We define $S_l$ as the $\mu^l - 1$ triangles $\{(h(a), x_a, t(a), a \in Z_P^{l,1-x_l}) \setminus A_P^{l'}\}$ such that $x_a$ is the unique remaining vertex of $X$ in $s(a)$ (by Δ₃ and our invariant of the $S_{\le l}$, there remains exactly one vertex in $s(a)$, and by Δ₄ these $\mu^l - 1$ triangles consume all remaining vertices of $X$ whose $l^{th}$ bit is $1-x_l$), and a last triangle using an arc in $A_P^{l'}$ with $t = (v_{|V^0|}^l, \alpha^l, v_{|V^0|-1}^l)$ if $x_l = 1$ and $t = (v_0^l, \alpha^l, v_{|V^0|}^0)$ otherwise. Thus, by our invariant, the remaining vertices of $X$ after defining $S$ are exactly $X^i$. As $S$ also consumes $\alpha$ and $V$ we have $V(P_{\omega,\gamma}) \setminus V(S) = X^i$. Notice that this definition of $S$ shows that $|V(P_{\omega,\gamma})| - m = |V(S)| = 3 \sum_{l \in [\gamma'-1]_0} \mu^l$

Let us now prove that for any packing $S$ of $P_{\omega,\gamma}$ with $|V(S)| = |V(P_{\omega,\gamma})| - m =$
$3\sum_{l \in [\gamma' - 1]_0} \mu^l$, there exists $i \in [\gamma]$ such that $V(P_{\omega,\gamma}) \setminus V(S) \subseteq X^i$. Let $t_1, \dots, t_\mu$ be the triangles of $S$. For any $t_k$ of $S$, we associate one backward arc $a_k$ of $t_k$ (if there are two backward arcs, we pick one arbitrarily). Let $Z = \{a_k : k \in \llbracket S \rrbracket\}$ and for every $l \in |\gamma' - 1]_0$ let $Z^l = \{a_k \in A : V(a_k) \subset V^l\}$ the set of the backward arcs which are between two vertices of level $l$. Notice that the $Z^l$'s form a partition of $Z$. For any $l \in [\gamma' - 1]_0$, we have $|Z^l| \le \mu^l$ as two arcs of $Z^l$ correspond to two different triangles of $S$, implying that $Z^l$ is a matching. Furthermore, as $|S| = |Z| = \sum_{l \in [\gamma' - 1]_0} |Z^l| = \mu = \sum_{l \in [\gamma']} \mu^l$, we get the equality $|Z^l| = \mu^l$ for any $l \in [\gamma' - 1]_0$. This implies that for each $Z^l$ there exists $x$ such that $Z^l = Z_P^{l,x}$, implying also that $V(Z^l) = V^l$, and $V(Z) = V$.

Let $A^l = Z^l \setminus A_P^l$, $S^l = \{t_k \in S : a_k \in A^l\}$. We can now prove by induction that all the remaining vertices $R_l = X \setminus V(\cup_{x \in [l]} S^l)$ have the same $l$ last bits. Notice that since all vertices of $V$ are already used, and as triangles of $S^l$ cannot use a dummy vertex in $\alpha$, all triangles of $S^l$ must be of the from $(h(a_k), x, t(a_k))$ with $x \in X$. As $A^l = Z_P^{l,x} \setminus A_P^{l'}$, by $\Delta_4$ we know that $\cup_{a \in A^l} s(a) \cap X$ contains all the remaining vertices of $X$, and thus of $R_{l-1}$, whose $l^{th}$ bit is $x$. Moreover, by $\Delta_3$ we know that for any $a \in A^l$ we have $|R_{l-1} \cap s(a)| \le 1$ because as $a \in A_P^l$ we know exactly the structure of $s(a) \cap X$, and if there remain two vertices in $s(a) \cap X$ then their last $l-1$ last bits would be different. Thus, as triangles of $S^l$ remove on vertex in the span of each $a \in A^l$, they remove all vertices of $R_{l-1}$ whose $l^{th}$ bit is $x$, implying the desired result.

<figure><img src="image_11.png" /></figure>

**Definition of the reduction** We suppose given a family of $t$ instances $F = \{\mathcal{I}_l, l \in [t]\}$ of $C_3$-PERFECT-PACKING-T restricted to instances of Theorem 7 where $\mathcal{I}_l$ asks if there is a perfect packing in $\mathcal{T}_l = L_l K_l$. We chose our equivalence relation in Definition 21 such that there exist $n$ and $m$ such that for any $l \in [t]$ we have $|V(L_l)| = n$ and $|V(K_l)| = m$. We can also copy some of the $t$ instances such that $t$ is a square number and $g = \sqrt{t}$ is a power of two. We reorganize our instances into $F = \{\mathcal{I}_{(p,q)} : 1 \le p, q \le g\}$ where $\mathcal{I}_{(p,q)}$ asks if there is a perfect packing in $\mathcal{T}_{(p,q)} = L_p K_q$. Remember that according to Theorem 7, all the $L_p$ are equals, and all the $K_q$ are equals. We point out that the idea of using a problem on "bipartite" instances to allow encoding $t$ instances on a "meta" bipartite graph $G = (A, B)$ (with $A = \{A_i, i \in \sqrt{t}\}$, $B = \{B_i, i \in \sqrt{t}\}$) such that each instance $p, q$ is encoded in the graph induced by $G[A_i \cup B_i]$ comes from [8]. We refer the reader to Figure 7 which represents the different parts of the tournament. We define a tournament $G = LM_G \tilde{L} \tilde{M}_G P_{(n,g)}$, where $L = L_1 \dots L_g$, $\tilde{M}_G$ is a set of $n$ vertices of degree (0,0), $M_G$ is a set of $(g-1)n$ vertices of degree (0,0), $\tilde{L} = \tilde{L}_1 \dots \tilde{L}_g$ where each $\tilde{L}_p$ is a set of $n$ vertices, and $P_{(n,g)}$ is a copy of the instance selector of Lemma 13. Then, for every $p \in [g]$ we add to $G$ all the possible $n^2$ backward arcs going from $\tilde{L}_p$ to $L_p$. Finally, for every distinguished set $X^p$ of $P_{(n,g)}$ (see in Lemma 13), we add all the possible $n^2$ backward arcs from $X^p$ to $\tilde{L}_p$.

Now, in a symmetric way we define a tournament $D = KM_D \tilde{K} \tilde{M}_D P'_{(m,g)}$, where $K = K_1 \dots K_g$, $\tilde{M}_D$ is a set of $m$ vertices of degree (0,0), $M_D$ is a set of $(g-1)m$ vertices of degree (0,0), $\tilde{K} = \tilde{K}_1 \dots \tilde{K}_g$ where each $\tilde{K}_q$ is a set of $m$ vertices, and $P'_{(m,g)}$ is a copy of the instance selector of Lemma 13. Then, for every $q \in [g]$ we add to $G$ all the $m^2$ possible backward arcs going from $\tilde{K}_p$ to $K_p$. Finally, for every distinguished set $X'^q$ of $P'_{(m,g)}$ we add all the possible $m^2$ backward arcs from $X'^q$ to $\tilde{K}_q$. Finally, we define $\mathcal{T} = GD$. Let us add some backward arcs from $D$ to $G$. For any $p$ and $q$ with $1 \le p, q \le g$, we add backward arcs from $K_q$ to $L_p$ such that $\mathcal{T}[K_q L_p]$ corresponds to $\mathcal{T}_{(p,q)}$. Notice that this is possible as for any fixed $p$, all the $\mathcal{T}_{(p,q)}$, $q \in [g]$ have the same left part $L_p$, and the same goes for any fixed right part.
<figure><img src="image_12.png" /><figcaption>■ **Figure 7** A example of the weak composition. All depicted arcs are backward arcs. Bold arcs represents the $n^2$ (or $m^2$) possible arcs between the two groups.</figcaption></figure>

**Restructuration lemmas** Given a set of triangles $S$ we define $S_{\subseteq P'} = \{t \in S | V(t) \subseteq P'_{(m,g)}\}$, $S_{\subseteq P} = \{t \in S : V(t) \subseteq P_{(n,g)}\}$, $S_{\tilde{M}_D} = \{t \in S : V(t) \text{ intersects } \tilde{K}, \tilde{M}_D \text{ and } P'_{m,g}\}$, $S_{M_D} = \{t \in S : V(t) \text{ intersects } K, M_D \text{ and } \tilde{K}\}$, $S_{\tilde{M}_G} = \{t \in S : V(t) \text{ intersects } \tilde{L}, \tilde{M}_G \text{ and } P_{n,g}\}$, $S_{M_G} = \{t \in S : V(t) \text{ intersects } L, M_G \text{ and } \tilde{L}\}$, $S_D = \{t \in S : V(t) \subseteq V(D)\}$, $S_G = \{t \in S : V(t) \subseteq V(G)\}$, and $S_{GD} = \{t \in S : V(t) \text{ intersects } V(G) \text{ and } V(D)\}$. Notice that $S_G, S_{GD}, S_D$ is a partition of $S$.

**Claim 13.1.** If there exists a perfect packing $S$ of $\mathcal{T}$, then $|S_{\tilde{M}_D}| = m$ and $|S_{M_D}| = (g-1)m$. This implies that $V(S_{\tilde{M}_D} \cup S_{M_D}) \cap V(\tilde{K}) = V(\tilde{K})$, meaning that the vertices of $\tilde{K}$ are entirely used by $S_{\tilde{M}_D} \cup S_{M_D}$.

**Proof.** We have $|S_{\tilde{M}_D}| \le m$ since $|\tilde{M}_D| = m$. We obtain the equality since the vertices of $\tilde{M}_D$ only lie in the span of backward arcs from $P'_{m,g}$ to $\tilde{K}$, and they are not the head or the tail of a backward arc in $\mathcal{T}$. Thus, the only way to use vertices of $\tilde{M}_D$ is to create triangles in $S_{\tilde{M}_D}$, implying $|S_{\tilde{M}_D}| \ge m$. Using the same kind of arguments we also get $|S_{M_D}| = (g-1)m$. As $|V(\tilde{K})| = gm$ we get the last part of the claim. ◀

**Claim 13.2.** If there exists a perfect packing $S$ of $\mathcal{T}$, then there exists $q_0 \in [g]$ such that $\tilde{K}_S = \tilde{K}_{q_0}$, where $\tilde{K}_S = \tilde{K} \cap V(S_{\tilde{M}_D})$.

**Proof.** Let $S_{P'}$ be the triangles of $S$ with at least one vertex in $P'_{m,g}$. As according to Claim 13.1 vertices of $\tilde{K}$ are entirely used by $S_{\tilde{M}_D} \cup S_{M_D}$, the only way to consume vertices of $P'_{m,g}$ is by creating local triangles in $P'_{m,g}$ or triangles in $S_{\tilde{M}_D}$. In particular, we cannot have a triangle $(u, v, w)$ with $\{u, v\} \subseteq \tilde{K}$ and $w \in P'_{m,g}$, or with $u \in \tilde{K}$ and $\{v, w\} \subseteq P'_{m,g}$. More formally, we get the partition $S_{P'} = S_{\subseteq P'} \cup S_{\tilde{M}_D}$. As $S$ is a perfect packing and uses in particular all vertices of $P'_{m,g}$ we get $|V(S_{P'})| = |V(P'_{m,g})|$, implying $|V(S_{\subseteq P'})| = |V(P'_{m,g})| - m$ by Claim 13.1. By Lemma 13, this implies that there exists $q_0 \in [g]$ such that $X' \subseteq X'^{q_0}$ where $X' = V(P'_{m,g}) \setminus V(S_{\subseteq P'})$. As $X'$ are the only remaining vertices that can be used by triangles of $S_{\tilde{M}_D}$, we get that the $m$ triangles of $S_{\tilde{M}_D}$ are of the form $(u, v, w)$ with $u \in \tilde{K}_{q_0}, v \in \tilde{M}_D$, and $w \in X'$.

**Claim 13.3.** If there exists a perfect packing $S$ of $\mathcal{T}$, then there exists $q_0 \in [g]$ such that $V(S_{P'} \cup S_{\tilde{M}_D} \cup S_{M_D}) = V(D) \setminus K_{q_0}$.

**Proof.** By Claim 13.1 we know that $|S_{M_D}| = (g-1)m$. As by Claim 13.2 there exists $q_0 \in [g]$ such that $\tilde{K}_S = \tilde{K}_{q_0}$, we get that the $(g-1)m$ triangles of $S_{M_D}$ are of the form $(u, v, w)$ with $u \in K \setminus K_{q_0}, v \in M_D$, and $w \in \tilde{K} \setminus \tilde{K}_{q_0}$. ◀
**Lemma 14.** If there exists a perfect packing $S$ of $\mathcal{T}$, then $V(S_{GD}) \cap V(G) \subseteq V(L)$. Informally, triangles of $S_{GD}$ do not use any vertex of $M_G, \tilde{L}, \tilde{M}_T$ and $P_{n,g}$.

**Proof.** By Claim 13.3, there exists $q_0 \in [g]$ such that $V(S_{P'} \cup S_{\tilde{M}_D} \cup S_{M_D}) = V(D) \setminus K_{q_0}$. By Theorem 7 we know that $K_{q_0} = K_{(q_0,1)} \dots K_{(q_0,m')}'$ for some $m'$ (we even have $m' = \frac{m}{2}$), where for each $j \in [m']$ we have $V(K_{(q_0,j)}) = (\theta_j, c_j)$. Moreover, for any $p \in [g]$, the last property of Theorem 7 ensures that for any $a \in \tilde{A}(\mathcal{T}_{(p,q_0)})$, $V(a) \cap V(K_{q_0}) \neq \emptyset$ implies $a = vc_j$ for $v \in L_p$. So no arc of $\tilde{A}(\mathcal{T}_{(p,q_0)})$, and thus no arc of $\mathcal{T}$ is entirely included in $K_{q_0}$. This implies that $S$ cannot cover the vertices of $K_{q_0}$ using triangles $t$ with $V(t) \subseteq V(K_{q_0})$, and thus that all these vertices must be used by triangles of $S_{GD}$, implying that $V(S_{GD}) \cap V(D) = K_{q_0}$. The last property of Theorem 7 also implies that all the $\theta_j$ have a left degree equal to 0 in $\mathcal{T}$, or equivalently that there is no arc $a$ of $\mathcal{T}$ such that $t(a) = \theta_j$ and $h(a) < \theta_j$. Thus, by induction for any $j$ from $m'$ to 1, we can prove that the only way for triangles of $S_{GD}$ to use $\theta_j$ is to create a triangle $t_j = (v, \theta_j, c_j)$ with necessarily $v \in V(L)$. $\quad$

Lemma 14 will allow us to prove Claims 14.1, 14.2 and 14.3 using the same arguments as in the right part (D) of the tournament as all vertices of $M_G, \tilde{L}, \tilde{M}_T$ and $P_{n,g}$ must be used by triangles in $S_G$.

**Claim 14.1.** If there exists a perfect packing $S$ of $\mathcal{T}$, then $|S_{\tilde{M}_G}| = n$ and $|S_{M_G}| = (g-1)n$. This implies that $V(S_{\tilde{M}_G} \cup S_{M_G}) \cap V(\tilde{L}) = V(\tilde{L})$, meaning that vertices of $\tilde{L}$ are entirely used by $S_{\tilde{M}_G} \cup S_{M_G}$.

**Proof.** We have $|S_{\tilde{M}_G}| \le n$ since $|\tilde{M}_G| = n$. Lemma 14 implies that all vertices of $\tilde{M}_G$ must be used by triangles of $S_G$, and thus using arcs whose both endpoints lie in $V(G)$. As vertices of $\tilde{M}_G$ are not the head or the tail of a backward arc in $\mathcal{T}$, we get that the only way for $S_G$ to use vertices of $\tilde{M}_G$ is to create triangles in $S_{\tilde{M}_G}$, implying $|S_{\tilde{M}_G}| \ge n$. Using the same kind of arguments (and as all vertices of $M_G$ must also be used by triangles of $S_G$) we also get $|S_{M_G}| = (g-1)n$. As $|V(\tilde{L})| = gn$ we get the last part of the claim. $\quad$

**Claim 14.2.** If there exists a perfect packing $S$ of $\mathcal{T}$, then there exists $p_0 \in [g]$ such that $\tilde{L}_S = \tilde{L}_{p_0}$, where $\tilde{L}_S = \tilde{L} \cap V(S_{\tilde{M}_G})$.

**Proof.** Lemma 14 implies that all vertices of $\tilde{M}_G$ and $P_{(n,g)}$ must be used by triangles in $S_G$. Let $S_P$ be the triangles of $S_G$ with at least one vertex in $P_{n,g}$. As according to Claim 14.1 vertices of $\tilde{L}$ are entirely used by $S_{\tilde{M}_G} \cup S_{M_G}$, the only way for $S_G$ to consume vertices of $P_{n,g}$ is by creating local triangles in $P_{n,g}$ or triangles in $S_{\tilde{M}_G}$. In particular, we cannot have a triangle $(u,v,w)$ with $\{u,v\} \subseteq \tilde{L}$ and $w \in P_{n,g}$, or with $u \in \tilde{L}$ and $\{v,w\} \subseteq P_{n,g}$. More formally, we get the partition $S_P = S_{\subseteq P} \cup S_{\tilde{M}_G}$. As $S_G$ uses in particular all vertices of $P_{n,g}$ we get $|V(S_P)| = |V(P_{n,g})|$, implying $|V(S_{\subseteq P})| = |V(P_{n,g})| - n$ by Claim 14.1. By Lemma 13, this implies that there exists $p_0 \in [g]$ such that $X \subseteq X^{p_0}$ where $X = V(P_{n,g}) \setminus V(S_{\subseteq P})$. As $X$ are the only remaining vertices that can be used by triangles of $S_{\tilde{M}_G}$, we get that the $n$ triangles of $S_{\tilde{M}_G}$ are of the form $(u,v,w)$ with $u \in \tilde{L}_{p_0}$, $v \in \tilde{M}_G$, and $w \in X$. $\quad$

**Claim 14.3.** If there exists a perfect packing $S$ of $\mathcal{T}$, then there exists $p_0 \in [g]$ such that $V(S_P \cup S_{\tilde{M}_G} \cup S_{M_G}) = V(G) \setminus L_{p_0}$.

**Proof.** By Claim 13.1 we know that $|S_{M_G}| = (g-1)n$. As by Claim 14.2 there exists $p_0 \in [g]$ such that $\tilde{L}_S = \tilde{L}_{p_0}$, we get that the $(g-1)n$ triangles of $S_{M_G}$ are of the form $(u,v,w)$ with $u \in L \setminus L_{p_0}$, $v \in M_G$, and $w \in \tilde{L} \setminus \tilde{L}_{p_0}$. $\quad$
We are now ready to state our final claim is now straightforward as according Claim 13.3 and 14.3 we can define $S_{(p_0,q_0)} = S \setminus ((S_{P'} \cup S_{\tilde{M}_D} \cup S_{M_D}) \cup (S_P \cup S_{\tilde{M}_G} \cup S_{M_G}))$.

► Claim 14.4. If there exists a perfect packing $S$ of $\mathcal{T}$, there exists $p_0, q_0 \in [g]$ and $S_{(p_0,q_0)} \subseteq S$ such that $V(S_{(p_0,q_0)}) = V(\mathcal{T}_{(p_0,q_0)})$ (or equivalently such that $S_{(p_0,q_0)}$ is a perfect packing of $\mathcal{T}_{(p_0,q_0)}$).

**Proof of the weak composition**

► **Theorem 15.** For any $\epsilon > 0$, $C_3$-PERFECT-PACKING-T (parameterized by the total number of vertices $N$) does not admit a polynomial (generalized) kernelization with size bound $O(N^{2-\epsilon})$ unless NP $\subseteq$ coNP/Poly.

**Proof.** Given $t$ instances $\{\mathcal{I}_l\}$ of $C_3$-PERFECT-PACKING-T restricted to instances of Theorem 7, we define an instance $\mathcal{T}$ of $C_3$-PERFECT-PACKING-T as defined in Section 4. We recall that $g = \sqrt{t}$, and that for any $l \in [t]$, $|V(L_l)| = n$ and $|V(K_l)| = m$. Let $N = |V(\mathcal{T})|$. As $N = |V(P'_{(m,g)})| + m + (g-1)m + 2mg + |V(P_{(n,g)})| + n + (g-1)n + 2ng$ and $|V(P_{(\omega,\gamma)})| = O(\omega\gamma)$ by Lemma 13, we get $N = O(g(n+m)) = O(t^{\frac{1}{2+o(1)}} \max(|\mathcal{I}_l|))$. Let us now verify that there exists $l \in [t]$ such that $\mathcal{I}_l$ admits a perfect packing iff $\mathcal{T}$ admits a perfect packing. First assume that there exist $p_0, q_0 \in [g]$ such that $\mathcal{I}_{(p_0,q_0)}$ admits a perfect packing. By Lemma 14.4, there is a packing $S_{P'}$ of $P'_{(m,g)}$ such that $V(S_{P'}) = V(P'_{(m,g)}) \setminus X'^{q_0}$. We define a set $S_{\tilde{M}_D}$ of $m$ vertex disjoint triangles of the form $(u, v, w)$ with $u \in \tilde{L}_{q_0}, v \in \tilde{M}_D, w \in X'^{q_0}$. Then, we define a set $S_{M_D}$ of $(g-1)m$ vertex disjoint triangles of the form $(u, v, w)$ with $u \in L \setminus L_{q_0}, v \in M_D, w \in \tilde{L} \setminus \tilde{L}_{q_0}$. In the same way we define $S_P, S_{\tilde{M}_G}$ and $S_{M_G}$. Observe that $V(\mathcal{T}) \setminus ((S_{P'} \cup S_{\tilde{M}_D} \cup S_{M_D}) \cup (S_P \cup S_{\tilde{M}_G} \cup S_{M_G})) = K_{q_0} \cup L_{p_0}$, and thus we can complete our packing into a perfect packing of $\mathcal{T}$ as $\mathcal{I}_{(p_0,q_0)}$ admits a perfect packing. Conversely if there exists a perfect packing $S$ of $\mathcal{T}$, then by Claim 14.4 there exists $p_0, q_0 \in [g]$ and $S_{(p_0,q_0)} \subseteq S$ such that $V(S_{(p_0,q_0)}) = V(\mathcal{T}_{(p_0,q_0)})$, implying that $\mathcal{I}_{(p_0,q_0)}$ admits a perfect packing. ►

► **Corollary 16.** For any $\epsilon > 0$, $C_3$-PACKING-T (parameterized by the size $k$ of the solution) does not admit a polynomial kernel with size $O(k^{2-\epsilon})$ unless NP $\subseteq$ coNP/Poly.

**5 Conclusion and open questions**

Concerning approximation algorithms for $C_3$-PACKING-T restricted to sparse instances, we have provided a $(1 + \frac{6}{c+5})$-approximation algorithm where $c$ is a lower bound of the minspan of the instance. On the other hand, it is not hard to solve by dynamic programming $C_3$-PACKING-T for instances where maxspan is bounded above. Using these two opposite approaches it could be interesting to derive an approximation algorithm for $C_3$-PACKING-T with factor better than 4/3 even for sparse tournaments.

Concerning FPT algorithms, the approach we used for sparse tournament (reducing to the case where $m = O(k)$ and apply the $O(m)$ vertices kernel) cannot work the general case. Indeed, if we were able to sparsify the initial input such that $m' = O(k^{2-\epsilon})$, applying the kernel in $O(m')$ would lead to a tournament of total bit size (by encoding the two endpoint of each arc) $O(m'\log(m')) = O(k^{2-\epsilon})$, contradicting Corollary 16. Thus the situation for $C_3$-PACKING-T could be as in vertex cover where there exists a kernel in $O(k)$ vertices, derived from [16], but the resulting instance cannot have $O(k^{2-\epsilon})$ edges [8]. So it is challenging question to provide a kernel in $O(k)$ vertices for the general $C_3$-PACKING-T problem.
References

1 Faisal N Abu-Khzam. A quadratic kernel for 3-set packing. In *International Conference on Theory and Applications of Models of Computation*, pages 81–87. Springer, 2009.

2 Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi. *Complexity and approximation: Combinatorial optimization problems and their approximability properties*. Springer Science & Business Media, 2012.

3 Piotr Berman and Marek Karpinski. On some tighter inapproximability results. In *International Colloquium on Automata, Languages, and Programming*, pages 200–209. Springer, 1999.

4 Hans L Bodlaender, Bart MP Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. *SIAM Journal on Discrete Mathematics*, 28(1):277–305, 2014.

5 Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. A min-max theorem on feedback vertex sets. *Mathematics of Operations Research*, 27(2):361–371, 2002.

6 Pierre Charbit, Stéphan Thomassé, and Anders Yeo. The minimum feedback arc set problem is np-hard for tournaments. *Combinatorics, Probability and Computing*, 16(01):1–4, 2007.

7 Marek Cygan. Improved approximation for 3-dimensional matching via bounded path-width local search. In *Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on*, pages 509–518. IEEE, 2013.

8 Holger Dell and Dániel Marx. Kernelization of packing problems. In *Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms, SODA’12*, 2012.

9 Rodney G Downey and Michael R Fellows. *Fundamentals of parameterized complexity*, volume 4. Springer, 2013.

10 Venkatesan Guruswami, C Pandu Rangan, Maw-Shang Chang, Gerard J Chang, and CK Wong. The vertex-disjoint triangles problem. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 26–37. Springer, 1998.

11 Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In *Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms*, pages 104–113. Society for Industrial and Applied Mathematics, 2012.

12 Bart MP Jansen and Astrid Pieterse. Sparsification upper and lower bounds for graph problems and not-all-equal sat. *Algorithmica*, pages 1–26, 2015.

13 Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In *Proceedings of the thirty-ninth annual ACM symposium on Theory of computing*, pages 95–103. ACM, 2007.

14 Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh. A 7/3-approximation for feedback vertex sets in tournaments. In *24th Annual European Symposium on Algorithms*, ESA 2016, pages 67:1–67:14, 2016.

15 Hannes Moser. A problem kernelization for graph packing. In *International Conference on Current Trends in Theory and Practice of Computer Science*, pages 401–412. Springer, 2009.

16 George L. Nemhauser and Leslie E. Trotter Jr. Properties of vertex packing and independence system polyhedra. *Mathematical Programming*, 6(1):48–61, 1974.

17 Christos H Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. *Journal of computer and system sciences*, 43(3):425–440, 1991.
A Definitions

Approximation

▶ **Definition 17 ([17]).** Let $\Pi$ and $\Pi'$ be two optimization (maximization or minimization) problems. We say that $\Pi$ $L$-reduces to $\Pi'$ if there are two polynomial-time algorithms $f, g$, and constants $\alpha, \beta > 0$ such that for each instance $I$ of $\Pi$

(a) Algorithm $f$ produces an instance $I' = f(I)$ of $\Pi'$ such that the optima of $I$ and $I'$, $OPT(I)$ and $OPT(I')$, respectively, satisfy $OPT(I') \le \alpha OPT(I)$

(b) Given any solution of $I'$ with cost $c$, algorithm $g$ produces a solution of $I$ with cost $c$ such that $|c - OPT(I)| \le \beta|c' - OPT(I')|$.

▶ **Definition 18.** Let $A$ be an algorithm of a maximization (resp. minimization) problem $\Pi$. For $\rho \ge 1$, we say that $A$ is a $\rho$-approximation of $\Pi$ iff for any instance $I$ of $\Pi$, $A_I \ge OPT(I)/\rho$ (resp. $A_I \le \rho OPT(I)$) where $A_I$ is the value of the solution $A(I)$ and $OPT(I)$ the value of an optimal solution of $I$.

▶ **Definition 19.** Let $\Pi$ be a NP-optimization problem. The problem $\Pi$ is in APX if there exists a constant $\rho > 1$ such that $\Pi$ admits a $\rho$-approximation algorithm.

▶ **Definition 20.** Let $\Pi$ be a NP-optimization problem. The problem $\Pi$ admits a PTAS if for any $\epsilon > 0$, there exists a polynomial $(1 + \epsilon)$-approximation of $\Pi$.

Parameterized complexity

We refer the reader to [9] for more details on parameterized complexity and kernelization, and we recall here only some basic definitions. A *parameterized problem* is a language $L \subseteq \Sigma^* \times \mathbb{N}$. For an instance $I = (x, k) \in \Sigma^* \times \mathbb{N}$, the integer $k$ is called the *parameter*.

A parameterized problem is *fixed-parameter tractable* (FPT) if there exists an algorithm $A$, a computable function $f$, and a constant $c$ such that given an instance $I = (x, k)$, $A$ (called an FPT algorithm) correctly decides whether $I \in L$ in time bounded by $f(k) \cdot |I|^c$, where $|I|$ denotes the size of $I$. Given a computable function $g$, a *kernelization algorithm* (or simply a *kernel*) for a parameterized problem $L$ of size $g$ is an algorithm $A$ that given any instance $I = (x, k)$ of $L$, runs in polynomial time and returns an equivalent instance $I' = (x', k')$ with $|I'| + k' \le g(k)$. It is well-known that the existence of an FPT algorithm is equivalent to the existence of a kernel (whose size may be exponential), implying that problems admitting a polynomial kernel form a natural subclass of FPT. Among the wide literature on polynomial kernelization, we only recall in the notion of weak composition used to lower bound the size of a kernel.

▶ **Definition 21 (Definition as written in [12]).** Let $L \subseteq \Sigma^*$ be a language, $R$ be a polynomial equivalence relation on $\Sigma^*$, let $Q \subseteq \Sigma^* \times \mathbb{N}$ be a parameterized problem, and let $f: \mathbb{N} \to \mathbb{N}$ be a function. An or-cross-composition of $L$ into $Q$ (with respect to $R$) of cost $f(t)$ is an algorithm that, given $t$ instances $x_i \in \Sigma^*$ of $L$ belonging to the same equivalence class of $R$, takes time polynomial in $\sum_{i \in [t]} |x_i|$ and outputs an instance $(y, k) \in \Sigma^* \times \mathbb{N}$ such that:

1. the parameter $k$ is bounded by $O(f(t) \max_i |x_i|^c)$, where $c$ is some constant independent of $t$, and

2. $(y, k) \in Q$ if and only if there is an $i \in [t]$ such that $x_i \in L$.

▶ **Theorem 22 ([4]).** Let $L \subseteq \Sigma^*$ be a language, let $Q \subseteq \Sigma^* \times \mathbb{N}$ be a parameterized problem, and let $d, \epsilon$ be positive reals. If $L$ is NP-hard under Karp reductions, has an or-cross-composition into $Q$ with cost $f(t) = t^{1/d+o(1)}$, where $t$ denotes the number of instances,
and $Q$ has a polynomial (generalized) kernelization with size bound $O(k^{d-\epsilon})$, then $NP \subseteq_{\text{coNP}} \text{Poly}$.

## B Problems

### Problem 1. (FVS)

**Input:** A directed graph $D = (V, A)$.

**Output:** A set of vertices $X \subseteq V$ such that $D[V \setminus X]$ is acyclic.

**Optimisation:** Minimise $|X|$.

The problem is called FVST if the input is a tournament.

### Problem 2. (d-SET PACKING)

**Input:** An integer $d \ge 3$ and a $d$-uniform hypergraph $G = (V, H)$.

**Output:** A subset of hyperedges $X = \{X_i, i \in [k] \text{ with } X_i \in H\}$ such that for every $i \neq j$, $X_i \cap X_j = \emptyset$.

**Optimisation:** Maximise $k$.

### Problem 3. (PERFECT $d$-SET PACKING)

**Input:** An integer $d \ge 3$ and a $d$-uniform hypergraph $G = (V, H)$.

**Question:** Is there a subset of hyperedges $X = \{X_i, i \in [k] \text{ with } X_i \in H\}$ such that for every $i \neq j$, $X_i \cap X_j = \emptyset$ and $\bigcup_{i \in [k]} X_i = V$?

### Problem 4. (H-PACKING)

**Input:** A graph $G = (V, E)$ and a subgraph $H$.

**Output:** A collection of subgraphs $X = \{H_i, i \in [k]\}$ such that for every $i$, $H_i$ is isomorphic to $H$ and for every $j \neq i$, $V(H_i) \cap V(H_j) = \emptyset$.

**Optimisation:** Maximise $k$.

### Problem 5. (PERFECT $H$-PACKING)

**Input:** A graph $G = (V, E)$ and a subgraph $H$.

**Question:** Is there a collection of subgraphs $X = \{H_i, i \in [k]\}$ such that for every $i$, $H_i$ is isomorphic to $H$, for every $j \neq i$, $V(H_i) \cap V(H_j) = \emptyset$ and $\bigcup_{i \in [k]} H_i = V$?

## C Polynomial detection of sparse tournaments

**Lemma 23.** In polynomial time, we can decide if a tournament is sparse or not, and if so, to give a linear representation whose FAS is a matching

**Proof.** Indeed if a tournament $\mathcal{T}$ is sparse we can detect the first vertex (or vertices) of a linear representation $\sigma(\mathcal{T})$ of $\mathcal{T}$ where $\overleftarrow{A}(\mathcal{T})$ is a matching. If $\mathcal{T}$ has a vertex $x$ of indegree 0 then $x$ must be the first or the second vertex of $\sigma(\mathcal{T})$, and we can always suppose that $x$ is the first vertex of $\sigma(\mathcal{T})$. Otherwise, we look at $Z$ the set of vertices of $\mathcal{T}$ with indegree 1. As $\mathcal{T}$ is a tournament we have $|Z| \le 3$ and if $Z = \emptyset$ then $\mathcal{T}$ is not a sparse tournament. If $|Z| = 1$, then the only element of $Z$ must be the first vertex of $\sigma(\mathcal{T})$. If $|Z| = 2$ with $Z = \{x, y\}$ such that $xy$ is an arc of $\mathcal{T}$, then $x$ must be the first element of $\sigma(\mathcal{T})$ and $y$ its second element. Finally, if $|Z| = 3$ with $Z = \{x, y, z\}$ then $xyz$ must be a triangle of $\mathcal{T}$ and must be placed at the beginning of $\sigma(\mathcal{T})$. So repeating inductively these arguments we obtain in polynomial time in $|\mathcal{T}|$ either $\sigma(\mathcal{T})$ such that $\overleftarrow{A}(\mathcal{T})$ is a matching or a certificate that $\mathcal{T}$ is not sparse. $\blacksquare$