20(0, 12.6)  20(-0.25, 13)

# Polynomial kernel for immersion hitting in tournaments††thanks: This work is
a part of projects that have received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme, grant agreements No. 714704 (Ł. Bożyk) and No. 677651 (Mi.
Pilipczuk).

Łukasz Bożyk  Institute of Informatics, University of Warsaw, Poland,
<EMAIL_ADDRESS> Michał Pilipczuk  Institute of Informatics, University of
Warsaw, Poland<EMAIL_ADDRESS>
###### Abstract

For a fixed simple digraph $H$ without isolated vertices, we consider the
problem of deleting arcs from a given tournament to get a digraph which does
not contain $H$ as an immersion. We prove that for every $H$, this problem
admits a polynomial kernel when parameterized by the number of deleted arcs.
The degree of the bound on the kernel size depends on $H$.

##  1 Introduction

Kernelization is an algorithmic framework for describing preprocessing
procedures that given an instance of a hard problem, identify and reduce
easily resolvable parts. The usual formalization of the concept is based on
the paradigm of parameterized complexity. A kernelization procedure, or a
kernel for short, for a parameterized decision problem $L$ is a polynomial-
time algorithm that given an instance $(I,k)$ of $L$, where $k$ is the
parameter, outputs an equivalent instance $(I^{\prime},k^{\prime})$ such that
both $|I^{\prime}|$ and $k^{\prime}$ are bounded by a computable function of
$k$. If this function is a polynomial in $k$, we say that the kernel is
polynomial. The search for (polynomial) kernels is an established research
area within the field of parameterized algorithms. We refer to the textbook of
Fomin et al. [14] for a broader discussion of classic results and techniques.

A particularly fruitful line of research within kernelization concerns the
methodology of protrusions and protrusion replacement. The idea is to find a
large protrusion: a piece of graph that is simple — for instance, has bounded
treewidth — and communicates with the rest of the graph only through a small
interface. If found, a protrusion can be fully understood — for instance,
using dynamic programming on its tree decomposition — and replaced with a
smaller one with the same functionality. So if one proves that, provided the
given instance is large, a large protrusion can be efficiently found and
replaced with a strictly smaller one, then applying this strategy exhaustively
eventually arrives at a kernel. Protrusion-based techniques were pioneered by
Bodlaender et al. [5], but by now have become a part of the standard toolbox
of kernelization. We refer the interested reader to [14, Part 2] for more
information.

A particularly important achievement in the development of protrusion-based
kernelization procedures is the result of Fomin et al. [13], who gave a
polynomial kernel for the Planar $\mathcal{F}$-Deletion problem, defined as
follows. Let $\mathcal{F}$ be a fixed family of graphs containing at least one
planar graph. Then in the problem we are given a graph $G$ and an integer $k$
(considered to be the parameter), and the question is whether one can hit all
minor models of graphs from $\mathcal{F}$ in $G$ using a hitting set
consisting of at most $k$ vertices. Fomin et al. gave a polynomial kernel for
this problem for every fixed family $\mathcal{F}$ as above. The degree of the
polynomial bound on the kernel size depends on $\mathcal{F}$ and it is known
that under certain complexity-theoretical assumptions, this is unavoidable
[17]. The assumption that $\mathcal{F}$ contains a planar graph is crucial in
the approach: under this assumption, graphs not containing any graph from
$\mathcal{F}$ as a minor have treewidth bounded by a constant, which unlocks a
multitude of tools related to tree decomposition using which one can
understand the structure of the instance.

The concept of a protrusion, as described above, is quite capacious and can be
applied in different settings as well. For instance, Giannopolou et al. [20]
considered the $\mathcal{F}$-Immersion Deletion problem, where for a given
graph $G$ and parameter $k$, one wishes to hit all immersion models of graphs
from $\mathcal{F}$ using a hitting set of edges of size at most $k$. (Recall
that an immersion model of a graph $H$ in a graph $G$ consists of mapping the
vertices of $H$ to distinct vertices of $G$ and edges of $H$ to pairwise edge-
disjoint paths in $G$ so that the image of an edge $uv$ connects the image of
$u$ with the image of $v$.) By loosely following the approach of [13],
Giannopolou et al. [20] gave a linear kernel for $\mathcal{F}$-Immersion
Deletion for every family $\mathcal{F}$ that contains a subcubic planar graph.
Here, the main idea was to adjust the notions of protrusions to the graph
parameter tree-cutwidth and corresponding tree-cut decompositions, which play
the same role for immersions as treewidth and tree decompositions play for
minors.

Motivated by this, it is interesting to consider other settings where the
protrusion methodology could be applied. A particularly tempting area is that
of directed graphs, where natural analogues of problems considered in
undirected graphs can be easily stated. Unfortunately, the structural theory
of directed graphs is much less understood than that of undirected graphs, and
many problems become inherently harder; see e.g. [18, 19, 22]. In particular,
there is even a scarcity of fixed-parameter tractability results, not to
mention kernelization results.

However, there is a particular class of directed graphs where a sound
structural theory has been developed: tournaments. (Here, recall that a
tournament is a directed graph where every pair of vertices is connected by
exactly one arc). This theory111In this line of work, most results concern the
class of semi-complete digraphs, which differ from tournaments by allowing
that a pair of vertices can be also connected by two oppositely-oriented arcs.
In this article we focus on the setting of tournaments for simplicity. was
pioneered by Chudnovsky, Ovetsky Fradkin, Kim, and Seymour [9, 10, 28, 29,
23], while structural and algorithmic aspects connected to parameterized
complexity were investigated by Fomin and Pilipczuk [15]. See the introductory
section of [15] for an overview.

In particular, as proved in the aforementioned works, there are two main width
notions for tournaments: cutwidth and pathwidth. The first one is tightly
connected to (directed) immersions as follows: if a tournament $T$ excludes a
digraph $H$ as an immersion, then the cutwidth of $T$ is bounded by a constant
depending only on $H$. Pathwidth is connected to topological minors and strong
minors in the same sense. These structural results were used for the design of
parameterized algorithms for containment problems in tournaments in [9, 28,
15]. Later, they were used by Raymond [30] and by Bożyk and Pilipczuk [8] to
establish Erdős-Pósa properties for immersions and topological minors in
tournaments.

The goal of this work is to explore the applicability of the structural theory
of tournaments for kernelization, with a particular focus of developing a
sound protrusion-based methodology.

### Our contribution.

For a simple directed graph $H$ without isolated vertices we define the
following parameterized problem:

$H$-hitting Immersions in Tournaments Input: A tournament $T$ and a positive
integer $k$. Parameter: $k$ Output: Is there a set $F\subseteq A(T)$, such
that $|F|\leqslant k$ and $T-F$ is $H$-immersion-free?

That this problem is fixed-parameter tractable is proved in [15]. Our main
result states that for every fixed $H$, $H$-hitting Immersions in Tournaments
admits a polynomial kernel, of degree dependent on $H$. Formally, we prove the
following theorem.

######  Theorem 1.

For every simple digraph $H$ without isolated vertices there exists a constant
$c$ and an algorithm that given an instance $(T,k)$ of $H$-hitting Immersions
in Tournaments, runs in polynomial time and returns an equivalent instance
$(T^{\prime},k)$ with $|T^{\prime}|\leqslant c\cdot k^{c}$.

We remark that when $H$ is the directed triangle, $H$-hitting Immersions in
Tournaments is equivalent to the Feedback Arc Set in Tournaments (FAST)
problem. There is a sizeable literature on the parameterized complexity of
FAST, see e.g. [1, 12, 15, 21], mostly due to the fact that it admits a
subexponential parameterized algorithm with running time
$2^{\mathcal{O}(\sqrt{k})}\cdot n^{\mathcal{O}(1)}$. Kernelization procedures
for FAST were investigated by Bessy et al. in [4], while kernelization of the
dual problems of packing arc-disjoint triangles and packing arc-disjoint
cycles in tournaments were recently studied by Bessy et al. in [3].

On a very high conceptual level, the proof of theorem 1 follows the classic
blueprint of protrusion-based kernelization, like in e.g. [13, 20]. That is,
if $(T,k)$ is a given instance of $H$-hitting Immersions in Tournaments, we
perform the following steps.

  * •

We may assume that the cutwidth of $T$ is bounded polynomially in $k$, for
otherwise in $T$ one can find $k+1$ arc-disjoint immersion models of $H$;
these witness a negative answer to the instance.

  * •

Assuming that $T$ is large — of size superpolynomial in $k$ — but has cutwidth
bounded polynomially in $k$, we may find in $T$ a large protrusion. Here, a
protrusion is an interval $I$ in the vertex ordering $\sigma$ witnessing small
cutwidth such that $\sigma$ restricted to $I$ witnesses that $T[I]$ has
constant cutwidth, and there is only a constant number of $\sigma$-backward
arcs with one endpoint in $I$ and the other outside of $I$. These are
instantiations of the two desired properties of a protrusion: it has to have
bounded width and communicate with the rest of the graph through a boundary of
bounded size.

  * •

We can replace the obtained protrusion with a strictly smaller one of the same
“type”, thus obtaining a strictly smaller equivalent instance. Applying this
strategy exhaustively eventually yields a kernel of polynomial size.

Compared to the previous works, the main difficulty is to tame the interaction
between a protrusion and the remainder of the instance. Namely, this
interaction is not restricted to a set of vertices or arcs of constant size:
as we work with tournaments, every vertex of a protrusion will necessarily
have an arc connecting it to every vertex outside of the protrusion. The idea
is that all but a constant number of those arcs will be forward arcs in the
fixed vertex ordering $\sigma$ with bounded cutwidth. We call those well-
behaved forward arcs generic, while the remaining constantly many backward
arcs are singular. Understanding the interaction between a protrusion and the
rest of the tournament as being governed by few singular arcs and a large
number of well-behaved generic arcs is the crux of our approach.

In particular, while looking for a large replaceable protrusion, we have to be
extremely careful when arguing about how such a protrusion may interact with
optimum solutions. Here, a key step is to find several protrusions that appear
consecutively in $\sigma$ (recall that our protrusions are intervals in
$\sigma$), have the same type (in the sense of admitting partial immersions of
$H$), and such that their union is a protrusion of again the same type. This
step is done using Simon Factorization, a tool commonly used in the theory of
automata and formal languages. Simon Factorization was recently used a few
times in structural graph theory [7, 25, 26], but we are not aware of any
previous application in the context of kernelization.

The application of Simon Factorization is also the only step in the reasoning
that causes the degree of the polynomial bounding the size of our kernel to
depend on $H$. It is an interesting open question whether this can be
improved, or in other words, whether there is a kernel of size at most $c\cdot
k^{d}$, where $c$ may depend on $H$ but $d$ does not. Judging by the results
on hitting immersions in undirected graphs [20], we expect that this might be
the case.

##  2 Preliminaries

We use the standard terminology and notation for describing immersions in
tournaments and for cutwidth of digraphs and of tournaments. This terminology
and notation is borrowed mostly, and often in a verbatim form, from the work
of Bożyk and Pilipczuk [8].

For a positive integer $n$, we denote $[n]\coloneqq\\{1,\ldots,n\\}$ and
$[-n]=\\{-1,\ldots,-n\\}$.

We use standard graph terminology and notation. All graphs considered in this
paper are finite, simple (i.e. without self-loops or multiple arcs with same
head and tail), and directed (i.e. are digraphs). For a digraph $D$, by $V(D)$
and $A(D)$ we denote the vertex set and the arc set of $D$, respectively. We
denote

$|D|\coloneqq|V(D)|\qquad\textrm{and}\qquad\|D\|\coloneqq|A(D)|.$

For $X\subseteq V(D)$, the subgraph induced by $X$, denoted $D[X]$, comprises
of the vertices of $X$ and all the arcs of $D$ with both endpoints in $X$. By
$D-X$ we denote the digraph $D[V(D)\setminus X]$. Further, if $F$ is a subset
of arcs of $D$, then by $D-F$ we denote the digraph obtained from $D$ by
removing all the arcs of $F$. For $X,Y\subseteq V(D)$ we denote by
$\overrightarrow{A}(X,Y)$ the set of all arcs $(u,v)\in A(D)$ such that $u\in
X$ and $v\in Y$ and moreover
$A(X,Y)\coloneqq\overrightarrow{A}(X,Y)\cup\overrightarrow{A}(Y,X)$. For an
arc $a=(u,v)\in A(D)$ we define $\operatorname{\mathsf{tail}}(a)\coloneqq u$
and $\operatorname{\mathsf{head}}(a)\coloneqq v$. For a directed (not
necessarily simple) path $P$ we denote by $\operatorname{\mathsf{first}}(P)$
and $\operatorname{\mathsf{last}}(P)$ the first and the last arcs on path $P$,
respectively.

### Tournaments.

A simple digraph $T=(V,A)$ is called a _tournament_ if for every pair of
distinct vertices $u,v\in V$, either $(u,v)\in A$, or $(v,u)\in A$ (but not
both). Alternatively, one can represent the tournament $T$ by providing a pair
$(\sigma,\overleftarrow{A}_{\sigma}(T))$, where $\sigma\colon V\to[|V|]$ is an
ordering of the set $V$ and $\overleftarrow{A}_{\sigma}(T)$ is the set of
_$\sigma$ -backward arcs_, that is,

$\overleftarrow{A}_{\sigma}(T)\coloneqq\\{\,(u,v)\in A\ \mid\
\sigma(u)>\sigma(v)\,\\}.$

All the remaining arcs are called _$\sigma$ -forward_. If the choice of
ordering $\sigma$ is clear from the context, we will call the arcs simply
_backward_ or _forward_. For $\alpha,\beta\in\\{0,1,\ldots,|V|\\}$,
$\alpha\leqslant\beta$, we define

$\sigma(\alpha,\beta]\coloneqq\\{v\in V\mid\alpha<\sigma(v)\leqslant\beta\\}.$

Sets $\sigma(\alpha,\beta]$ as defined above will be called _$\sigma$
-intervals_.

### Cutwidth.

Let $T=(V,A)$ be a tournament and $\sigma$ be an ordering of $V$. The set

$\operatorname{\mathsf{cut}}_{\sigma}[\alpha]=\\{(u,v)\in
A\mid\sigma(u)>\alpha\geqslant\sigma(v)\\}\subseteq\overleftarrow{A}_{\sigma}(T)$

is called the _$\alpha$ -cut_ of $\sigma$. The width of the ordering $\sigma$
is equal to
$\max_{0\leqslant\alpha\leqslant|V|}|\operatorname{\mathsf{cut}}[\alpha]|$,
and the _cutwidth_ of $T$, denoted $\operatorname{\mathbf{ctw}}(T)$, is the
minimum width among all orderings of $V$.

It is perhaps a bit surprising that in tournaments, there is a very simple
algorithm to compute an ordering of optimum width: just sort the vertices by
outdegrees.

######  Lemma 2 (see [2, 27]).

Let $T$ be a tournament and $\sigma$ be an ordering of $T$ satisfying the
following for every pair of vertices $u$ and $v$: if $u$ appears before $v$ in
$\sigma$, then the outdegre of $u$ is not smaller than the outdegree of $v$.
Then the width of $\sigma$ is equal to $\operatorname{\mathbf{ctw}}(T)$.

If $I=\sigma(\alpha,\beta]$, then we denote

$\partial^{+}(I)\coloneqq\overrightarrow{A}(I,\sigma(0,\alpha])\quad\text{and}\quad\partial^{-}(I)\coloneqq\overrightarrow{A}(\sigma(\beta,|V|],I).$

Note that
$\partial^{+}(I)\subseteq\operatorname{\mathsf{cut}}_{\sigma}[\alpha]$ and
$\partial^{-}(I)\subseteq\operatorname{\mathsf{cut}}_{\sigma}[\beta]$ and
therefore $|\partial^{+}(I)|\leqslant c$ and $|\partial^{-}(I)|\leqslant c$,
where $c$ is the width of $\sigma$. These inclusions may be proper, as the
arcs from the set
$\widehat{\partial}(I)\coloneqq\overrightarrow{A}(\sigma(\beta,|V|],\sigma(0,\alpha])$
contribute to the cuts but are not incident with $I$. We define
$\partial(I)\coloneqq\partial^{+}(I)\cup\partial^{-}(I)$ and call the elements
of $\partial(I)$ _$I$ -singular_ (or simply _singular_) arcs. Moreover, we
define

$\Gamma^{+}(I)\coloneqq\overrightarrow{A}(I,\sigma(\beta,|V|]),\qquad\Gamma^{-}(I)\coloneqq\overrightarrow{A}(\sigma(0,\alpha],I),\quad\textrm{and}\quad\Gamma(I)=\Gamma^{+}(I)\cup\Gamma^{-}(I),$

and call the elements of $\Gamma(I)$ _$I$ -generic_ (or simply _generic_)
arcs.

If $I^{\prime}=V-I$ where $I=\sigma(\alpha,\beta]$, then we call the set
$I^{\prime}$ a _co-interval_ and define _$I^{\prime}$ -singular_ and
_$I^{\prime}$ -generic_ arcs as follows

$\partial^{-}(I^{\prime})\coloneqq\partial^{+}(I),\quad\partial^{+}(I^{\prime})\coloneqq\partial^{-}(I),\quad\partial(I^{\prime})\coloneqq\partial^{+}(I^{\prime})\cup\partial^{-}(I^{\prime})=\partial(I),$
$\Gamma^{-}(I^{\prime})\coloneqq\Gamma^{+}(I),\quad\Gamma^{+}(I^{\prime})\coloneqq\Gamma^{-}(I),\quad\Gamma(I^{\prime})\coloneqq\Gamma^{-}(I^{\prime})\cup\Gamma^{+}(I^{\prime})=\Gamma(I).$

### Immersions.

A digraph $\widehat{H}$ is an _immersion model_ (or briefly a _copy_) of a
digraph $H$ if there exists a mapping $\phi$, called an immersion embedding,
such that:

  * •

vertices of $H$ are mapped to pairwise different vertices of $\widehat{H}$;

  * •

each arc $(u,v)\in A(H)$ is mapped to a directed path in $\widehat{H}$
starting at $\phi(u)$ and ending at $\phi(v)$; and

  * •

each arc of $\widehat{H}$ belongs to exactly one of the paths
$\\{\phi(a)\colon a\in A(H)\\}$.

If it does not lead to misunderstanding, we will sometimes slightly abuse the
above notation by identifying $\phi$ and $\widehat{H}$ and calling $\phi$ the
immersion model of $H$.

Let $H$ be a digraph. We say that a digraph $G$ _contains $H$ as an immersion_
(or $H$ can be _immersed_ in $G$) if $G$ has a subgraph that is an immersion
model of $H$. Digraph $G$ is called _$H$ -immersion-free_ (or _$H$ -free_ for
brevity) if it does not contain $H$ as an immersion.

We will use the following result of Fomin and Pilipczuk [15].

######  Theorem 3 (Theorem 7.3 of [15]).

Let $T$ be a tournament which does not contain a digraph $H$ as an immersion.
Then $\operatorname{\mathbf{ctw}}(T)\in\mathcal{O}((|H|+\|H\|)^{2})$.

######  Corollary 4.

For every digraph $H$ there exists a constant $c_{H}$ such that for every
$H$-free tournament $T$, we have $\operatorname{\mathbf{ctw}}(T)\leqslant
c_{H}$.

Throughout this paper we fix a simple digraph $H$ without isolated vertices
and an integer $k\in\mathbb{N}$. For a tournament $T$, a set $F\subseteq A(T)$
is called a _solution_ if $T-F$ is $H$-free. Moreover, $F$ is an _optimal
solution_ if it is a solution of the smallest possible size. So $(T,k)$ is a
YES-instance of $H$-hitting Immersions in Tournaments if and only if in $T$
there exists an optimal solution of size at most $k$.

### Monoids and Simon factorization.

Simon factorization was originally developed by Simon in [31] and the
currently best bounds are due to Kufleitner [24]. See also the work of
Bojańczyk [6] for a nice exposition; we mostly follow the notation from that
source.

Let $S$ be a finite monoid (i.e., a finite set equipped with an associative
binary operation $\cdot$ and a neutral element $1$). An element $e\in S$ is
called _idempotent_ if $e\cdot e=e$. For a finite alphabet $A$, by $A^{\star}$
we denote the set of all finite words over $A$, and a morphism $\alpha\colon
A^{\star}\to S$ is a function satisfying $\alpha(\varepsilon)=1$
($\varepsilon$ being the empty word) and
$\alpha(w_{1}w_{2})=\alpha(w_{1})\cdot\alpha(w_{2})$ for every $w_{1},w_{2}\in
A^{\star}$. Note that a morphism is uniquely defined by the images of single
symbols from $A$. The following lemma is a direct consequence of Simon
Factorization, see appendix A for a derivation.

######  Lemma 5.

Let $S$ be a finite monoid, $A$ be a finite alphabet, and $\alpha\colon
A^{\star}\to S$ be a morphism. Suppose $w\in A^{\star}$ is a word of length at
least $\ell^{3|S|}$. Then there exists a subword $w^{\prime}$ of $w$ and an
idempotent $e\in S$ such that $w^{\prime}=w_{1}w_{2}\ldots w_{\ell}$, where
$w_{i}\in A^{\star}$ are nonempty subwords of $w$ and

$\alpha(w_{1})=\alpha(w_{2})=\ldots=\alpha(w_{\ell})=e.$

Note that in the setting of lemma 5, given a word $w\in A^{\star}$ of length
$n\geqslant\ell^{3|S|}$, one can easily find $w^{\prime}$ and a suitable
decomposition $w^{\prime}=w_{1}w_{2}\ldots w_{\ell}$ in time
$\mathcal{O}(|S|\cdot n^{3})$ assuming unit cost of operations in $S$. Indeed,
one can guess $e$ (by trying at most $|S|$ possibilities) and the first
position of $w^{\prime}$ within $w$ (by trying $n$ possibilities), and then
for every subword $w^{\prime\prime}$ starting at this position compute the
longest possible decomposition of the form $w^{\prime\prime}=w_{1}w_{2}\ldots
w_{\ell^{\prime}}$ such that
$\alpha(w_{1})=\ldots=\alpha(w_{\ell^{\prime}})=e$, if existent. The latter
can be done by a standard left-to-right dynamic programming in time
$\mathcal{O}(n^{2})$.

##  3 Partial immersions

Our goal in this section is to extend the notion of an immersion to partial
immersions. These will be used to understand possible behaviors of immersion
models in a tournament $T$ with respect to different intervals in an ordering
of the vertex set of $T$. Let then $T=(V,A)$ be a tournament and let $\sigma$
be an ordering of $V$. For now, fix a $\sigma$-interval
$I\coloneqq\sigma(\alpha,\beta]$.

######  Definition 1.

A _scattered path_ in $I$ of size $q\geqslant 0$ is a sequence
$\widetilde{P}=(P_{i})_{i=1}^{q}$ satisfying the following properties:

  * •

for each $i\in[q]$, $P_{i}$ is a directed (simple) path of length at least $1$
consisting of arcs that belong to $A(T[I])\cup\partial(I)\cup\Gamma(I)$;

  * •

paths $P_{i}$ for $i\in[q]$ are pairwise arc-disjoint;

  * •

for every $i\in[q]$, $i\neq 1$, we have
$\operatorname{\mathsf{first}}(P_{i})\in\Gamma^{-}(I)\cup\partial^{-}(I)$;

  * •

for every $i\in[q]$, $i\neq q$, we have
$\operatorname{\mathsf{last}}(P_{i})\in\Gamma^{+}(I)\cup\partial^{+}(I)$.

Each term in the sequence $(P_{i})_{i=1}^{q}$ will be called a _piece_ of
$\widetilde{P}$. The set of arcs of all pieces of $\widetilde{P}$ is denoted
$A(\widetilde{P})$. If $\operatorname{\mathsf{first}}(P_{i})\in\Gamma^{-}(I)$
and $\operatorname{\mathsf{last}}(P_{i})\in\Gamma^{+}$, then the piece $P_{i}$
is called _generic_.

Note that $\operatorname{\mathsf{first}}(P_{1})$ is allowed to be an arc in
the set $A(T[I])\cup\Gamma^{+}(I)\cup\partial^{+}(I)$. If it is such, we call
the vertex
$\operatorname{\mathsf{tail}}(\operatorname{\mathsf{first}}(P_{1}))\in I$ the
_beginning_ of $\widetilde{P}$ and denote it by
$\operatorname{\mathsf{start}}(\widetilde{P})$. Similarly, if
$\operatorname{\mathsf{last}}(P_{q})\in
A(T[I])\cup\Gamma^{-}(I)\cup\partial^{-}(I)$, then we call the vertex
$\operatorname{\mathsf{head}}(\operatorname{\mathsf{last}}(P_{q}))$ the _end_
of $\widetilde{P}$ and denote it by
$\operatorname{\mathsf{end}}(\widetilde{P})$. Note that the empty sequence is
a scattered path of size $0$. Also, a scattered path with only one piece,
whose both beginning and end exist, is just a path in $T[I]$. By
$\mathcal{P}_{I}$ we denote the family of all scattered paths in $I$.

We say that a scattered path $\widetilde{P}=(P_{i})_{i=1}^{q}$ in $I$ can be
_shortened_ to a scattered path $\widetilde{P}^{\prime}$ (or that
$\widetilde{P}^{\prime}$ is a _shortening_ of $\widetilde{P}$) if:

  * •

$\operatorname{\mathsf{start}}(\widetilde{P})=\operatorname{\mathsf{start}}(\widetilde{P}^{\prime})$
and
$\operatorname{\mathsf{end}}(\widetilde{P})=\operatorname{\mathsf{end}}(\widetilde{P}^{\prime})$
(meaning either equal or simultaneously undefined);

  * •

for each piece $P^{\prime}_{s}$ of $\widetilde{P}^{\prime}$ there exist
indices $i_{s}^{-}\leqslant i_{s}^{+}$ such that
$\operatorname{\mathsf{tail}}(\operatorname{\mathsf{first}}(P^{\prime}_{s}))=\operatorname{\mathsf{tail}}(\operatorname{\mathsf{first}}(P_{i_{s}^{-}}))$
and
$\operatorname{\mathsf{head}}(\operatorname{\mathsf{last}}(P^{\prime}_{s}))=\operatorname{\mathsf{head}}(\operatorname{\mathsf{last}}(P_{i_{s}^{+}}))$;
and

  * •

whenever $s<s^{\prime}$, we have $i_{s}^{+}<i_{s^{\prime}}^{-}$ and
$P^{\prime}_{s}$ appears before $P^{\prime}_{s^{\prime}}$ in
$\widetilde{P}^{\prime}$.

Intuitively, shortening of the path means removing some pieces and replacing
several contiguous subsequences of the pieces with single pieces, keeping the
tail of the beginning and the head of the end of the replaced subsequence.
Note that in particular, some pieces of $\widetilde{P}$ can be simply omitted
in $\widetilde{P}^{\prime}$ (other than the initial and the terminal one).

######  Definition 2.

A _partial immersion embedding_ of $H$ in $I$ (or shortly, a _partial
immersion_ in $I$) is a mapping $\phi\colon A(H)\to\mathcal{P}_{I}$ such that

  * •

all scattered paths $\phi(a)$ for $a\in A(H)$ are pairwise arc-disjoint;

  * •

if $\operatorname{\mathsf{tail}}(a)=\operatorname{\mathsf{tail}}(a^{\prime})$
then $\operatorname{\mathsf{start}}(\phi(a))$ and
$\operatorname{\mathsf{start}}(\phi(a^{\prime}))$ are either equal, or
simultaneously undefined;

  * •

if $\operatorname{\mathsf{start}}(\phi(a))$ and
$\operatorname{\mathsf{start}}(\phi(a^{\prime}))$ are defined and equal, then
$\operatorname{\mathsf{tail}}(a)=\operatorname{\mathsf{tail}}(a^{\prime})$;

  * •

if $\operatorname{\mathsf{head}}(a)=\operatorname{\mathsf{head}}(a^{\prime})$
then $\operatorname{\mathsf{end}}(\phi(a))$ and
$\operatorname{\mathsf{end}}(\phi(a^{\prime}))$ are either equal, or
simultaneously undefined;

  * •

if $\operatorname{\mathsf{end}}(\phi(a))$ and
$\operatorname{\mathsf{end}}(\phi(a^{\prime}))$ are defined and equal, then
$\operatorname{\mathsf{head}}(a)=\operatorname{\mathsf{head}}(a^{\prime})$.

Intuitively, we can think of a partial immersion as of a “trace” which some
immersion model $\widehat{H}$ of $H$ in $T$ “leaves” on the interval $I$. Some
edges of $H$ have images being paths in $\widehat{H}$ non-incident with $I$
(these correspond to empty scattered paths in the partial immersion
embedding). Some images of arcs of $H$ come back and forth to $I$,
intersecting with $I$ along a non-empty scattered path (the ordering of paths
on a single scattered path corresponds to the order of their appearance along
the image of the respective arc of $H$). Finally, some arc images begin or end
within $I$, which corresponds to the case when the beginning or the end of a
scattered path is defined and is a vertex of $I$.

We call a partial immersion $\phi^{\prime}$ in $I$ a _shortening_ of $\phi$ in
$I$ if for every $a\in A(H)$, the scattered path $\phi^{\prime}(a)$ is a
shortening of $\phi(a)$. We call $\phi$ _minimal_ if there is no shortening of
$\phi$ with at least one scattered path of strictly smaller size. Note that
$\phi$ may be minimal even if some piece of some $\phi(a)$ can be replaced by
a different single piece with equal first and last vertices. Shortening which
does not decrease the size of any scattered path will be called _trivial_.

Note that each immersion model $\phi$ of $H$ in $T$ is a partial immersion in
$V(T)$, in which all scattered paths $\phi(a)$, $a\in A(H)$, are paths in $T$
beginning and ending at $\phi(\operatorname{\mathsf{tail}}(a))$ and
$\phi(\operatorname{\mathsf{head}}(a))$, respectively. Moreover, each partial
immersion $\phi$ in $I$ gives rise to a natural partial immersion of $H$ in
$J\subseteq I$ in which all paths $\phi(a)$ where $a\in A(H)$ are “trimmed” to
scattered paths consisting of precisely those arcs which are incident with
$J$.

Formally, let $I$ and $J$ be $\sigma$-intervals such that $J\subseteq I$. If
$P$ is a path in $I$, then define the _trace_ $P|_{J}$ of $P$ on $J$ to be the
scattered path consisting of all arcs of $P$ incident with $J$, arranged in
the order of appearance along $P$. If $\widetilde{P}=(P_{i})_{i=1}^{q}$ is a
scattered path in $I$, then define the _trace $\widetilde{P}|_{J}$_ of
$\widetilde{P}$ on $J$ to be the concatenation of scattered paths
$P_{i}|_{J}$. The _trace_ $\phi|_{J}$ of a partial immersion $\phi$ of $H$ in
$I$ on $J$ is defined by setting $\phi|_{J}(a)=(\phi(a))|_{J}$ for every $a\in
A(H)$.

Consider any $\sigma$-intervals $I_{1}$, $I_{2}$ with the property that there
exist $\alpha,\beta,\gamma\in\\{0,1,\ldots,|V|\\}$ such that
$I_{1}=\sigma(\alpha,\gamma]$ and $I_{2}=\sigma(\gamma,\beta]$. We will call
such a pair of intervals _consecutive_. Equivalently, two disjoint intervals
are consecutive if their union $I=I_{1}\cup I_{2}$ is a $\sigma$-interval as
well. Let $\widetilde{P}_{1}$ be a scattered path in $I_{1}$ and
$\widetilde{P}_{2}$ be a scattered path in $I_{2}$. We say that
$\widetilde{P}_{1}$ and $\widetilde{P}_{2}$ are _compatible_ if

  * •

$A(\widetilde{P}_{1})\cap A(I_{1},I_{2})=A(\widetilde{P}_{2})\cap
A(I_{1},I_{2})$;

  * •

the set of pieces whose arc set is $A(\widetilde{P}_{1})\cup
A(\widetilde{P}_{2})$ can be ordered to form a scattered path $\widetilde{P}$
in $I$ with the property that all pieces of $\widetilde{P_{i}}$ appear in
$\widetilde{P}$ in the same order as they do in $\widetilde{P_{i}}$, for
$i=1,2$.

Every $\widetilde{P}$ described above will be called a _gluing_ of
$\widetilde{P}_{1}$ and $\widetilde{P}_{2}$. Note that a gluing is not
necessarily uniquely defined, which can be seen particularly well when
$A(\widetilde{P}_{1})\cap A(I_{1},I_{2})=A(\widetilde{P}_{2})\cap
A(I_{1},I_{2})=\emptyset$ — in this case the pieces of both paths can be
“shuffled” in any way only keeping the order of pieces originating from the
same path.

######  Observation 6.

If $\widetilde{P}_{1}$ is compatible with $\widetilde{P}_{2}$ and
$\widetilde{P}^{\prime}_{2}$ is a shortening of $\widetilde{P}_{2}$, then
there exists a shortening $\widetilde{P}^{\prime}_{1}$ of $\widetilde{P}_{1}$
such that $\widetilde{P}^{\prime}_{1}$ and $\widetilde{P}^{\prime}_{2}$ are
compatible and every gluing of them is a shortening of some gluing of
$\widetilde{P}_{1}$ and $\widetilde{P}_{2}$.

######  Proof.

To construct $\widetilde{P}^{\prime}_{1}$ from $\widetilde{P}_{1}$ it is
enough to omit the pieces which do not share arcs with
$\widetilde{P}^{\prime}_{2}$. $\square$

We will say that two partial immersions $\phi_{1}$ in $I_{1}$ and $\phi_{2}$
in $I_{2}$ are _compatible_ if there exists a partial immersion $\phi$ in $I$
such that $\phi_{1}=\phi|_{I_{1}}$ and $\phi_{2}=\phi|_{I_{2}}$, or — in other
words — that for every $a\in A(H)$ the scattered path $\phi(a)$ is a gluing of
$\phi_{1}(a)$ and $\phi_{2}(a)$. We will call every such $\phi$ a _gluing_ of
$\phi_{1}$ and $\phi_{2}$. Note that a gluing is not necessarily uniquely
defined. Denote the set of all gluings of $\phi_{1}$ and $\phi_{2}$ by
$\phi_{1}\oplus\phi_{2}$.

######  Observation 7.

If $\phi\in\phi_{1}\oplus\phi_{2}$ and $\phi$ is minimal, then $\phi_{1}$ and
$\phi_{2}$ are minimal.

######  Proof.

Suppose that $\phi_{1}$ is not minimal. Then there exists a shortening
$\phi^{\prime}_{1}$ of $\phi_{1}$ which has a strictly smaller total number of
pieces. For every $a\in A(H)$ the scattered path $\phi^{\prime}_{1}(a)$ is
compatible with some scattered path $\phi^{\prime}_{2}(a)$ obtained by
omitting several pieces in $\phi_{2}(a)$. In particular, the collection of all
such $\phi^{\prime}_{2}(a)$ — call it $\phi^{\prime}_{2}$ — is a partial
immersion compatible with $\phi^{\prime}_{1}$ that is a shortening of
$\phi_{2}$. Any gluing belonging to $\phi^{\prime}_{1}\oplus\phi^{\prime}_{2}$
is a shortening of $\phi$ with a strictly smaller total number of pieces —
contradiction. An analogous reasoning can be applied upon supposing that
$\phi_{2}$ is not minimal. $\square$

The notions of a scattered path, partial immersion and trace can be naturally
extended to co-intervals, by applying all definitions verbatim. If $I$ is a
$\sigma$-interval and $I^{\prime}=V-I$ is the corresponding co-interval, then
partial immersions $\phi_{1}$ in $I$ and $\phi_{2}$ in $I^{\prime}$ are
_compatible_ if there exists an immersion $\phi$ in $T$ such that
$\phi_{1}=\phi|_{I}$ and $\phi_{2}=\phi|_{I^{\prime}}$. Again, every such
$\phi$ is called a _gluing_ of $\phi_{1}$ and $\phi_{2}$.

### Types of intervals.

The key ingredient of our analysis is a constant-size encoding of the set of
possible “behaviors” of partial immersions in intervals.

A $\sigma$-interval $I$ shall be called _$\ell$ -long_ if $|I|\geqslant\ell$.
Further, we shall call $I$ _$c$ -flat_ if $|\partial^{+}(I)|\leqslant c$,
$|\partial^{-}(I)|\leqslant c$, and $\sigma$ restricted to $T[I]$ has width at
most $c$.

Note that if $I=\sigma(\alpha,\beta]$ is $2r$-long, then the intervals
$I^{-}_{r}\coloneqq\sigma(\alpha,\alpha+r]$ and
$I^{+}_{r}\coloneqq\sigma(\beta-r,\beta]$ are disjoint. On the other hand, if
$I$ is $c$-flat, then we can color all backward arcs incident with $I$ with at
most $3c$ colors in such a way that each $\gamma$-cut of $\sigma$ restricted
to those arcs contains arcs of mutually different colors. This can be achieved
e.g. by greedy coloring the $\gamma$-cuts for consecutive
$\gamma=\alpha,\ldots,\beta+1$. Formally, there exists a function
$\xi\colon\overleftarrow{A}_{\sigma}(T)\cap A(I,V)\to[3c]$ such that for every
$\gamma\in[|V|-1]$ and every two distinct arcs
$a_{1},a_{2}\in\operatorname{\mathsf{cut}}_{\sigma}[\gamma]\cap A(I,V)$ we
have $\xi(a_{1})\neq\xi(a_{2})$. In the following fix such a function.

######  Definition 3.

Let $\phi$ be a partial immersion in an interval $I$ that is $2r$-long and
$c$-flat. For each $a\in A(H)$ we define the $(r,c)$-_type_
$\tau^{(r,c)}(\phi(a))$ of the scattered path $\phi(a)=(P_{i})_{i=1}^{q}$ as
the following sequence of length $2q$:

$(f_{-}(\operatorname{\mathsf{first}}(P_{1})),f_{+}(\operatorname{\mathsf{last}}(P_{1})),f_{-}(\operatorname{\mathsf{first}}(P_{2})),f_{+}(\operatorname{\mathsf{last}}(P_{2})),\ldots,f_{-}(\operatorname{\mathsf{first}}(P_{q})),f_{+}(\operatorname{\mathsf{last}}(P_{q}))),$

where the functions $f_{\pm}\colon
A(T[I])\cup\partial(I)\cup\Gamma(I)\to[-3c]\cup[r]\cup\\{\operatorname{\mathsf{X}},\operatorname{\mathsf{H}}\\}$
are defined as follows

$f_{-}(a)=\begin{cases}-\xi(a)&\text{ if }a\in\partial^{-}(I),\\\
\sigma(\operatorname{\mathsf{head}}(a))-\alpha&\text{ if
}a\in\Gamma^{-}(I)\text{ and }\operatorname{\mathsf{head}}(a)\in I^{-}_{r},\\\
\operatorname{\mathsf{X}}&\text{ if }a\in\Gamma^{-}(I)\text{ and
}\operatorname{\mathsf{head}}(a)\notin I^{-}_{r},\\\
\operatorname{\mathsf{H}}&\text{ otherwise;}\end{cases}$
$f_{+}(a)=\begin{cases}-\xi(a)&\text{ if }a\in\partial^{+}(I),\\\
r+\sigma(\operatorname{\mathsf{tail}}(a))-\beta&\text{ if
}a\in\Gamma^{+}(I)\text{ and }\operatorname{\mathsf{tail}}(a)\in I^{+}_{r},\\\
\operatorname{\mathsf{X}}&\text{ if }a\in\Gamma^{+}(I)\text{ and
}\operatorname{\mathsf{tail}}(a)\notin I^{+}_{r},\\\
\operatorname{\mathsf{H}}&\text{ otherwise.}\end{cases}$

Let $S$ be the set of all terms of the sequences
$(\tau^{(r,c)}(\phi(a)))_{a\in A(H)}$, where by term we mean a value with an
assigned position (i.e. equal values in different sequences are considered
different terms). The _$(r,c)$ -type_ of $\phi$ is the collection of types
$\tau^{(r,c)}(\phi)=(\tau^{(r,c)}(\phi(a)))_{a\in A(H)}$ equipped with a pair
of equivalence relations $(R_{-},R_{+})$ on the set $S\cup[3c]$ defined as
follows.

  * •

If a piece $P_{1}$ of $\phi(a_{1})$ and a piece $P_{2}$ of $\phi(a_{2})$
satisfy
$\operatorname{\mathsf{head}}(\operatorname{\mathsf{first}}(P_{1}))=\operatorname{\mathsf{head}}(\operatorname{\mathsf{first}}(P_{2}))$,
then the corresponding terms in $\tau^{(r,c)}(\phi)$ (elements of the set
$\\{\operatorname{\mathsf{X}}\\}\cup[r]$ with assigned positions in respective
sequences) are in relation $R_{-}$.

  * •

If a piece $P$ of $\phi(a)$ is such that
$\operatorname{\mathsf{head}}(\operatorname{\mathsf{first}}(P))$ is the tail
of a singular arc of color $x\in[3c]$, then the corresponding term in
$\tau^{(r,c)}(\phi)$ is in relation $R_{-}$ with $x$.

  * •

Analogously, if
$\operatorname{\mathsf{tail}}(\operatorname{\mathsf{last}}(P_{1}))=\operatorname{\mathsf{tail}}(\operatorname{\mathsf{last}}(P_{2}))$,
then the terms $f_{+}(\operatorname{\mathsf{last}}(P_{1}))$ and
$f_{+}(\operatorname{\mathsf{last}}(P_{2}))$ are in relation $R_{+}$. And
$x\in[3c]$ is in relation with all terms corresponding to tails of ends of
paths which are simultaneously the head of the singular arc of color $x$.

Let us provide some intuition on what kind of information is stored in the
type of $\phi$ defined above. First of all, the entire “singular interface” of
this partial immersion is kept, i.e. in the type we remember precisely the
singular arcs used to enter or exit $I$ when traversing along each scattered
path $\phi(a)$. Moreover, if we enter or exit $I$ with a generic arc, we
remember the precise vertex of entry/exit inside $I$, but only if it is close
enough to the “border” of $I$ (i.e. within the first or last $r$ vertices in
$\sigma$). Otherwise we remember the respective entry/exit as “generic”, which
is marked by the marker $\operatorname{\mathsf{X}}$. Moreover, we keep the
information about whether the scattered path begins or ends inside $I$ — the
marker $\operatorname{\mathsf{H}}$ represents that a vertex of $H$ is mapped
under the partial immersion embedding to a vertex within $I$. Finally if the
extreme (first or last) arcs of some pieces are generic and have the same
first/last vertex in $I$, we remember this fact in the equivalence relations
$R_{\pm}$. We shall need this information to be able to “glue” two partial
immersions without using the same generic gluing arc for different pieces. The
incidence with singular arcs is also stored to avoid a situation when one
attempts a generic gluing along a singular arc. The reason for colors being
stored as negative integers is purely technical — it ensures that
$[r]\cap[-3c]=\emptyset$.

An _$(r,c)$ -type_ is any collection of sequences of even lengths over the set
$[-3c]\cup[r]\cup\\{\operatorname{\mathsf{X}},\operatorname{\mathsf{H}}\\}$
indexed by $A(H)$ and equipped with a pair of equivalence relations
$(R_{-},R_{+})$ on the union of the set of all terms of these sequences and
$[3c]$. An _$I$ -admissible $(r,c)$-type_ is every type $\tau$ such that there
exists a partial immersion $\phi$ in $I$ such that $\tau=\tau^{(r,c)}(\phi)$.
The _size_ of a type is the sum of lengths of its sequences (i.e. it does not
depend on the equivalence relations).

Let $\gamma_{r}$ be a function mapping each element from the set $[r]$ onto
the single marker $\operatorname{\mathsf{X}}$, and identity otherwise.
Intuitively, the function $\gamma_{r}$ keeps only the information about
generic nature of the end of a piece, and “forgets” about the closeness of
this vertex to the boundary. We say that an $(r,c)$-type $\tau^{\prime}$ is a
_shortening_ of an $(r,c)$-type $\tau$ if for every $a\in A(H)$ the sequence
$\gamma(\tau^{\prime}_{a})$ is a subsequence of $\gamma(\tau_{a})$ and the two
sequences have the same first and last terms.

The following observation is a direct consequence of the definition of
shortening of a partial immersion.

######  Observation 8.

If a partial immersion $\phi^{\prime}$ of $(r,c)$-type $\tau^{\prime}$ is a
shortening of a partial immersion $\phi$ of $(r,c)$-type $\tau$, then
$\tau^{\prime}$ is a shortening of $\tau$.

######  Definition 4.

An $I$-admissible $(r,c)$-type $\tau$ is called _minimal_ (in $I$) if there is
no $I$-admissible type $\tau^{\prime}$ of strictly smaller size that would be
a shortening of $\tau$.

######  Observation 9.

Let $\phi$ be a partial immersion in $I$ of $(r,c)$-type $\tau$. Then $\phi$
is minimal if and only if $\tau$ is minimal in $I$.

######  Proof.

If $\phi$ is not minimal, then for any nontrivial shortening $\phi^{\prime}$
of $\phi$, $\tau^{(r,c)}(\phi^{\prime})$ is a shortening of $\tau$ of strictly
smaller size. Conversely, if $\tau$ is not minimal, then there exists an
$I$-admissible type $\tau^{\prime}$ of strictly smaller size. Every partial
immersion $\phi^{\prime}$ of type $\tau^{\prime}$ is a nontrivial shortening
of $\phi$. $\square$

We now observe that in a minimal partial immersion on an interval $I$, all
scattered paths will be relatively small, that is, will visit $I$ only a
bounded number of times.

######  Lemma 10.

Suppose that $F\subseteq A(T)$ has the property that $|F|\leqslant f$, $I$ is
$4\|H\|(c+f+1)$-long and $c$-flat, and a partial immersion $\phi$ in $I$ is
minimal and disjoint with $F$. Then for every $a\in A(H)$ the scattered path
$\phi(a)$ has size at most $2c+3$.

######  Proof.

We will show that every partial immersion $\phi$ disjoint with $F$ can be
shortened to a partial immersion $\phi^{\prime}$ disjoint with $F$ in which
every path $\phi(a)$ has at most one generic piece. This will yield the
desired result as every nongeneric piece of $\phi(a)$ which is neither the
initial, nor the terminal one, contains at least one arc from the set
$\partial(I)$, which is of size not exceeding $2c$ (as $I$ is $c$-flat).

Take an arbitrary $\phi$ disjoint with $F$. For every $a\in A(H)$, let
$\phi(a)=(P^{a}_{i})_{i=1}^{q_{a}}$. Let $i_{a}^{-}$ be the smallest index $i$
such that $\operatorname{\mathsf{first}}(P^{a}_{i})\in\Gamma^{-}(I)$ (if there
is no such index, we put $i_{a}^{-}=\infty$). Similarly, let $i_{a}^{+}$ be
the greatest index $i$ such that
$\operatorname{\mathsf{last}}(P^{a}_{i})\in\Gamma^{+}(I)$ (or
$i_{a}^{+}=-\infty$ if no such index exists). Note that if $i<i_{a}^{-}$ or
$i>i_{a}^{+}$, then $P^{a}_{i}$ is not generic, so

$\left|\bigcup_{a\in
A(H)}\bigcup_{i\notin[i_{a}^{-},i_{a}^{+}]}\\{P^{a}_{i}\\}\right|\leqslant\|H\|\cdot(2c+2).$

The set on the left-hand side of the above inequality comprises of pieces that
we will keep unchanged in $\phi$; we will show a way to shorten $\phi$ by
replacing the subsequence $(P^{a}_{i})_{i=i_{a}^{-}}^{i_{a}^{+}}$ with a
single generic piece for each $\phi(a)$ for which this subsequence is nonempty
(if $i^{-}_{a}>i^{+}_{a}$, then $\phi(a)$ has no generic pieces). This will
conclude the proof as the new piece will be the only generic one.

Let

$\mathcal{G}=\Gamma(I)\cap\bigcup_{a\in
A(H)}\bigcup_{i\notin[i_{a}^{-},i_{a}^{+}]}A(P^{a}_{i}),$

so in particular $|\mathcal{G}|\leqslant\|H\|\cdot(2c+2)$ as each piece
$P^{a}_{i}$ with $i\notin[i_{a}^{-},i_{a}^{+}]$ contains at most one generic
arc in $\Gamma(I)$. Since $I$ is $2\|H\|(c+f+1)$-long, we may find in $I$ a
subset $J$ of vertices not incident with $F\cup\mathcal{G}\cup\partial(I)$
such that $|J|\geqslant\|H\|$. Indeed,

$|I|\geqslant 4\|H\|(c+f+1)\geqslant 2f+2(c+1)\|H\|+2c+\|H\|\geqslant
2|F|+|\mathcal{G}|+|\partial(I)|+\|H\|.$

Now assign to each $a\in A(H)$ a different vertex $v(a)\in J$. We can use
these vertices are “pivots” for the newly constructed generic pieces. Indeed,
for every $a\in A(H)$ such that $i_{a}^{-}\leqslant i_{a}^{+}$ consider the
path

$P^{a}_{\pm}=(\operatorname{\mathsf{tail}}(\operatorname{\mathsf{first}}(P^{a}_{i_{a}^{-}})),v(a))(v(a),\operatorname{\mathsf{head}}(\operatorname{\mathsf{last}}(P^{a}_{i_{a}^{+}}))).$

This path is well-defined as the two arcs it consists of are generic (because
$v(a)$ was chosen not to be incident with $\partial(I)$). Moreover, it is
edge-disjoint with $\mathcal{G}\cup F$ and with all other
$P^{a^{\prime}}_{\pm}$ ($a^{\prime}\neq a$), as $v(a)\neq v(a^{\prime})$.
Inserting paths $P^{a}_{\pm}$ in place of the subsequences described above
gives a desired shortening and finishes the proof. $\square$

We call an $(r,c)$-type $\tau$ _short_ if for every $a\in A(H)$ the length of
$\tau(\phi(a))$ is at most $4c+6$.

######  Corollary 11.

For $r\geqslant 1$ we have the following:

  1. 1.

If an interval $I$ is $4\|H\|(r+c)$-long and $c$-flat, and a partial immersion
$\phi$ in $I$ is minimal, then $\tau^{(r,c)}(\phi)$ is short.

  2. 2.

For every pair of integers $r,c\in\mathbb{N}$ there is a constant $t(r,c)$
such that there are exactly $t(r,c)$ short $(r,c)$-types. In particular, for
any interval $I$ as above, there are at most $t(r,c)$ different $I$-admissible
minimal $(r,c)$-types.

######  Proof.

It is enough to take $F=\emptyset$ in lemma 10 to see that the lengths of
sequences $\tau^{(r,c)}(\phi(a))$ for $a\in A$ are uniformly bounded by
$2(2c+3)$. To prove that the number of types is bounded in terms of $r$ and
$c$ it is now enough to observe that the number of different equivalence
classes $R_{+}$, $R_{-}$ is so. The last claim is true as these are the
equivalence classes introduced on a set of size bounded in terms of $r$ and
$c$. $\square$

Let $I_{1}$, $I_{2}$ be two consecutive $c$-flat, $2(r+c)$-long
$\sigma$-intervals and $I=I_{1}\cup I_{2}$. We say that two $(r,c)$-types
$\tau_{1}$ of $I_{1}$ and $\tau_{2}$ of $I_{2}$ are _compatible_ if there
exists a partial immersion $\phi$ in $I$ such that $\phi|_{I_{1}}$ and
$\phi|_{I_{2}}$ are compatible, $\phi|_{I_{1}}$ has type $\tau_{1}$, and
$\phi|_{I_{2}}$ has type $\tau_{2}$.

The _gluing_ of the types $\tau_{1}\oplus\tau_{2}$ is defined as the set of
all $(r,c)$-types of all such $\phi$. The following lemma proves that this
definition is correct, i.e. that types of two immersions store enough
information to ensure the possibility of gluing them.

######  Lemma 12.

Let $I_{1}$, $I_{2}$ be two consecutive $c$-flat, $4\|H\|(r+c)$-long
$\sigma$-intervals and $I=I_{1}\cup I_{2}$. If two $(r,c)$-types $\tau_{1}$ of
$I_{1}$ and $\tau_{2}$ of $I_{2}$ are _compatible_ , then for every partial
immersion $\phi_{1}$ in $I_{1}$ of type $\tau_{1}$ and for every partial
immersion $\phi_{2}$ in $I_{2}$ of type $\tau_{2}$, the immersions $\phi_{1}$
and $\phi_{2}$ are compatible.

######  Proof.

By the definition of compatible types, we have at least one pair of compatible
partial immersions $\eta_{1}$ in $I_{1}$ and $\eta_{2}$ in $I_{2}$, of types
$\tau_{1}$ and $\tau_{2}$ respectively. Consider any
$\eta\in\eta_{1}\oplus\eta_{2}$. We will use $\eta$ as a “model” for
understanding how to successfully glue $\phi_{1}$ and $\phi_{2}$.

Fix $a\in A(H)$ and mappings $\pi_{i}$ sending the pieces of path
$\eta_{i}(a)$ to the corresponding pieces of path $\phi_{i}(a)$, in accordance
with the equality of types, where $i=1,2$. Moreover, color in $\eta(a)$ all
arcs contained in $A(I_{1},I_{1})\cup\partial^{+}(I_{1})\cup\Gamma^{-}(I_{1})$
blue, all arcs contained in
$A(I_{2},I_{2})\cup\partial^{-}(I_{2})\cup\Gamma^{+}(I_{2})$ green, and all
other arcs (i.e. the “gluing” arcs in $A(I_{1},I_{2})$) red. Thus, every piece
in $\eta(a)$ consists of alternating (and possibly empty) green and blue paths
with a red arc between each two consecutive paths of different colors.

Suppose that some piece $P$ of $\eta(a)$ contains a red arc $e$. Assume that
the maximal monochromatic nonred subpath of $P$ directly preceding this arc is
blue and the maximal monochromatic nonred subpath of $P$ directly following
this arc is green (the reasoning in the other case is analogous). Then the
blue path is a subpath of some piece $P_{1}$ of $\eta_{1}$ and the green path
is a subpath of some piece $P_{2}$ of $\eta_{2}$, where the only difference is
the arc $e$ and possibly the other extreme arcs (if they are colored red as
well). We will show that we may directly glue pieces $\pi_{1}(P_{1})$ of
$\phi_{1}$ and $\pi_{2}(P_{2})$ of $\phi_{2}$ using the arc

$e^{\prime}=(\operatorname{\mathsf{tail}}(\operatorname{\mathsf{last}}(\pi_{1}(P_{1}))),\operatorname{\mathsf{head}}(\operatorname{\mathsf{first}}(\pi_{2}(P_{2}))))$

and moreover — that such gluing can be performed simultaneously in all places
corresponding to red arcs of $\eta$. This yields a construction of a gluing
$\phi\in\phi_{1}\oplus\phi_{2}$ therefore certifying the desired
compatibility. Moreover, $\tau^{(r,c)}(\phi)=\tau^{(r,c)}(\eta)$ and $\eta$
was chosen arbitrarily, which implies that the types of immersions being glued
are enough to determine all possible types of gluings.

First of all note that if the arc $e$ is singular of color $x$, then this fact
is stored in the equivalence relations $R_{+}$ of $\tau^{(r,c)}(\eta_{1})$ and
$R_{-}$ of $\tau^{(r,c)}(\eta_{2})$. Therefore, by the equality of types of
$\eta_{i}$ and $\phi_{i}$, the arc $e^{\prime}$ is singular of color $x$ as
well, hence
$e^{\prime}=\operatorname{\mathsf{last}}(\pi_{1}(P_{1}))=\operatorname{\mathsf{first}}(\pi_{2}(P_{2}))$
and the gluing is possible.

If $e$ is generic then, again by the respective equivalence relations, no
other generic gluing arc joins vertices
$\operatorname{\mathsf{tail}}(\operatorname{\mathsf{last}}(P_{1}))$ and
$\operatorname{\mathsf{head}}(\operatorname{\mathsf{last}}(P_{1}))$. This
means that $e^{\prime}$ is generic and does not correspond to any other red
arc of $\eta$ than $e$. Therefore again the gluing along this arc can be
performed. $\square$

### Boundaried intervals and signatures.

In the process of replacing protrusions we will need to consider intervals not
as subsets of an ordered vertex set of a larger tournament, but as standalone
structures which can be used to replace one another. We introduce the notion
of an $(r,c)$-boundaried interval to enable such considerations.

######  Definition 5.

An _$(r,c)$ -boundaried interval_is a digraph $D$ on vertex set
$V(D)=S^{+}\cup I\cup S^{-}$ equipped with an ordering $\sigma_{I}$ of $I$.
Furthermore, we require the following:

  * •

$|I|\geqslant 4\|H\|(r+c)$;

  * •

$D[I]$ is a tournament;

  * •

$\sigma_{I}$ has width at most $c$;

  * •

$S^{-}\subseteq[3c]\times\\{-\\}$ and $S^{+}\subseteq[3c]\times\\{+\\}$;

  * •

each vertex of $S^{+}$ has only one incident arc and this arc belongs to the
set $\overrightarrow{A}(I,S^{+})$;

  * •

each vertex of $S^{-}$ has only one incident arc and this arc belongs to the
set $\overrightarrow{A}(S^{-},I)$.

The _$r$ -boundary_ of $D$ is the pair of sets $I^{-}$ and $I^{+}$ consisting
of the first and the last $r$ vertices of $I$ in $\sigma_{I}$, respectively.
For $D$ defined above, we will shortly write $D=I\cup S^{\pm}$.

Note that this notion emulates a $4\|H\|(r+c)$-long $c$-flat interval $I$ in
the following sense. Arcs whose heads are contained in $S^{+}$ correspond to
$\partial^{+}(I)$, and arcs whose tails are contained in the set $S^{-}$
correspond to $\partial^{-}(I)$. The names of the auxiliary vertices in
$S^{\pm}$ correspond to the $\xi$-colors of the respective backward arcs. The
$r$-boundary consists of precisely those vertices whose generic entry or exit
is remembered in the $(r,c)$-type of a partial immersion.

Formally, every $4\|H\|(r+c)$-long $c$-flat $\sigma$-interval $I$ in $T$ can
be uniquely encoded with an $(r,c)$-boundaried interval $D^{(r,c)}(I)$, whose
structure resembles the structure of $T[I]$ and $\partial(I)$ as follows:

  * •

the vertices and arcs of $I$ are kept along with their ordering in $T$;

  * •

every singular arc $a\in\partial^{\pm}(I)$ is mapped to an arc joining
$(\xi(a),\pm)\in S^{\pm}$ with the endpoint of $a$ contained in $I$;

  * •

the projection of $S^{\pm}$ onto the first coordinate is precisely
$\\{\xi(a)\mid a\in\partial^{\pm}(I)\\}$.

The notion of a partial immersion can be naturally adjusted to the setting of
boundaried intervals. The only difference is the lack of the “generic
interface” i.e. there are no auxiliary edges in boundaries intervals used to
emulate $\Gamma(I)$. These can be, however, emulated by storing the
information from the type (marker $\operatorname{\mathsf{X}}$ or number in
$[r]$ if the generic arc is incident with the $r$-boundary, and the
equivalence relations $R_{\pm}$) instead of the identity of particular generic
arcs. Formally, a piece of a scattered path in $(r,c)$-boundaried interval can
begin or end with an element in $\\{\operatorname{\mathsf{X}}\\}\cup[r]$
instead of a generic arc. In particular, this slightly modified variant of
partial immersions can be equipped with precisely the same definition of
admissible $(r,c)$-type as in the former case.

######  Definition 6.

An _$(r,c)$ -signature_ is a subset of the set of all short $(r,c)$-types. The
_$(r,c)$ -signature_ $\Sigma^{(r,c)}(I)$ of a $4\|H\|(r+c)$-long $c$-flat
$\sigma$-interval $I$ is the set of all $I$-admissible minimal $(r,c)$-types.
The _$(r,c)$ -signature_ $\Sigma^{(r,c)}(D)$ of an $(r,c)$-boundaried interval
$D=I\cup S^{\pm}$ is the set of all $I$-admissible minimal $(r,c)$-types.

The intuition behind this definition is that if $I$ is appropriately long and
flat, then the signature of $I$ stores the information about all possible
interactions of $I$ with minimal partial immersions. Note that
$\Sigma^{(r,c)}(D^{(r,c)}(I))=\Sigma^{(r,c)}(I)$.

We say that two $(r,c)$-boundaried intervals $I\cup S^{\pm}$ and
$I^{\prime}\cup S^{\prime\pm}$ are _exchangeable_ if they have equal
$(r,c)$-signatures, $S^{\pm}=S^{\prime\pm}$ (both intervals use precisely the
same colors on the boundary), and the incidence structure of $r$-boundaries of
those intervals with backward arcs is the same, i.e. for every $i\in[r]$ the
set of colors of singular arcs incident with both $S^{\mp}$ and the $i$-th
vertex of $I^{\pm}$ is the same as analogously defined set of colors for
$i$-th vertex of $I^{\prime\pm}$. Intuitively this means that in $T$ we may
replace the interval $I$ with $I^{\prime}$.

######  Corollary 13.

For every pair of integers $r,c\in\mathbb{N}$ there is a constant $s(r,c)$
such that there are exactly $s(r,c)$ different $(r,c)$-signatures.

######  Proof.

We may set $s(r,c)=2^{t(r,c)}$, where $t(r,c)$ is the constant provided by
corollary 11. $\square$

For future discussion of algorithmic aspects, we will need the following
observation.

######  Lemma 14.

Consider $r$ and $c$ fixed and let $T$, $\sigma$, and $I$ be as in definition
6. Then given $T$, $\sigma$, and $I$, the signature $\Sigma^{(r,c)}(I)$ can be
computed in polynomial time.

######  Proof.

It suffices to decide, for every short $(r,c)$-type $\tau$, whether $\tau$ is
$I$-admissible. This can be done in polynomial time using the algorithm for
rooted immersion containment of Fomin and Pilipczuk [15]. Alternatively, it
follows from the result of Ganian et al. [16, Theorem 17] that
$I$-admissibility of a fixed type $\tau$ can be expressed using an
$\mathsf{MSO}$ formula. Then one can apply the algorithm for $\mathsf{MSO}$
model-checking on structures of bounded cliquewidth [11] in conjunction with
the observation that boundedness of cutwidth entails boundedness of
cliquewidth for tournaments [15]. $\square$

Let $\mathcal{S}^{(r,c)}$ be the set of all $(r,c)$-signatures; we have
$|\mathcal{S}^{(r,c)}|=s(r,c)$, where $s(r,c)$ is the constant given by
corollary 13. Let $\mathcal{S}^{(r,c)}_{\sigma}$ be the set of those
$(r,c)$-signatures which are equal to $\Sigma^{(r,c)}(I)$ for some
$\sigma$-interval $I$, i.e. contain only $I$-admissible minimal $(r,c)$-types.
Then $\mathcal{S}^{(r,c)}_{\sigma}\subseteq S^{(r,c)}$, so
$|\mathcal{S}^{(r,c)}_{\sigma}|\leqslant s(r,c)$. We argue that
$\mathcal{S}^{r,c}_{\sigma}$ has a structure of a semigroup in the following
sense.

######  Lemma 15.

Let $I_{1}$, $I_{2}$ be two $4\|H\|(r+c)$-long $c$-flat $\sigma$-intervals
such that $I=I_{1}\cup I_{2}$ is a $c$-flat $\sigma$-interval. Then
$\Sigma^{(r,c)}(I)$ is uniquely determined by $\Sigma^{(r,c)}(I_{1})$ and
$\Sigma^{(r,c)}(I_{2})$.

######  Proof.

It is enough to prove that:

  * (i)

for every $\tau\in\Sigma^{(r,c)}(I)$ there exist
$\tau_{1}\in\Sigma^{(r,c)}(I_{1})$ and $\tau_{2}\in\Sigma^{(r,c)}(I_{2})$
which are compatible and $\tau\in\tau_{1}\oplus\tau_{2}$; and

  * (ii)

for every two compatible $\tau_{1}\in\Sigma^{(r,c)}(I_{1})$ and
$\tau_{2}\in\Sigma^{(r,c)}(I_{2})$ and every $\tau\in\tau_{1}\oplus\tau_{2}$
that is minimal in $I$, we have $\tau\in\Sigma^{(r,c)}(I)$.

For the proof of (i) take a minimal partial immersion $\phi$ in $I$ with
$\tau^{(r,c)}=\tau$. We know that
$\tau\in\tau^{(r,c)}(\phi|_{I_{1}})\oplus\tau^{(r,c)}(\phi|_{I_{2}})$, so it
is enough to prove that $\phi|_{I_{1}}$ and $\phi|_{I_{2}}$ are minimal. But
this follows directly from 7.

For the proof of (ii) note that $\tau_{1}\oplus\tau_{2}$ consists only of
$I$-admissible types. $\square$

Lemma 15 implies that the set $\mathcal{S}^{(r,c)}_{\sigma}\cup\\{0\\}$ can be
endowed with an associative binary product operation such that for every two
consecutive intervals $I_{1}$, $I_{2}$, the product of their signatures is the
signature of their union $I_{1}\cup I_{2}$. Formally, we set the product for
all pairs of consecutive intervals as above; lemma 15 enures that this is
well-defined. Next, for all pairs of elements
$\tau_{1},\tau_{2}\in\mathcal{S}^{r,c}_{\sigma}$ for which their product is
not yet defined, we set $\tau_{1}\cdot\tau_{2}=0$. Also, we set $0=0\cdot
0=0\cdot\tau=\tau\cdot 0$ for all $\tau\in\mathcal{S}^{(r,c)}_{\sigma}$. In
this way, $\mathcal{S}^{(r,c)}_{\sigma}\cup\\{0\\}$ becomes a monoid; the
empty signature is the neutral element of multiplication.

By lemma 5 we obtain the following.

######  Corollary 16.

Suppose $I$ is a $c$-flat $4\|H\|(r+c)\ell^{3s(r,c)}$-long $\sigma$-interval.
Then there exists a sequence of consecutive $4\|H\|(r+c)$-long $c$-flat
$\sigma$-intervals $(I_{i})_{i=1}^{\ell}$ whose $(r,c)$-signatures are equal
and equal to the signature of their union. Moreover, given $r$, $c$, $T$,
$\sigma$, and $I$, such a sequence can be found in polynomial time.

######  Proof.

Let $(X_{i})_{i=1}^{\ell^{3s(r,c)}}$ be an arbitrary sequence of consecutive
$4\|H\|(r+c)$-long $c$-flat $\sigma$-intervals included in $I$. Note that
$\Sigma^{(r,c)}_{\sigma}\colon A^{\ast}\to\mathcal{S}^{(r,c)}$ is a properly
defined morphism, sending a single interval to its signature and a
concatenation of two consecutive intervals to the unique signature of their
union (which is not $0$). Applying lemma 5 finishes the proof; the algorithmic
statement follows from the remark after lemma 5. $\square$

##  4 Finding protrusions

In order to find an appropriately large subgraph of $T$ which does not
“affect” the behavior of $T$ with respect to $H$-hitting Immersions in
Tournaments, we roughly proceed as follows. First, we find a suitable ordering
$\sigma$ of $V(T)$ and an appropriately long interval $X$ in $\sigma$ such
that $X$ has a constant-size singular interface towards the remainder of $T$.
Then, inside $X$, we find (again, an appropriately long) subinterval $I$ of a
very specific structure: $I$ can be divided into $2k+3$ subintervals with the
same signatures as itself. This is where we use Simon Factorization through
corollary 16. In the next part we use this extra structure to prove that one
of these subintervals can be replaced with a strictly smaller replacement in
such a way that after the substitution, we obtain an equivalent instance of
the problem.

We proceed to a formal implementation of this plan. The first lemma gives the
ordering $\sigma$ and the interval $X$.

######  Lemma 17.

Let $T$ be a tournament with $\operatorname{\mathbf{ctw}}(T)\leqslant c$ and
$|T|\geqslant(2c+1)(x+1)(k+1)$. If $T$ contains at most $k$ arc-disjoint
immersion copies of $H$, then there exists an ordering $\sigma$ of $V(T)$ and
an $H$-free $\sigma$-interval $X$ such that $|X|\geqslant x$ and $X$ is
$c_{H}$-flat with respect to $\sigma$.

Moreover, given $T,k,c,x$ as above, one can in polynomial time either conclude
that $T$ contains more than $k$ arc-disjoint immersion copies of $H$, or find
an ordering $\sigma$ and an interval $X$ satisfying the above properties.

######  Proof.

We first argue the existential statement, and then address the algorithmic
aspects at the end.

Let $\sigma_{0}$ be an ordering of $V(T)$ of width
$\operatorname{\mathbf{ctw}}(T)\leqslant c$. Consider any $k+1$ vertex-
disjoint $\sigma_{0}$-intervals, each containing at least $(2c+1)(x+1)$
vertices. By assumption, at least one of them, say $I$, induces an $H$-free
graph. Let $B=\partial(I)$. Then $|B|\leqslant 2c$.

Note that we have $\operatorname{\mathbf{ctw}}(T[I])\leqslant c_{H}$ by
corollary 4. Let $\sigma_{I}$ be an ordering of vertices of $I$ of width
$\operatorname{\mathbf{ctw}}(T[I])$ and let $\sigma$ be the ordering obtained
from $\sigma_{0}$ by reordering $I$ according to $\sigma_{I}$, that is,

  * •

If $u,v\in I$ then $\sigma(u)<\sigma(v)\iff\sigma_{I}(u)<\sigma_{I}(v)$.

  * •

If $u\notin I$ or $v\notin I$, then
$\sigma(u)<\sigma(v)\iff\sigma_{0}(u)<\sigma_{0}(v)$.

Consider the set

$I_{-B}\coloneqq I-\left(\\{\operatorname{\mathsf{tail}}(a)\mid
a\in\partial^{+}(I)\\}\cup\\{\operatorname{\mathsf{head}}(a)\mid
a\in\partial^{-}(I)\\}\right),$

i.e. the vertices in $I$ which are not incident with $B$. Since $|B|\leqslant
2c$, we have that $|I_{-B}|>(2c+1)x$ and $I_{-B}$ is the union of at most
$2c+1$ $\sigma$-intervals. Hence, at least one of these intervals has size at
least $x$. Call it $X$.

Let

$I^{-}\coloneqq\\{v\in I\leavevmode\nobreak\ |\leavevmode\nobreak\
\sigma(v)<\sigma(w)\text{ for every }w\in X\\}\quad\textrm{and}\quad
I^{+}=I-I^{-}-X.$

Note that as no arc from $B$ is adjacent to $X$, $\overrightarrow{A}(X,I^{-})$
contains precisely all $\sigma$-backward arcs in $T$ with tail in $X$, and
$\overrightarrow{A}(I^{+},X)$ contains all those with head in $X$. On the
other hand, both $\overrightarrow{A}(X,I^{-})$ and
$\overrightarrow{A}(I^{+},X)$ have size bounded by the width of $\sigma_{I}$,
which is at most $c_{H}$. It follows that $X$ is $c_{H}$-flat with respect to
$\sigma$.

As for the algorithmic aspect, an ordering $\sigma_{0}$ with optimum width can
be computed using lemma 2. Then we can divide $\sigma_{0}$ into $k+1$ disjoint
$\sigma_{0}$-intervals of size at least $(2c+1)(x+1)$ each, and for each of
them check in polynomial time whether it induces an $H$-free subtournament
using the algorithm from [15]. If this check fails for each of the intervals,
we may terminate the algorithm and conclude that $T$ contains $k+1$ arc-
disjoint copies of $H$. Otherwise, we have one interval $I$ such that $T[I]$
is $H$-free, and it is straightforward to turn the remainder of the reasoning
into a polynomial-time algorithm computing $\sigma$ and $X$. $\square$

In the remainder of this section let $x\geqslant 4\|H\|$, $r$, $c$ be fixed
positive integers. Moreover, let $T$ be a tournament for which there exists an
optimal solution of size at most $k$ and let $\sigma$ be an ordering of $T$.
Finally let $X$ be an $H$-free $c$-flat $x(3c+k+1)(2k+3)^{3s(r,c)}$-long
$\sigma$-interval. We assume that there is a coloring $\xi$ mapping all
$\sigma$-backward arcs incident to $X$ to colors in $[3c]$ such that not two
such arcs of the same color participate in the same $\sigma$-cut.

We may apply corollary 16 to $X$ to find a collection of $2k+3$ consecutive
$\sigma$-intervals $I_{i}$ with $|I_{i}|=x(3c+k+1)$ for all $i\in[2k+3]$ such
that all $I_{i}$ have equal $(r,c)$-signatures, and this common signature,
call it $\Sigma$, is equal to the $(r,c)$-signature of their union $I$. Then
$I$ is an $H$-free $c$-flat $x(3c+k+1)(2k+3)$-long $\sigma$-interval. That
such $I$ can be found in polynomial time (given $r$, $c$, $x$, $T$, $X$,
$\sigma$, and $\xi$) follows from corollary 16.

Now comes a key step in the proof: we argue that from the equality of types of
$I,I_{1},\ldots,I_{2k+3}$ it follows that every optimum solution will contain
a bounded number of arcs incident with $I$.

######  Lemma 18.

For every optimal solution $F\subseteq A(T)$, we have $|F\cap
A(I,V(T))|\leqslant 2c$.

######  Proof.

Fix an optimal solution $F$. By assumption, $|F|\leqslant k$.

Define

$F_{\star}=(F-A(I,V(T)))\cup\partial(I).$

That is, $F_{\star}$ is obtained from $F$ by removing all arcs incident with
$I$ are replacing them with all $I$-singular arcs. We will prove that
$F_{\star}$ is a solution in $T$. Observe that since $F$ is optimal, this will
imply that

$\displaystyle|F\cap A(I,V(T))|$ $\displaystyle=|F|-|F-A(I,V(T))|$
$\displaystyle\leqslant|F_{\star}|-|F-A(I,V(T))|=|F_{\star}\cap
A(I,V(T))|=|\partial(I)|\leqslant 2c,$

and in consequence we may set $X_{\star}\coloneqq I$.

Suppose for the sake of contradiction that $F_{\star}$ is not a solution in
$T$, i.e. there exists an immersion model $\phi$ of $H$ in $T-F_{\star}$. We
may choose $\phi$ so that $\phi|_{I}$ is minimal. As

$|I|\geqslant x(3c+k+1)\geqslant 4\|H\|(c+(2c+k)+1)\geqslant
4\|H\|(c+|F_{\star}|+1),$

by lemma 10 we have that $\tau^{(r,c)}(\phi|_{I})$ is short. Note that $\phi$
is incident with $I$ for otherwise it would have not been hit by $F$,
contradicting $F$ being a solution. Moreover, $A(\phi)\cap
A(I,V(T))\subseteq\Gamma(I)$ as all singular arcs incident with $I$ are in
$F_{\star}$ which is disjoint with $\phi$.

Observe that since each of the at most $k$ arcs in $F$ is incident with at
most $2$ intervals $I_{j}$, there exists $i\in[2k+3]$ such that $i\neq 1$,
$i\neq 2k+3$, and $I_{i}$ is not incident with $F$. Pick vertices
$v_{\alpha}\in V(I_{1})$, $v_{\omega}\in V(I_{2k+3})$ which are not incident
with $\partial(I)\cup\partial(I_{i})\cup F$. This is possible since

$|I_{1}|,|I_{2k+3}|\geqslant
3c+k+1>c+c+k\geqslant|\partial(I)|+|\partial(I_{i})|+|F|\geqslant|\partial(I)\cup\partial(I_{i})\cup
F|.$

By equality of signatures of $I$ and $I_{i}$ and the shortness of
$\tau^{(r,c)}(\phi|_{I})$, we conclude that there exists a partial immersion
$\phi^{\prime}$ in $I_{i}$ of the same type as $\phi|_{I}$, which moreover has
a purely generic boundary (i.e. does not contain any $I$-singular arcs).

Now it is enough to observe that we can connect $\phi^{\prime}$ with
$\phi|_{T-I}$ to get an immersion of $H$ in $T$ disjoint with $F$. We shall
use $v_{\alpha}$ and $v_{\omega}$ as pivots for two-arc generic paths,
similarly as in the proof of lemma 10. In other words, to enrich
$\phi^{\prime}$ and $\phi|_{T-I}$ to a full immersion model of $H$, we insert
a collection of two-arc generic paths with middle vertices in $v_{\alpha}$ or
$v_{\omega}$, joining vertices on $\phi^{\prime}$ with vertices on
$\phi|_{T-I}$.

Formally, for every $a\in A(H)$ for which $\phi(a)$ is incident with both $I$
and $T-I$ we do the following. Consider all arcs used for gluing
$\phi|_{I}(a)$ with $\phi|_{T-I}(a)$. As argued above, all these arcs are
generic. For each such arc $g\in\Gamma^{+}(I)$ consider the piece $P$ of the
scattered path $\phi(a)$ with $g=\operatorname{\mathsf{last}}(P)$ and let
$P^{\prime}$ be the corresponding piece of the corresponding (via equality of
the $(r,c)$-types) scattered path $\phi^{\prime}(a)$. Now replace the arc
$\operatorname{\mathsf{last}}(P^{\prime})$ with a two-arc path

$(\operatorname{\mathsf{tail}}(\operatorname{\mathsf{last}}(P^{\prime})),v_{\omega})(v_{\omega},\operatorname{\mathsf{head}}(g))$

joining $P^{\prime}$ with the piece $Q$ of $\phi|_{T-I}(a)$ which is glued in
$\phi$ along $g$ to $P$. Finally remove $g$ from $Q$. We perform a similar
replacement for each $g\in\Gamma^{-}(I)$ (changing the roles in each pair
first/last, head/tail, $v_{\alpha}$/$v_{\omega}$). The choice of $v_{\alpha}$
and $v_{\omega}$ ensures that the new connections are arc-disjoint and
disjoint with $F$. $\square$

We define a digraph $T^{\circ}$ based on $T$ and $I=I_{1}\cup\ldots\cup
I_{2k+3}$ as follows: start with $T$, and

  * •

remove all vertices of $I_{2}$;

  * •

for every arc $a\in\partial^{+}(I_{2})$, replace $a$ with an arc with the same
head as $a$ and tail in a fresh vertex $s^{+}_{\xi(a)}$;

  * •

for every arc $a\in\partial^{-}(I_{2})$, replace $a$ with an arc with the same
tail as $a$ and head in a fresh vertex $s^{-}_{\xi(a)}$.

We call the constructed graph a _$c$ -boundaried co-interval_. The intuition
of this construction is as follows. We pinch off one of the $2k+3$ intervals
and keep the singular arc interface in a fashion similar as in
$(r,c)$-boundaried intervals. The only difference is that we do not keep track
of the $r$-boundary vertices.

Now we can define the _gluing_ of $T^{\circ}$ with an $(r,c)$-boundaried
interval $B=I\cup S^{\pm}$ with signature $\Sigma$, simply by identifying the
singular arcs of the same color (note that different vertices from $S^{\pm}$
can be therefore mapped to the same vertex) and completing the obtained
structure to a tournament by making all missing arcs generic. Note that in
order for this to be well-defined, we need to require that the sets of colors
of the singular arcs in $T^{\circ}$ and in $B$ are identical — if it is so, we
will say that $T^{\circ}$ and $B$ are _compatible_. Also, note that we require
that the signature of $B$ is $\Sigma$: that is, the possible types of partial
immersions present in $B$ are exactly the same as in the substituted interval
$I_{2}$.

Denote by $T^{\circ}\oplus B$ the tournament obtained from gluing $T^{\circ}$
and $B$. Note that in this tournament we have naturally defined ordering of
vertices: in $T^{\circ}$ it is inherited from the ordering $\sigma$ of $T$ and
within $B$ it is inherited from the ordering $\sigma_{I}$ of the boundaried
interval. Finally all the vertices of the substituted interval appear in the
ordering between the two interval parts (prefix and suffix) of the co-
interval. The following observation is obvious.

######  Observation 19.

If two exchangable $(r,c)$-boundaried intervals $B=I\cup S^{\pm}$ and
$B^{\prime}=I^{\prime}\cup S^{\pm}$ are compatible with $T^{\circ}$, then the
$(r,c)$-signatures of $I$ in $T^{\circ}\oplus B$ and $I^{\prime}$ in
$T^{\circ}\oplus B^{\prime}$ are equal.

We now observe, by inspecting the proof of lemma 18, that if in $I$ we replace
one of its subintervals with an exchangeable interval, then the conclusion of
lemma 18 — that the modified $I^{\prime}$ will still have constant incidence
with every optimal solution in $T$ — will still hold. Let us summarize this
section with putting together these observations and recalling all needed
assumptions.

######  Corollary 20.

Suppose that $x\geqslant 4\|H\|$, $r$, $c$ are fixed positive integers, $T$ is
a tournament of for which there exists an optimal solution of size at most $k$
and $\sigma$ is an ordering of $T$. Suppose further that $X$ is an $H$-free
$c$-flat $x(3c+k+1)(2k+3)^{3s(r,c)}$-long $\sigma$-interval with all incident
$\sigma$-backward arcs colored according to $\xi$ with colors $[3c]$ so that
no two arcs of the same color participate in the same $\sigma$-cut.

Then there exists an $(r,c)$-signature $\Sigma$, a $c$-boundaried co-interval
$T^{\circ}$ of this signature, and an $(r,c)$-boundaried interval $B=I\cup
S^{\pm}$ such that $T=T^{\circ}\oplus B$ and moreover for every
$B^{\prime}=I^{\prime}\cup S^{\prime\pm}$ exchangeable with $B$ and for every
optimal solution $F\subseteq A(T^{\prime})$ where $T^{\prime}=T^{\circ}\oplus
B^{\prime}$ we have: $|F\cap A(I^{\prime},T^{\prime})|\leqslant 2c$. Moreover,
given $x$, $r$, $c$, $T$, $\sigma$, and $X$, such $\Sigma$, $T^{\circ}$, and
$B$ can be computed in polynomial time.

######  Proof.

It is enough to see that the argument from the proof of lemma 18 can be
applied to both $T$ and $T^{\prime}$ to obtain constant incidence of any
optimum solution with $I$ (and $I^{\prime}$). Constant incidence with an
interval means in particular constant incidence with each of its subintervals.
As for the algorithmic statement, it follows directly from corollary 16 and
lemma 14. $\square$

##  5 Replacing protrusions

In the entire section we fix $c\coloneqq c_{H}$, where $c_{H}$ is the constant
from corollary 4, and $r\coloneqq 6\|H\|c$. Moreover we assume that
$x\geqslant 4\|H\|$; the precise value of $x$ will be determined later.

######  Definition 7.

_Protrusion_ is any $(r,c)$-boundaried interval $X=I\cup S^{\pm}$ which is
$H$-free and $x(3c+k+1)$-long. For brevity we will refer to $X$ as to $I$. The
set $\Sigma^{(r,c)}(X)$ is the _signature_ of the protrusion.

Let $T$ be a tournament equipped with a vertex ordering $\sigma$ and let $I$
be an $H$-free interval and such that $T=T^{\circ}\oplus X$, where $X$ is a
protrusion of signature $\Sigma$. Let $I\subseteq V(T)$ be the interval
defined by the protrusion. Fix the coloring $\xi$ of $\sigma$-backward arcs
incident with $I$.

Recall that from corollary 20 follows that for every $(r,c)$-boundaried co-
interval $T^{\circ}$ compatible with $X$ if $T^{\circ}\oplus X$ admits an
optimal solution $F$ of size not greater than $k$, then there are at most $2c$
arcs in $F$ incident with $X$.

For every protrusion $X=I\cup S^{\pm}$ define a function $f_{X}\colon
2^{\mathcal{S}^{(r,c)}}\to\\{0,1,2,\ldots,2c\\}\cup\\{\infty\\}$ as follows:
$f_{X}(S)$ is the minimum number of arcs in $A(I,I)$ needed to hit all partial
immersions in $I$ whose signatures belong to $S$, or $\infty$ if this number
is greater than $2c$.

We introduce an equivalence relation $\sim$ on the set of all protrusions. Let
$X=I\cup S^{\pm}$, $X^{\prime}=I^{\prime}\cup S^{\prime\pm}$. We say that
$X\sim X^{\prime}$ if:

  * •

$S^{\pm}=S^{\prime\pm}$;

  * •

$\Sigma^{(r,c)}(X)=\Sigma^{(r,c)}(X^{\prime})$; and

  * •

$f_{X}(S)=f_{X^{\prime}}(S)$ for every $S\subseteq\mathcal{S}^{(r,c)}$.

Note that the number of equivalence classes of $\sim$ is finite and bounded by
a constant depending only on $H$. This means that if in each class we pick a
representative with the minimal number of vertices (call each such element a
_small_ protrusion), then all small protrusions will have size bounded from
above uniformly by a constant $s_{H}$ depending on the digraph $H$ only.

Same arguments as in the proof of lemma 14 give the following.

######  Lemma 21.

Given protrusions $X$ and $X^{\prime}$ it can be decided in polynomial time
whether $X\sim X^{\prime}$.

We now argue that equivalent protrusions are replaceable.

######  Lemma 22.

Suppose that $T=T^{\circ}\oplus X$ is a tournament satisfying the conclusion
of corollary 20, where $X$ is a boundaried $(r,c)$-interval of signature
$\Sigma$ and $T^{\circ}$ is a $c$-boundaried co-interval which is compatible
with $X$.

Then for every $X^{\prime}$ such that $X\sim X^{\prime}$, the optimal solution
in $T^{\circ}\oplus X$ is of size not greater than $k$ if and only if the
optimal solution in $T^{\circ}\oplus X^{\prime}$ is of size not greater than
$k$.

######  Proof.

We will prove the forward implication only; the proof of the other one is
completely analogous due to the symmetry of the roles of $X$ and $X^{\prime}$.

Let $F$ be an optimal solution in $T$ and suppose that $|F|\leqslant k$. Let

$F_{0}=F-A(X,V(T)),\qquad F_{1}=F\cap A(V(T)\setminus
X,X)\quad\textrm{and}\quad F_{X}=F\cap A(X,X).$

By the assumption that $T=T^{\circ}\oplus X$ satisfies the conclusion of
corollary 20, we have $|F_{1}\cup F_{X}|\leqslant 2c$.

######  Claim 1.

Every $X$-generic arc of $F_{1}$ is incident with the $r$-boundary of $X$.

######  Proof (of claim).

Suppose for the sake of contradiction that in $F_{1}$ there exists an
$X$-generic arc $g$ not incident with the $r$-boundary of $X$. This means that
this arc is incident with an _internal_ vertex of $X$, i.e. the vertex being
$\sigma$-smaller than all vertices in $X_{r}^{+}$ and $\sigma$-larger than all
vertices in $X_{r}^{-}$.

By the optimality of $F$ we conclude that in $T-(F-g)$ there exist immersion
models of $H$, and moreover each such model uses the arc $g$. Let us choose
such model $\phi$ with the property that the partial immersion $\phi|_{X}$
cannot be non-trivially shortened. We will show a way to “reroute” the generic
connection containing $g$ to avoid $F$, all $X$-singular arcs and all other
generic arcs used in $\phi$. This way we expose an immersion model of $H$ in
$T-F$, which is a contradiction.

This is the part of the proof where the $r$-boundary of $X$ (and keeping track
of the $r$-boundaries in the definition of types) comes into play. In the
beginning of this section we picked $r$ large enough to ensure the existence
of a “pivot” vertex, which can be used for rerouting.

Suppose that $g\in\Gamma^{+}(X)$; the case $g\in\Gamma^{-}(X)$ is analogous.
Denote $v=\operatorname{\mathsf{tail}}(g)$. Note that at most $4c$ vertices of
$X_{r}^{+}$ are incident with $F_{1}\cup F_{X}$, as $|F_{1}\cup
F_{X}|\leqslant 2c$. Moreover
$|\overrightarrow{A}(X_{r}^{+},\\{v\\})|\leqslant c$, because $X$ is $c$-flat.
The number of vertices of $X_{r}^{+}$ incident with $\partial^{-}(X)$ also
does not exceed $c$.

For every $a\in A(H)$ the number of arcs on $\phi|_{X}(a)$ with tail in $v$
does not exceed $1$ as otherwise $\phi|_{X}(a)$ could be non-trivially
shortened contradicting minimality of $\phi|_{X}$. So the number of arcs in
$\Gamma^{+}(X)\cap(F_{1}\cup F_{X}\cup A(\phi|_{X}))$ incident with
$X_{r}^{+}$ is not greater than $\|H\|$. Together this means that if

$r>6c+\|H\|,$

which is true, then there exists a vertex $v_{\omega}\in X_{r}^{+}$ which is
not incident with any of the special arcs mentioned above. The arc
$(v,v_{\omega})$ exists and is not contained in $F\cup A(\phi)$. Neither is
the arc joining $v_{\omega}$ with the respective vertex in $T-X$. The arc $g$
may therefore be replaced by a path composed of the two arcs described above.
And so we have obtained an immersion model of $H$ in $T-F$, a contradiction.

$\square$

Let $S$ be the set of all short types $\tau$ such that every $X$-admissible
partial immersion of type $\tau$ intersects with $F_{X}$. Because
$f_{X}(S)=f_{X^{\prime}}(S)$, we know that there exists a set $F_{X^{\prime}}$
of arcs of $A(X^{\prime})$ in $T^{\prime}\coloneqq T^{\circ}\oplus X^{\prime}$
such that $|F_{X^{\prime}}|\leqslant|F_{X}|$ and each partial immersion whose
type is in $S$ intersects with $F_{X^{\prime}}$. Let $F^{\prime}_{1}\subseteq
A(T^{\prime}-X^{\prime},X^{\prime})$ be the set directly corresponding to
$F_{1}$ by a natural bijection that maps each singular arc of to the singular
arc of the same color, and each generic arc to a generic arc whose the
endpoint in $T^{\circ}$ is the same and the other endpoint has the same index
in the respective $r$-boundary (by 1, this endpoint must belong to the
respective boundary). We will prove that the set $F^{\prime}\coloneqq
F_{0}\cup F^{\prime}_{1}\cup F_{X^{\prime}}$ is a solution in $T^{\prime}$,
thereby completing the proof due to $|F^{\prime}|\leqslant|F|$.

Suppose for the sake of contradiction that there exists an immersion model
$\phi$ of $H$ in $T^{\prime}-F^{\prime}$. Choose one such that
$\phi|_{X^{\prime}}$ is minimal. Therefore, by lemma 10, $\phi|_{X^{\prime}}$
is short. Moreover $\tau^{(r,c)}(\phi|_{X^{\prime}})\notin S$, so in $T$ there
exists a partial immersion $\phi_{X}$ in $X$ which is disjoint with $F$ and
such that $\tau^{(r,c)}(\phi_{X})=\tau^{(r,c)}(\phi|_{X^{\prime}})$. We will
show a way to reconstruct an immersion model of $H$ in $T$ from $\phi_{X}$ and
$\phi|_{T^{\circ}}$ which will be disjoint with $F$ and hence will give the
desired contradiction. We may follow closely the strategy used in the proof of
lemma 12, taking an additional care about ensuring disjointness with $F$.

We know that $\phi_{X}$ is disjoint with $F$, so for sure the direct gluing
along singular arcs is possible, as it was so with $\phi|_{X^{\prime}}$ and
$\phi_{T^{\circ}}$. Moreover, gluing along generic arcs with one endpoint $u$
on the $r$-boundary of $X$ and the other one $v$ in $T^{\circ}$ is possible
since the arc $uv$ is generic, not incident with $F$ and will not have to be
introduced more than once (this is “guarded” by the equivalence relations
$R^{\pm}$).

$\square$

We are now set up with all tools needed to prove our main theorem.

######  Proof (of theorem 1).

We prove that provided $|T|>C\cdot k^{C}$, where the constant $C$ will be
defined later, one can compute an instance $(T^{\prime},k)$ equivalent to
$(T,k)$ and satisfying $|T^{\prime}|<|T|$. The conclusion will follow from
applying such reduction (at most) $|T|$ times.

First of all note that from theorem 3 for a digraph being a disjoint union of
$k$ exemplars of $H$, we conclude that if $T$ does not contain $k$ arc-
disjoint immersion copies of $H$, then
$\operatorname{\mathbf{ctw}}(T)\leqslant c_{0}k^{2}$ for some constant $c_{0}$
(depending on $H$). In particular, it follows that if
$\operatorname{\mathbf{ctw}}(T)>k^{2}c_{0}$ (which can be established in
polynomial time using lemma 2), then $T$ is a no-instance. So from now on we
may assume that $\operatorname{\mathbf{ctw}}(T)\leqslant c_{0}k^{2}$.

Let $c=c_{H}$, $r=6\|H\|c$, $x^{\prime}=\max\left\\{4\|H\|,s_{H}+1\right\\}$
and $x=x^{\prime}(3c+k+1)(2k+3)^{3s(r,c)},$ where $s(r,c)$ is defined in
corollary 13. Let $C$ be a constant satisfying
$Ck^{C}\geqslant(2k^{2}c_{0}+1)(x+1)(k+1)$, e.g.
$C=\max\\{3s(r,c)+4,5^{3s(r,c)}\cdot 3c_{0}\cdot 4x^{\prime}\cdot(6c+2)\\}$.

Suppose that $T$ is a tournament satisfying
$\operatorname{\mathbf{ctw}}(T)\leqslant k^{2}c_{0}$ and $|T|>Ck^{C}$.
Applying lemma 17, we either conclude that $T$ admits more than $k$ arc-
disjoint copies of $H$ (so $(T,k)$ is a no-instance), or find an ordering
$\sigma$ of $V(T)$ and an $H$-free $c$-flat $x$-long $\sigma$-interval $J$.
Both conclusions can be effectively gained in polynomial time.

In the latter case, we may use corollary 16 in a manner described in section 4
to find in $J$ an $H$-free $c$-flat $x^{\prime}(3c+k+1)(2k+3)$-long
$\sigma$-interval $I$ of $(r,c)$-signature $\Sigma$, which can be decomposed
to $2k+3$ consecutive $x^{\prime}(3c+k+1)$-long $\sigma$-intervals $I_{i}$,
each of $(r,c)$-signature $\Sigma$. Both $I$ and $\Sigma$ are found in
polynomial time.

Let $T=T^{\circ}\oplus X$ be the decomposition where $T^{\circ}$ is a
$c$-boundaried co-interval and $X=(I_{2}\cup S^{\pm},\Sigma)$ is a protrusion
corresponding to $I_{2}$. Clearly, $X$ is compatible with $T^{\circ}$. Using
lemma 21 we may check in polynomial time all small protrusions to find one
$X^{\prime}$ such that $X^{\prime}\sim X$. Let us define
$T^{\prime}=T^{\circ}\oplus X^{\prime}$.

By lemma 22 we conclude that $(T^{\prime},k)$ is an instance of $H$-hitting
Immersions in Tournaments equivalent to $(T,k)$. Moreover as
$|X^{\prime}|\leqslant s_{H}<|X|$, we have that $|T^{\prime}|<|T|$. $\square$

## References

  * [1] N. Alon, D. Lokshtanov, and S. Saurabh.  Fast FAST.  In 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, volume 5555 of Lecture Notes in Computer Science, pages 49–58. Springer, 2009.

  * [2] F. Barbero, C. Paul, and M. Pilipczuk.  Exploring the complexity of layout parameters in tournaments and semicomplete digraphs.  ACM Trans. Algorithms, 14(3):38:1–38:31, 2018.
  * [3] S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, and M. Zehavi.  Packing arc-disjoint cycles in tournaments.  Algorithmica, 83(5):1393–1420, 2021.
  * [4] S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh, and S. Thomassé.  Kernels for feedback arc set in tournaments.  Journal of Computer and System Sciences, 77(6):1071–1078, 2011\.
  * [5] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos.  (Meta) Kernelization.  J. ACM, 63(5):44:1–44:69, 2016.
  * [6] M. Bojanczyk.  Factorization forests.  In 13th International Conference on Developments in Language Theory, DLT 2009, volume 5583 of Lecture Notes in Computer Science, pages 1–17. Springer, 2009.
  * [7] M. Bonamy and M. Pilipczuk.  Graphs of bounded cliquewidth are polynomially $\chi$-bounded.  Advances in Combinatorics, 2020:8, 2020.
  * [8] Ł. Bożyk and M. Pilipczuk.  On the Erdős-Pósa property for immersions and topological minors in tournaments.  Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, Apr. 2022.
  * [9] M. Chudnovsky, A. Ovetsky Fradkin, and P. D. Seymour.  Tournament immersion and cutwidth.  Journal of Combinatorial Theory, Series B, 102(1):93–101, 2012\.
  * [10] M. Chudnovsky and P. D. Seymour.  A well-quasi-order for tournaments.  Journal of Combinatorial Theory, Series B, 101(1):47–53, 2011\.
  * [11] B. Courcelle, J. A. Makowsky, and U. Rotics.  Linear time solvable optimization problems on graphs of bounded clique-width.  Theory of Computing Systems, 33(2):125–150, 2000.
  * [12] U. Feige.  Faster FAST (Feedback Arc Set in Tournaments).  CoRR, abs/0911.5094, 2009.
  * [13] F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh.  Planar $\mathcal{F}$-Deletion: Approximation, kernelization and optimal FPT algorithms.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 470–479. IEEE Computer Society, 2012.
  * [14] F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi.  Kernelization: Theory of Parameterized Preprocessing.  Cambridge University Press, 2019.
  * [15] F. V. Fomin and M. Pilipczuk.  On width measures and topological problems on semi-complete digraphs.  Journal of Combinatorial Theory, Series B, 138:78–165, 2019.
  * [16] R. Ganian, P. Hliněný, and J. Obdržálek.  Clique-width: When hard does not mean impossible.  In 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, volume 9 of LIPIcs, pages 404–415. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2011.
  * [17] A. C. Giannopoulou, B. M. P. Jansen, D. Lokshtanov, and S. Saurabh.  Uniform kernelization complexity of hitting forbidden minors.  ACM Transactions on Algorithms, 13(3):35:1–35:35, 2017.
  * [18] A. C. Giannopoulou, K. Kawarabayashi, S. Kreutzer, and O. Kwon.  The directed flat wall theorem.  In 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 239–258. SIAM, 2020.
  * [19] A. C. Giannopoulou, K. Kawarabayashi, S. Kreutzer, and O. Kwon.  Directed tangle tree-decompositions and applications.  In 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 377–405. SIAM, 2022.
  * [20] A. C. Giannopoulou, M. Pilipczuk, J.-F. Raymond, D. M. Thilikos, and M. Wrochna.  Linear kernels for edge deletion problems to immersion-closed graph classes.  SIAM Journal on Discrete Mathematics, 35(1):105–151, 2021.
  * [21] M. Karpinski and W. Schudy.  Faster algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament.  In 21st International Symposium on Algorithms and Computation, ISAAC 2010, volume 6506 of Lecture Notes in Computer Science, pages 3–14. Springer, 2010.
  * [22] K. Kawarabayashi and S. Kreutzer.  The directed grid theorem.  In 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 655–664. ACM, 2015.
  * [23] I. Kim and P. D. Seymour.  Tournament minors.  Journal of Combinatorial Theory, Series B, 112:138–153, 2015\.
  * [24] M. Kufleitner.  The height of factorization forests.  In 33rd International Symposium Mathematical Foundations of Computer Science 2008, MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pages 443–454. Springer, 2008.
  * [25] J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, R. Rabinovich, and S. Siebertz.  Rankwidth meets stability.  In 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 2014–2033. SIAM, 2021.
  * [26] J. Nešetřil, R. Rabinovich, P. Ossona de Mendez, and S. Siebertz.  Linear rankwidth meets stability.  In 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1180–1199. SIAM, 2020.
  * [27] A. Ovetsky Fradkin.  Forbidden structures and algorithms in graphs and digraphs.  PhD thesis, Princeton University, 2011.
  * [28] A. Ovetsky Fradkin and P. D. Seymour.  Tournament pathwidth and topological containment.  Journal of Combinatorial Theory, Series B, 103(3):374–384, 2013\.
  * [29] A. Ovetsky Fradkin and P. D. Seymour.  Edge-disjoint paths in digraphs with bounded independence number.  Journal of Combinatorial Theory, Series B, 110:19–46, 2015.
  * [30] J. Raymond.  Hitting minors, subdivisions, and immersions in tournaments.  Discrete Mathematics and Theoretical Computer Science, 20(1), 2018\.
  * [31] I. Simon.  Factorization forests of finite height.  Theoretical Computer Science, 72(1):65–94, 1990.

##  Appendix A Derivation of Lemma 5

Given an alphabet $A$ and a word $w\in A^{\star}$, we say that $w$ can be
_decomposed_ into words $w_{1}$, $w_{2}$, $\ldots$, $w_{\ell}$ if
$w=w_{1}w_{2}\ldots w_{\ell}$. An unranked rooted tree $T$ labeled with
elements of $A^{\star}$ is a _decomposition tree_ of $w$ if:

  * •

the root is labeled with $w$;

  * •

the label of every non-leaf node can be decomposed into labels of all sons of
this node (from left to right);

  * •

the label of every leaf node is an element of $A\cup\\{\varepsilon\\}$ (here
$\varepsilon$ is the empty word).

The _degree_ of a node of a decomposition tree is the number of its sons.
Given a monoid $S$ and a morphism $\alpha\colon A^{\star}\to S$, we say that
decomposition $w=w_{1}w_{2}\ldots w_{\ell}$ satisfies the _$\alpha$
-idempotent rule_ if there exists an idempotent $e\in S$ such that

$\alpha(w_{1})=\alpha(w_{2})=\ldots=\alpha(w_{\ell})=e.$

We define an _$\alpha$ -factorization forest_ for a word $w\in A^{\star}$ as a
decomposition tree of $w$, whose each non-leaf node with degree greater than
$2$ corresponds to an $\alpha$-idempotent rule.

######  Theorem 23 (Factorization Forest theorem of Simon).

Let $S$ be a finite monoid, $A$ be a finite alphabet, and $\alpha\colon
A^{\star}\to S$ be a morphism. Then every $w\in A^{\star}$ has an
$\alpha$-factorization forest of height at most $3|S|$.

The intuition behind Lemma 5 is as follows. If word $w$ is appropriately long
then existence of a constant-height factorization forest forces existence of a
node of large degree (hence corresponding to an idempotent rule) in this
forest.

######  Proof (of lemma 5).

Fix $w\in A^{\star}$ of length at least $\ell^{3|S|}$. By theorem 23 there
exists an $\alpha$-factorization forest $T$ for $w$ of height at most $3|S|$.
Note that if $T$ admits a node of degree at least $\ell$, then the idempotent
rule corresponding to this node provides the desired subword $w^{\prime}$ and
its decomposition into $\ell$ non-empty subwords (in the case of degree
strictly larger than $\ell$, we may concatenate all subwords whose indices are
not smaller than $\ell$ into a single subword).

We will prove that such node always exists. Suppose for the sake of
contradiction that all non-leaf nodes of $T$ have degree strictly smaller than
$\ell$. As $T$ has height at most $3|S|$, the number of leaves of $T$ is
therefore strictly smaller than $\ell^{3|S|}$. On the other hand, each letter
of $w$ has a different corresponding leaf node of $T$, so there are at least
$|w|\geqslant\ell^{3|S|}$ leaf nodes. The contradiction finishes the proof.
$\square$