# On the minimum number of inversions to make a digraph k-(arc-)strong

Julien Duron, Frédéric Havet, Florian Hörsch, Clément Rambaud

► To cite this version:

Julien Duron, Frédéric Havet, Florian Hörsch, Clément Rambaud. On the minimum number of inversions to make a digraph k-(arc-)strong. Journal of Graph Theory, 2025, 111 (2), pp.31-62. 10.1002/jgt.23290 . hal-05470637

HAL Id: hal-05470637

https://inria.hal.science/hal-05470637v1

Submitted on 22 Jan 2026

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_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
On the minimum number of inversions to make a digraph
$k$-(arc-)strong.

Julien Duron¹, Frédéric Havet², Florian Hörsch³, and Clément Rambaud²,⁴

¹École normale supérieure de Lyon, LIP, France

²Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France

³CISPA Saarbrücken, Germany, florian.hoersch@cispa.de

⁴DIENS, École normale supérieure, CNRS, PSL University, Paris, France

**Abstract**

The inversion of a set X of vertices in a digraph D consists of reversing the direction of all arcs of D⟨X⟩. We study $sinv_k(D)$ (resp. $sinv_k(D)$) which is (for some positive integer $k$) the minimum number of inversions needed to transform D into a $k$-arc-strong (resp. $k$-strong) digraph or $+\infty$ if no such transformation exists. Note that $sinv'_k(D) \le sinv_k(D)$. We set $sinv'_k(n) = \max\{sinv'_k(D) | D$ is a $2k$-edge-connected digraph of order $n\}$. We show the following results where $k$ is a fixed integer for $(i) - (vi)$:

(i) $\frac{1}{2}\log(n-k+1) \le sinv'_k(n) \le \log n + 4k - 3$ for every $n \ge k$;

(ii) for any fixed positive integer $t$, deciding whether a given oriented graph $D$ with $sinv'_k(D) < +\infty$ satisfies $sinv'_k(D) \le t$ is NP-complete;

(iii) for any fixed positive integer $t$, deciding whether a given oriented graph $D$ with $sinv_k(D) < +\infty$ satisfies $sinv_k(D) \le t$ is NP-complete;

(iv) if $T$ is a tournament of order at least $2k+1$, then $sinv_k(T) \le 2k$, and $sinv'_k(T) \le \frac{4}{3}k + o(k)$;

(v) $\frac{1}{2}\log(2k+1) \le sinv'_k(T)$ for some tournament $T$ of order $2k+1$;

(vi) if $T$ is a tournament of order at least $19k-2$ (resp. $11k-2$), then $sinv_k(T) \le 1$ (resp. $sinv_k(T) \le 3$);

(vii) for every $\epsilon > 0$, there exists $C$ such that for every positive integer $k$ and every tournament $T$ on at least $2k+1+\epsilon k$ vertices, we have $sinv_k(T) \le C$.

**Keywords:** inversion; tournament; $k$-strong; $k$-arc-strong.

# 1 Introduction

Notation not given below is consistent with [BJG09]. For some positive integer $k$, we denote by $[k]$ the set $\{1, 2, \dots, k\}$, and we use $\log$ to refer to the logarithm to the base 2. A **digraph** may contain **digons**, those are pairs of arcs in opposite direction between the same two vertices, but no parallel arcs or loops while an **oriented graph** is a digraph without digons. A **multigraph** may contain parallel edges, but no loops, while a multigraph with no parallel edges is called a **graph**. When the graph or digraph is clear from the context, we use $n$ for its number of vertices.

A **feedback arc set** in a digraph is a set of arcs whose reversal results in an acyclic digraph. Considering an arbitrary ordering $(v_1, \dots, v_n)$ of the vertices of a digraph $D$ and a smallest set among the one containing the forward arcs (i.e. arcs $v_i v_j$ with $i < j$) and the one containing the backward arcs (i.e. arcs $v_i v_j$ with $i > j$), one gets that $D$ has a feedback arc set of size at most $|A(D)|/2$. In particular, every oriented graph of order $n$ has a feedback arc set of size at most $\frac{1}{2}\binom{n}{2}$. This bound is almost tight : de la Vega [Fer83] showed that there are infinitely many oriented graphs with no feedback arc set of size less than $\frac{1}{2}\binom{n}{2} - 1.73n^{3/2}$. Finding a minimum cardinality feedback arc set of a given digraph is an important and heavily studied algorithmic problem. It is one of the first problems shown to
be NP-hard listed by Karp in [Kar72]. Furthermore, it is hard to approximate. For arbitrary digraphs, the best known ratio is $O(\log n \log \log n)$ due to Even et al. [ENSS95]. It was proven to be APX-hard by Kann [Kan92]. This was later strengthened by Dinur and Safra who showed that, unless P is equal to NP, it cannot be approximated within a factor of better than about 1.36 [DS05]. For **tournaments**, which are orientations of complete graphs, the problem was proven to remain NP-complete, independently by Alon [Alo06] and Charbit, Thomassé, and Yeo [CTY07]. On the other hand, a polynomial-time approximation scheme was provided by Kenyon-Mathieu and Schudy [KMS07], improving on an earlier 3-approximation algorithm by Ailon, Charikar, and Newman [ACN08].

To make a digraph $D$ acyclic, one can use a different operation from arc reversal, called inversion. The **inversion** of a set $X$ of vertices consists in reversing the direction of all arcs of $D\langle X \rangle$. We say that we **invert** $X$ in $D$. The resulting digraph is denoted by $\text{Inv}(D; X)$. If $(X_i)_{i \in I}$ is a family of subsets of $V(D)$, then $\text{Inv}(D; (X_i)_{i \in I})$ is the digraph obtained after inverting the $X_i$ one after another. Observe that this is independent of the order in which we invert the $X_i$: $\text{Inv}(D; (X_i)_{i \in I})$ is obtained from $D$ by reversing exactly those arcs for which an odd number of the $X_i$ contain its two endvertices. A **decycling family** of a digraph $D$ is a family $(X_i)_{i \in I}$ of subsets of $V(D)$ such that $\text{Inv}(D; (X_i)_{i \in I})$ is acyclic. A digraph admits a decycling family if and only if it does not contain any digon. Indeed, observe that an inversion operation changes the orientation of either none or both of the arcs in a digon. Hence, a digraph containing a digon cannot be made acyclic by inversions. Conversely, in an oriented graph, the pairs of endvertices of the arcs of a minimal feedback arc-set form a decycling family. The **inversion number** of an oriented graph $D$, denoted by $\text{inv}(D)$, is the minimum number of inversions needed to transform $D$ into an acyclic oriented graph, that is, the minimum cardinality of a decycling family. This parameter was first introduced by Belkhechine et al. in [BBBP10] and then studied in several papers [BJdSH22, TSKP22, AHH$^+$25, APS$^+$24]. In particular, Belkhechine et al. proved in [BBBP10] that, for any fixed integer $k$, deciding whether a given tournament has inversion number at most $k$ is polynomial-time solvable. In contrast, Bang-Jensen et al. [BJdSH22] proved that deciding whether a given digraph has inversion number 1 is NP-complete. This was generalized by Alon et al. [APS$^+$24]: for any fixed positive integer $k$, deciding whether a given digraph has inversion number at most $k$ is NP-complete. Further, the extremal question of determining the maximum integer $\text{inv}(n)$ of the inversion numbers of all oriented graphs on $n$ vertices has been investigated. Independently, Aubian et al. [AHH$^+$25] and Alon et al. [APS$^+$24] proved $n - 2\sqrt{n \log n} \le \text{inv}(n) \le n - \lfloor \log(n+1) \rfloor$.

The main purpose of this article is to study the possibilities of applying the inversion operation to obtain a different objective than the resulting digraph being acyclic. Instead of making a digraph acyclic, we are interested in making it satisfy a prescribed connectivity property. A digraph $D$ is **strongly connected** or simply **strong** (resp. **k-arc-strong** for some positive integer $k$), if for any partition $(V_1, V_2)$ of $V(D)$ with $V_1, V_2 \neq \emptyset$ there is an arc (resp. at least $k$ arcs) with tail in $V_1$ and head in $V_2$. Similarly, a multigraph $G$ is **connected** (resp. **k-edge-connected** for some positive integer $k$), if for any partition $(V_1, V_2)$ of $V(G)$ with $V_1, V_2 \neq \emptyset$ there is an edge (resp. at least $k$ edges) with one endvertex in $V_1$ and one endvertex in $V_2$. We further say that $G$ is **k-connected** if $|V(G)| \ge k + 1$ and $G-S$ is connected for every $S \subseteq V(G)$ with $|S| \le k - 1$. For a given digraph $D$, we denote by $\text{UG}(D)$ the undirected multigraph that we obtain by suppressing the orientations of the arcs. A digraph is **k-connected** (resp. **k-edge-connected**) if its underlying multigraph $\text{UG}(D)$ is. Clearly, a digraph $D$ can be made $k$-arc-strong by reversing some arcs if and only if the edges of $\text{UG}(D)$ can be oriented such that the resulting digraph is $k$-arc-strong. Robbins' Theorem [Rob39] asserts that a graph admits a strong orientation if and only if it is 2-edge-connected, and more generally, Nash-Williams' weak orientation theorem [NW60] asserts that a graph admits a $k$-arc-strong orientation if and only if it is $2k$-edge-connected.

We can hence decide in polynomial time whether a given digraph can be transformed into a $k$-arc-strong digraph via arc reversals, applying standard flow algorithms to its underlying graph. Furthermore, it is well-known that, if this is the case, then, by reducing to a minimum-cost submodular flow problem, one can determine, in polynomial time, a minimum set of arcs in $D$ whose reversal gives a $k$-arc-strong digraph, see Section 8.8.4 of [BJG09] for details. It is easy to see that the number of necessary arc reversals to make a $2k$-edge-connected digraph $D$ $k$-arc-strong cannot be bounded by a function depending only on $k$. For example, one can consider digraphs that contain a number of sinks which is linear in the number of vertices of the graph, where a **sink** is a vertex with no outgoing arc. However, Bang-Jensen and Yeo [BJY04] proved that for tournaments, the size of such a set is always bounded by a quadratic
function of $k$. Precisely, they showed that every tournament on at least $2k + 1$ vertices can be made $k$-arc-strong by reversing at most $\frac{1}{2}k(k+1)$ arcs. This result is tight for the transitive tournaments.

We are interested in the problem of using inversions to make a digraph $k$-arc-strong. A $k$-arc-strengthening family of a digraph $D$ is a family $(X_i)_{i \in I}$ of subsets of $V(D)$ such that $\text{Inv}(D; (X_i)_{i \in I})$ is $k$-arc-strong. The $k$-arc-strong inversion number of a digraph $D$, denoted by $\text{sinv}'_k(D)$, is the minimum number of inversions needed to transform $D$ into a $k$-arc-strong digraph, that is, the minimum cardinality of a $k$-arc-strengthening family. We first deal with the extremal behaviour of $\text{sinv}'_k(D)$ for some fixed $k$, that is, we deal with the question of finding the maximum number of necessary inversions to make a $2k$-edge-connected digraph on a fixed number of vertices $k$-arc-strong. To this end, we define $\text{sinv}'_k(n) = \max\{\text{sinv}'_k(D) | D$ is a $2k$-edge-connected digraph of order $n\}$. It turns out that $\text{sinv}'_k(n)$ is an unbounded, but slowly growing, function. We are able to determine $\text{sinv}'_k(n)$ up to a constant multiplicative factor of roughly 2. More precisely, we show the following result:

**Theorem 1.1.** For any pair of positive integers $k, n$ with $n \ge k + 2$, we have

$$ \frac{1}{2} \log(n - k + 1) \le \text{sinv}'_k(n) \le \log n + 4k - 3. $$

Observe that the condition $n \ge k + 2$ is necessary for $\text{sinv}'_k(n)$ to be well-defined.

Next, we consider the algorithmic complexity of computing $\text{sinv}'_k(D)$ for a given digraph $D$ and a fixed integer $k$. We show that this problem is NP-hard. More precisely, we show the following, slightly stronger, result.

**Theorem 1.2.** Deciding whether a given oriented graph $D$ satisfies $\text{sinv}'_k(D) \le t$ is NP-complete for all pairs of positive integers $k$ and $t$.

Furthermore, we show that there is little hope to approximate $\text{sinv}'_k(D)$ in polynomial time.

**Theorem 1.3.** Unless $P=\text{NP}$, there do not exist any integers $c_1, c_2, k$ with $1 \le c_1 \le c_2$ and $k \ge 1$ for which there exists a polynomial-time algorithm that can assert whether a given $2k$-edge-connected oriented graph can be made $k$-arc-strong by at most $c_1$ inversions or cannot be made $k$-arc-strong by at most $c_2$ inversions.

As a related problem, one may also want to make a digraph $k$-strong. A digraph $D$ is $k$-strong if $|V(D)| \ge k+1$ and for any set $S \subseteq V(D)$ with fewer than $k$ vertices, $D-S$ is strong. A digraph which can be made $k$-strong by reversing arcs is $k$-strengthenable. The $1$-strengthenable digraphs are the $2$-edge-connected ones, because being $1$-strong is the same as being strong or $1$-arc-strong. Thomassen [Tho15] proved that the $2$-strengthenable digraphs are the $4$-edge-connected digraphs $D$ such that $D-v$ is $2$-edge-connected for every vertex $v \in V(D)$. On the other hand, it is NP-hard to compute the minimum number of arc reversals needed to make a given digraph $2$-strong, as shown by Bang-Jensen et al. in [BJHK23]. Furthermore, in contrast to the analogous problem for $k$-arc-strengthenable digraphs, for $k \ge 3$, it is NP-complete to decide whether a digraph is $k$-strengthenable. Indeed, Durand de Gevigney [Dur20] proved that it is NP-complete to decide whether an undirected graph has a $k$-strong orientation for any $k \ge 3$.

It is also natural to use inversions to make a digraph $k$-strong. A $k$-strengthening family of a digraph $D$ is a family $(X_i)_{i \in I}$ of subsets of $V(D)$ such that $\text{Inv}(D; (X_i)_{i \in I})$ is $k$-strong. The $k$-strong inversion number of a $k$-strengthenable digraph $D$, denoted by $\text{sinv}_k(D)$, is the minimum number of inversions needed to transform $D$ into a $k$-strong digraph, that is, the minimum cardinality of a $k$-strengthening family. It follows directly from the fact that every $k$-strong digraph is $k$-arc-strong that $\text{sinv}_k(D) \ge \text{sinv}'_k(D)$ holds for every $k$-strengthenable digraph $D$. In the light of the complexity result of Durand de Gevigney [Dur20], it seems difficult to obtain an extremal result in the shape of Theorem 1.1 for $k$-strong digraphs. However, we give the following complexity results which are the natural analogues of Theorems 1.2 and 1.3.

**Theorem 1.4.** Deciding whether a given $k$-strengthenable oriented graph $D$ satisfies $\text{sinv}_k(D) \le t$ is NP-complete for all pairs of positive integers $k$ and $t$.
**Theorem 1.5.** Unless $P=NP$, there do not exist any integers $c_1, c_2, k$ with $1 \le c_1 \le c_2$ and $k \ge 1$ for which there exists a polynomial-time algorithm that can assert whether a given $k$-strengthenable oriented graph can be made $k$-strong by at most $c_1$ inversions or cannot be made $k$-strong by at most $c_2$ inversions.

In the remainder of this article, we focus on a particular kind of oriented graphs, namely tournaments. No tournament on fewer than $2k+1$ vertices is $k$-arc-strong, and thus no tournament on fewer than $2k+1$ vertices is $k$-arc-strengthenable. On the other hand, it is not hard to show that every tournament of order at least $2k+1$ is $k$-strengthenable. Moreover, every tournament on at least $2k+1$ vertices can be made $k$-strong by reversing the orientation of at most $\frac{1}{4}(4k-2)(4k-3)$ arcs, see e.g. [BJG09], p. 379.

Further, the following improvement was conjectured by Bang-Jensen. See [BJG09].

**Conjecture 1.6** (Bang-Jensen, 1994). Every tournament on at least $2k+1$ vertices can be made $k$-strong by reversing at most $\frac{1}{2}k(k+1)$ arcs.

This would be tight as shown by the transitive tournaments. Bang-Jensen, Johansen, and Yeo [BJJY23] proved a weaker version of this conjecture where $2k+1$ is replaced by $3k-1$.

It is then natural to ask whether or not we can make a tournament $k$-strong or $k$-arc-strong using significantly fewer than $\frac{1}{2}k(k+1)$ inversions. This leads us to consider $M_k = \max\{\sinv_k(T) \mid T \text{ tournament of order at least } 2k+1\}$ and $M'_k = \max\{\sinv'_k(T) \mid T \text{ tournament of order at least } 2k+1\}$. We show that these numbers are indeed significantly smaller than $\frac{1}{2}k(k+1)$, but cannot be bounded by a constant independent of $k$. More precisely, we show the following result.

**Theorem 1.7.** For every sufficiently large integer $k$, we have $\frac{1}{2}\log(2k+1) \le M'_k \le M_k \le 2k$.

The lower bound is obtained by a counting argument.

We also prove that $M_1 = M'_1 = 1$ and $M_2 = M'_2 = 2$ showing that the upper bound is not tight for $k=1, 2$. We also prove a better upper for $M'_k$ for large values of $k$.

**Theorem 1.8.** $M'_k \le \frac{4}{3}k + o(k)$.

However, we believe that this bound, as well as the others, is not tight.

**Problem 1.9.** Find better bounds on $M_k$ and $M'_k$.

We further study the question of how the parameters $\sinv_k$ and $\sinv'_k$ behave when fixing $k$ and considering tournaments whose size is significantly larger than $2k+1$. As a first result, we prove that every sufficiently large tournament can be made $k$-strong (and thus also $k$-arc-strong) in one inversion.

**Theorem 1.10.** Let $n$ and $k$ be positive integers with $n \ge 19k-2$. If $T$ is a tournament on $n$ vertices, then $\sinv'_k(T) \le \sinv_k(T) \le 1$.

In fact, it is relatively straightforward to see that $\sinv_k(T) \le 1$ for tournaments $T$ of even larger order relative to $k$ (see Theorem 6.1).

This leads us to the study of the functions $m_k(n) = \max\{\sinv_k(T) \mid T \text{ tournament of order } n\}$ and $m'_k(n) = \max\{\sinv'_k(T) \mid T \text{ tournament of order } n\}$ for all $n \ge 2k+1$. We believe that $m_k$ and $m'_k$ have the following monotonic behaviour.

**Conjecture 1.11.** Let $k$ be a positive integer.

(i) $m_k$ and $m'_k$ are non-increasing mappings.

(ii) $M_k = m_k(2k+1)$ and $M'_k = m'_k(2k+1)$.

Note that (i) implies (ii). This conjecture is motivated by the fact that one can easily prove that $m_k$ and $m'_k$ are non-increasing for $n > 4k-2$. See Section 7. Therefore, in order to approach Problem 1.9, it is sufficient to consider tournaments whose order is in the range from $2k+1$ to $4k-2$.

Theorem 1.10 implies that, for every pair of positive integers $k$ and $i$, there is a smallest integer $N_k(i)$ such that $m_k(n) \le i$ for all $n \ge N_k(i)$. Similarly, for every pair of positive integers $k$ and $i$, there is a smallest integer $N'_k(i)$ such that $m'_k(n) \le i$ for all $n \ge N'_k(i)$. Since $m'_k(n) \le m_k(n)$ for all $k$ and $n$, we have $N'_k(i) \le N_k(i)$ for all $k$ and $i$. It is natural to ask the following questions.
**Problem 1.12.** Let $k, i, n$ be positive integers, and let $T$ be a tournament on $n$ vertices.

What is the minimum integer $N_k(i)$ such that $\text{sinv}_k(T) \le i$ if $n \ge N_k(i)$?

What is the minimum integer $N'_k(i)$ such that $\text{sinv}'_k(T) \le i$ if $n \ge N'_k(i)$?

Theorem 1.10 states $N'_k(1) \le N_k(1) \le 19k - 2$. Since the transitive tournament on $3k-1$ vertices satisfies $\text{sinv}'_k(TT_{3k+1}) = \text{sinv}_k(TT_{3k+1}) = 2$ (Theorem 5.9), we have $N_k(1) \ge N'_k(1) \ge 3k$. We further establish the following better lower bounds for $N_k(1)$ and $N'_k(1)$ by giving simple examples.

**Proposition 1.13.** For any positive integer $k$, we have $N_k(1) \ge 5k - 2$ and $N'_k(1) \ge 4k - 2$.

We further show that a significantly smaller tournament can still be dealt by three inversions.

**Theorem 1.14.** For any positive integer $k$, we have $N'_k(3) \le N_k(3) \le 11k - 2$.

Finally, using probabilistic methods, we prove that every tournament that is a constant factor bigger than $2k$ can be made $k$-strong by a constant number of inversions. More precisely, we prove the following result.

**Theorem 1.15.** There exists a function $f: \mathbb{R}_>0 \to \mathbb{N}$ such that for every $\epsilon > 0$ and every positive integer $k$, if $T$ is an $n$-vertex tournament with $n \ge 2k + 1 + \epsilon k$, then $\text{sinv}_k(T) \le f(\epsilon)$.

The fact that $m_k(n) = 1$ for $n$ sufficiently large implies that the set $\mathcal{F}_k$ of tournaments $T$ such that $\text{sinv}_k(T) > 1$ is finite. This implies that computing $\text{sinv}_k$ and $\text{sinv}'_k$ for fixed $k$ can be done in polynomial time for tournaments.

**Corollary 1.16.** Let $k$ be a positive integer. We can compute $\text{sinv}_k(T)$ (resp. $\text{sinv}'_k(T)$) for a given tournament $T$ on $n$ vertices in $O(n^{7/2})$ time (resp. $O(n^2)$ time).

*Proof.* We first check in constant time, whether $T$ is in $\mathcal{F}_k$. If yes, then we can return $\text{sinv}_k(T)$ and $\text{sinv}'_k(T)$ that may be stored in some precomputed table. If not, then $\text{sinv}'_k(T) \le \text{sinv}_k(T) \le 1$. We then check in $O(n^{7/2})$ time using algorithms due to Even and Tarjan [ET75] or Galil [Gal80] based on flow (resp. $O(n^2)$ time using Mansour and Schieber's [MS89] algorithm based on flow or Gabow's algorithm [Gab91] based on matroids) whether $T$ is $k$-strong (resp. $k$-arc-strong) to determine whether $\text{sinv}_k(T)$ (resp. $\text{sinv}'_k(T)$) is equal to 0 or 1. $\square$

This article is structured as follows. We give some notation and a collection of preliminary results in Section 2. In Section 3, we prove Theorem 1.1. In Section 4, we prove the complexity results, namely Theorems 1.2 to 1.5. The results on tournaments are contained in Section 5, in which we prove Theorem 1.7, and in Section 6, in which we prove Theorems 6.1, 1.10, 1.14 and 1.15 and Proposition 1.13.

# 2 Preliminaries

In Section 2.1, we introduce some formal notation and in Section 2.2, we give a collection of auxiliary results.

## 2.1 Notation

A **mixed graph** $G = (V, E, A)$ is a triple consisting of a set $V$ of elements called **vertices**, a set $E$ of unordered pairs of vertices called **edges**, and a set $A$ of ordered pairs of vertices called **arcs**. Hence a multigraph can be seen as a mixed graph whose arc set is empty, while a digraph can be seen as a mixed graph whose edge set is empty and that does not contain parallel arcs. Given a mixed graph $G$, its vertex set is denoted by $V(G)$, its edge set is denoted by $E(G)$ and its arc set by $A(G)$. The **underlying graph** $\text{UG}(G)$ of a mixed graph $G$ is the undirected multigraph that we obtain by suppressing the orientations of the arcs (i.e. replacing each arc by an edge between its two endvertices). An **orientation** of a mixed graph $G$ is a digraph obtained by giving an orientation to every edge, i.e. replacing each edge by one of the two arcs between its endvertices.

Let $S, S'$ be disjoint sets of vertices in a mixed graph $G$. We denote by $\delta_G(S, S')$ the set of edges of $E(G)$ with exactly one endvertex in $S$ and one endvertex in $S'$. We use $\delta_G(S)$ for $\delta_G(S, V(G) \setminus S)$. We also denote by $\delta_G^+(S, S')$ (resp. $\delta_G^-(S, S')$) the set of arcs in $A(G)$ with tail (resp. head) in $S$ and head (resp. tail) in $S'$.
tail) in $S'$. Again, we use $\delta_G^+(S)$ (resp. $\delta_G^-(S)$) for $\delta_G^+(S, V(G) \setminus S)$ (resp. $\delta_G^-(S, V(G) \setminus S)$). The **degree** (resp. **out-degree**, **in-degree**) of $S$ in $G$ is $d_G(S) = |\delta_G(S)|$ (resp. $d_G^+(S) = |\delta_G^+(S)|$, $d_G^-(S) = |\delta_G^-(S)|$). We further use $d_G(S, S') = |\delta_G(S, S')|$, $d_G^+(S, S') = |\delta_G^+(S, S')|$, and $d_G^-(S, S') = |\delta_G^-(S, S')|$. Let $N_G(S)$ (resp. $N_G^+(S)$, $N_G^-(S)$) denote the set of vertices in $V(G) \setminus S$ that are incident to at least one edge (arc) in $\delta_G(S)$ (resp. $\delta_G^+(S)$, $\delta_G^-(S)$). The **degree** (resp. **out-degree**, **in-degree**) of a vertex $v$ in $G$ is $d_G(v) = d_G(\{v\})$ (resp. $d_G^+(v) = d_G^+(\{v\})$, $d_G^-(v) = d_G^-(\{v\})$). For simplicity, when the mixed graph is clear from the context, the subscript $G$ is omitted.

Let $D$ be a digraph. A **sink** (resp. **source**) in a digraph is a vertex with out-degree 0 (resp. in-degree 0). We say that $D$ is **eulerian** if $d_D^-(v) = d_D^+(v)$ holds for every vertex $v$. Let $A$ and $B$ be two disjoint sets in $D$. If $ab$ is an arc for all pairs $(a, b)$ in $A \times B$, then we write $A \Rightarrow B$.

Let $u, v$ be two distinct vertices in $D$. The **strong-connectivity** from $u$ to $v$ in $D$, denoted by $\kappa_D(u, v)$, is the maximal number $\alpha$ such that $D - X$ contains a $(u, v)$-path for every $X \subseteq V(D) \setminus \{u, v\}$ with $|X| \le \alpha - 1$. For some $S \subseteq V(D)$ and positive integer $k$, we say that $S$ is **k-strong** in $D$ if $\kappa_D(u, v) \ge k$ for all $u, v \in S$.

## 2.2 Preliminary results

We use several times without explicitly mentioning it that for every positive integer $k$, there is a $k$-strong tournament on $2k + 1$ vertices. One example for such a tournament is the socalled rotative tournament whose vertex set is $[2k + 1]$ and where an arc is oriented from $i$ to $j$ if $i - j \in [k](\text{mod } 2k + 1)$.

We need the following simple result that allows us to extend a set which is $k$-strong in a digraph.

**Proposition 2.1.** Let $D$ be a digraph, let $S$ be a $k$-strong set in $D$ and let $v \in V(D) \setminus S$. If $v$ has at least $k$ in-neighbours in $S$ and at least $k$ out-neighbours in $S$, then $S \cup \{v\}$ is $k$-strong in $D$.

*Proof.* Suppose for the sake of a contradiction that there is a set $X \subseteq V(D)$ of size at most $k - 1$ and a pair $(s, t)$ of vertices in $(S \cup \{v\}) \setminus X$ such that there is no $(s, t)$-path in $D - X$. If $s, t \in S$, then this contradicts the fact that $S$ is $k$-strong in $D$. Thus exactly one of $s$ and $t$ is $v$. Without loss of generality, suppose $s \in S$ and $t = v$. Since $|N^-(v) \cap S| \ge k$, $v$ has an in-neighbour $t_0 \in S - X$, and as $S$ is $k$-strong in $D$, there is an $(s, t_0)$-path in $D - X$, and so there is an $(s, t)$-path in $D - X$, a contradiction. $\square$

The well-known following result is helpful for applying Proposition 2.1. It follows directly from Proposition 2.2.2 of [BJH18].

**Proposition 2.2.** Let $T$ be a tournament on at least $4k - 1$ vertices for some positive integer $k$. Then there exists some $v \in V(T)$ with $\min\{d_T^+(v), d_T^-(v)\} \ge k$.

We need the following simple characterization of $k$-arc-strong tournaments of order $2k + 1$.

**Proposition 2.3 (Folklore).** A tournament on $2k + 1$ vertices is $k$-arc-strong if and only if it is **eulerian**.

For sake of completeness, we give a short proof of this fact.

*Proof.* Let $T$ be a tournament on $2k + 1$ vertices. If $T$ is $k$-arc-strong, then every vertex $u$ in $T$ has in- and out-degree at least $k$, but since $d_T^+(u) + d_T^-(u) = 2k$, we deduce that $d_T^+(u) = d_T^-(u)$ and so $T$ is **eulerian**. Reciprocally, if $T$ is **eulerian**, then $d_T^+(u) = d_T^-(u) = k$ for every vertex $u$ of $T$. Now consider a partition $(V_1, V_2)$ of $V(T)$ where $V_1$ and $V_2$ are non-empty. Then the number of arcs from $V_1$ to $V_2$ is at least

$$ \sum_{v \in V_1} d_T^+(v) - \left( \frac{|V_1|}{2} \right) \ge |V_1| \left( k - \frac{|V_1| - 1}{2} \right) \\ \ge k $$

and so $T$ is $k$-arc-strong. $\square$

We need the following orientation property of mixed graphs that can be found in [FF10].

**Proposition 2.4.** Let $H$ be a mixed graph whose underlying graph is **eulerian**. Then $H$ has an **eulerian** orientation if and only if $d_H(S) \ge d_H^+(S) - d_H^-(S)$ for all $S \subseteq V(H)$.
Finally, we state two basic tools from probability theory.

**Proposition 2.5 (Union Bound).** Let $E_1, \dots, E_\ell$ be a set of events in a random experiment and E the event that at least one of $E_1, \dots, E_\ell$ occurs. Then $\Pr(E) \le \sum_{i=1}^\ell \Pr(E_i)$.

**Proposition 2.6 (Chernoff’s Bound).** If X is a random variable following a binomial law with parameters $p \in [0, 1]$ and $n \ge 0$, then for every $\epsilon \in [0, 1]$

$$ \Pr[X \le (1 - \epsilon)pn] \le \exp\left(-\frac{\epsilon^2}{2}pn\right). $$

We refer the reader to [MR02, Part II, Section 5] for an introduction to the probabilistic method, including proofs of Propositions 2.5 and 2.6.

# 3 Bounds on $\sinv'_k(n)$

This section is dedicated to the extremal results we have on the k-arc-strong inversion number. In particular, we prove Theorem 1.1, which we restate.

**Theorem 1.1.** For any pair of positive integers $k, n$ with $n \ge k + 2$, we have

$$ \frac{1}{2}\log(n - k + 1) \le \sinv'_k(n) \le \log n + 4k - 3. $$

First, we prove the upper bound. Let $d$ be a positive integer. A multigraph $G$ is said to be $d$-degenerate if every submultigraph of $G$ has a vertex of degree at most $d$. Every $d$-degenerate graph admits a $d$-degenerate ordering, that is an ordering $(v_1, \dots, v_n)$ of the vertices of $G$ such that every vertex has at most $d$ neighbours with lower indices.

We shall need the following proposition, which, as observed in [BJHK23], is a direct consequence of Corollary 2 in [KS06].

**Proposition 3.1.** Let $G$ be a multigraph that has a $k$-arc-connected orientation for some positive integer $k$ and let $(e_1, f_1), \dots, (e_t, f_t)$ be a collection of pairwise disjoint pairs of parallel edges in $G$. Then $G$ has a $k$-arc-connected orientation in which $e_i$ and $f_i$ are oriented in opposite directions for $i = 1, \dots, t$.

We use the following result which has recently been proved in a related paper by the second, third, and fourth author [HHR24].

**Theorem 3.2 ([HHR24])**. Let $G$ be an $n$-vertex $d$-degenerate graph. For any two orientations $\vec{G}_1, \vec{G}_2$ of $G$, one can transform $\vec{G}_1$ into $\vec{G}_2$ by inverting at most $\log n + 2d - 1$ sets.

Let $G$ be a multigraph and let $S$ be a subset of $V(G)$ with $\emptyset \subsetneq S \subsetneq V(G)$. The $S$-cut in $G$, denoted by $\delta_G(S)$, is the set of all the edges $uv$ in $G$ with $u \in S$ and $v \notin S$. A cut in $G$ is an $S$-cut for some non-trivial set $S$ (that is $S \neq \emptyset$ and $S \neq V(G)$). Note that a multigraph is $k$-edge-connected if and only if there is no cut in $G$ of size at most $k-1$. For all pair of distinct vertices $u, v$ in $G$, a $(u, v)$-cut in $G$ is a cut $\delta_G(S)$ of $G$ with $u \in S$ and $v \notin S$. A multigraph $G$ is **minimally $k$-edge-connected** if it is $k$-edge-connected and $G \setminus e$ is not $k$-edge-connected for any edge $e \in E(G)$. Equivalently, for every edge $uv$, there is a cut of size exactly $k$ containing $uv$.

The next result gives an upper bound on the number of edges in a multigraph where each edge is contained in a small cut.

**Lemma 3.3.** Let $n$ and $k$ be positive integers with $n \ge k + 1$, and let $G$ be an $n$-vertex multigraph. If for every edge $uv \in E(G)$ there is a $(u, v)$-cut of size at most $k$ in $G$, then $G$ has at most $k(n-1)$ edges.

*Proof.* Let $F_1, \dots, F_k$ be a set of $k$ edge-disjoint spanning forests in $G$ such that $\sum_{i=1}^k |E(F_i)|$ is maximized. If there is an edge $e = uv \in E(G) \setminus \cup_{i=1}^k E(F_i)$, then, as $e$ cannot be added to $E(F_i)$, we obtain that $F_i$ contains a $(u, v)$-path for $i \in [k]$. Hence $G \setminus e$ does have any $(u, v)$-cut whose size is smaller than $k$, a contradiction. This yields $|E(G)| = \sum_{i=1}^k |E(F_i)| \le k(n-1)$. $\square$

We are now ready to prove the upper bound in Theorem 1.1.
**Lemma 3.4.** Let $n$ and $k$ be positive integers with $n \ge k+1$. Then, for every 2k-edge-connected n-vertex digraph $D$, $\sin v'_{k}(D) \le \log n + 4k - 3$.

*Proof.* Without loss of generality, suppose that $D$ is minimally 2k-edge-connected. Then by Lemma 3.3, every subgraph of $UG(D)$ has average degree smaller than $2k$. This implies that $UG(D)$ is $(2k-1)$-degenerate. Let $D_0$ be the subdigraph obtained from $D$ by removing all digons. By Proposition 3.1, there is an orientation $D'_0$ of $UG(D_0)$ such that together with the digons of $D$, this digraph is $k$-arc-strong. By Theorem 3.2, there is a set $\mathcal{X}$ of at most $\log n + 2(2k-1) - 1$ inversions transforming $D_0$ into $D'_0$. Since digons are preserved by inversions, we deduce that $\mathrm{Inv}(D; \mathcal{X})$ is $k$-arc-strong, and so $\sin v'_{k}(D) \le \log n + 4k - 3$. $\square$

In order to prove the lower bound in Theorem 1.1, we first need the following intermediate result.

**Lemma 3.5.** For every positive integer $t$, there exists a 2-edge-connected digraph $D$ on $2^{t-1}+1+(\binom{2^{t-1}+1}{2})$ vertices with a specified vertex $s$ such that each digraph obtained from $D$ by applying at most $t-1$ inversions contains a sink or source distinct from $s$.

*Proof.* Let first $S$ be a set of $2^{t-1}+1$ vertices. Now we obtain the digraph $D$ by adding a vertex $v_{\{s_1,s_2\}}$ as well as the arcs $s_1v_{\{s_1,s_2\}}$ and $s_2v_{\{s_1,s_2\}}$ for every $\{s_1,s_2\} \subseteq S$. It is easy to see that $D$ is 2-edge-connected and that the number of vertices of $D$ is $2^{t-1} + 1 + (\binom{2^{t-1}+1}{2})$. Now let $D'$ be obtained from $D$ by inverting a collection of $t-1$ sets $X_1, \dots, X_{t-1} \subseteq V(D)$. As $|S| = 2^{t-1} + 1$, there exist distinct vertices $s_1, s_2 \in S$ such that for $i=1, \dots, t-1$, we have either $\{s_1, s_2\} \subseteq X_i$ or $\{s_1, s_2\} \cap X_i = \emptyset$. Then in each of the $t-1$ inversions, either both or none of the arcs incident to $v_{\{s_1,s_2\}}$ are inverted. We obtain that $v_{\{s_1,s_2\}}$ is either a source or a sink in $D'$. The statement hence follows for an arbitrary $s \in S$. $\square$

The next lemma gives a construction of graphs of arbitrary size that need a significant amount of inversions to become strong.

**Lemma 3.6.** For every positive integer $n \ge 3$, there is a 2-edge-connected digraph $D$ on $n$ vertices such that any digraph obtained from $D$ by applying at most $\frac{1}{2}[\log n] - 1$ inversions contains a sink or a source.

*Proof.* For $n=3,4$, the statement is clearly true. We may therefore suppose that $n \ge 5$ and hence $\frac{3}{2\sqrt{2\sqrt{n}}} \le \frac{1}{2}$. Let $n' = 2^{\frac{1}{2}[\log n]-1} + 1 + (\binom{2^{\frac{1}{2}[\log n]-1}+1}{2})$. By Lemma 3.5, there is a digraph $D'$ on $n'$ vertices together with a vertex $s \in V(D')$ such that every graph obtained from $D'$ by applying at most $\frac{1}{2}[\log n] - 1$ inversions contains a sink or source distinct from $s$.

Next observe that

$$
\begin{align*}
n' &= 2^{\frac{1}{2}[\log n]-1} + 1 + \binom{2^{\frac{1}{2}[\log n]-1} + 1}{2} \\
&= 2^{\frac{1}{2}[\log n]-1} + 1 + \frac{1}{2}(2^{\frac{1}{2}[\log n]-1} + 1)2^{\frac{1}{2}[\log n]-1} \\
&\le 2^{\frac{1}{2}\log n - \frac{1}{2}} + 1 + \frac{1}{2}(2^{\frac{1}{2}\log n - \frac{1}{2}} + 1)2^{\frac{1}{2}\log n - \frac{1}{2}} \\
&= \frac{\sqrt{n}}{\sqrt{2}} + 1 + \frac{1}{2}\left(\frac{\sqrt{n}}{\sqrt{2}} + 1\right)\frac{\sqrt{n}}{\sqrt{2}} \\
&= \frac{n}{4} + \frac{3}{2\sqrt{2}}\sqrt{n} + 1 \\
&= \frac{n}{4} + \frac{3}{2\sqrt{2}\sqrt{n}}n + 1 \\
&\le \frac{n}{4} + \frac{n}{2} + \frac{n}{4} \\
&= n.
\end{align*}
$$

We now obtain $D$ from $D'$ by adding a new set of $n-n'$ vertices and for each of them, adding a digon linking it to $s$. By construction, $D$ has $n$ vertices. Further, as the same property holds for $D'$, in any graph obtained from $D$ by at most $\frac{1}{2}[\log n] - 1$ inversions, one of the vertices in $V(D') \setminus \{s\}$ is a source or a sink. $\square$
We are now ready to prove the lower bound in Theorem 1.1.

**Lemma 3.7.** For every pair of positive integers $n, k$ with $n \ge k+2$, there is a 2k-edge-connected digraph $D$ on $n$ vertices such that $\text{sinv}'_k(D) \ge \frac{1}{2}\log(n-k+1)$.

*Proof.* By assumption, we have $n-k+1 \ge 3$. Hence, by Lemma 3.6, there exists a 2-edge-connected digraph $D_0$ on $n-k+1$ vertices such that any digraph obtained from $D_0$ by inverting fewer than $\frac{1}{2}\log(n-k+1)$ sets has a sink or a source. Now let $D$ be the digraph obtained from $D_0$ by adding a set $S$ of $k-1$ vertices, for any pair of vertices in $S$ a digon linking them, and for every vertex in $S$ and every vertex in $V(D_0)$ a digon linking these vertices. One can check that $D$ has $n$ vertices and is 2k-edge-connected.

Now consider a family of subsets $\mathcal{X}$ such that $D' = \text{Inv}(D; \mathcal{X})$ is $k$-arc-strong. Any vertex $v \in V(D_0)$ is linked to the vertices of $S$ by digons in $D$. Since an inversion transforms a digon into a digon, it is also connected to the vertices of $S$ by digons in $D'$. Hence, in $D'$, $v$ has at least one in-neighbour and one out-neighbour in $V(D_0)$. In other words, the subdigraph of $D'$ induced by $V(D_0)$ has no source and no sink. Thus $|\mathcal{X}| \ge \frac{1}{2}\log(n-k+1)$.

Therefore $\text{sinv}'_k(D) \ge \frac{1}{2}\log(n-k+1)$. $\square$

Finally, Lemmas 3.4 and 3.7 imply Theorem 1.1.

# 4 Complexity of computing $\text{sinv}_k$ and $\text{sinv}'_k$

In this section, we deal with the complexity of computing the parameters $\text{sinv}_k(D)$ and $\text{sinv}'_k(D)$ for a given digraph $D$. More concretely, we prove Theorems 1.2, 1.3, 1.4, and 1.5.

In order to prove these results in this section, we shall use another well-studied hypergraph parameter. Let $H$ be a hypergraph. For some positive integer $k$, a $k$-colouring of $H$ is a mapping $\phi: V(H) \to [k]$ such that every hyperedge $e \in E(H)$ contains two vertices $u$ and $v$ with $\phi(u) \neq \phi(v)$. The **chromatic number** of $H$, denoted by $\chi(H)$ is the smallest integer $k$ such that $H$ admits a $k$-colouring. Generalizing the definition for graphs, for some $S \subseteq V(H)$, the $S$-cut, denoted by $\delta_H(S)$, is the set of hyperedges $e \in E(H)$ satisfying $e \cap S \neq \emptyset$ and $e \setminus S \neq \emptyset$. A **cut cover** of $H$ is a collection $X_1, \dots, X_t$ of subsets of $V(H)$ such that $\cup_{i=1}^t \delta_H(X_i) = E(H)$. The **cut covering number** of $H$, denoted by $\text{cc}(H)$, is the minimum integer $t$ such that there is a cut cover of $H$ of size $t$. The following well-known result shows a close relationship between the cut covering number and the chromatic number. It was proved in [HHM77] for graphs and literally generalizes to hypergraphs.

**Proposition 4.1** (Harary, Hsu, and Miller [HHM77]). For any hypergraph $H$, we have $\text{cc}(H) = [\log(\chi(H))]$.

It is well-known that the problem of deciding whether a given graph can be coloured with $t$ colours is NP-hard for any $t \ge 3$ (see [Sch78]). Moreover, the problem of deciding whether a hypergraph is 2-colourable is also NP-hard (see [Sch78]). It hence follows from Proposition 4.1 that deciding whether the cut covering number of a given hypergraph is at most $t$ is NP-hard for any integer $t \ge 1$. We shall show a reduction from this problem to the one of deciding whether $\text{sinv}'_k(D) \le t$ for a given oriented graph $D$.

We need the following result of Guruswami, Hastad, and Sudan [GHS00].

**Proposition 4.2** (Guruswami, Hastad, and Sudan [GHS00]). Unless $P=\text{NP}$, there do not exist any integers $c_1, c_2$ with $2 \le c_1 \le c_2$ for which there exists a polynomial-time algorithm that distinguishes a $c_1$-colourable hypergraph from a not $c_2$-colourable hypergraph.

As a consequence, we directly obtain a negative result concerning the approximation of the cut covering number from Proposition 4.1.

**Proposition 4.3.** Unless $P=\text{NP}$, there do not exist any integers $c_1, c_2$ with $1 \le c_1 \le c_2$ for which there exists a polynomial-time algorithm that distinguishes a hypergraph of cut covering number at most $c_1$ from a hypergraph of cut covering number more than $c_2$.

We shall also use the following notation. Given a digraph $D$ and a set $X$ of vertices in $D$, we denote by $\partial_D(X)$ the set of edges of $\text{UG}(D)$ with exactly one endvertex in $X$: $\partial_D(X) = \delta_{\text{UG}(D)}(X)$.
## 4.1 Inversions to become $k$-arc-strong

In this subsection, we prove Theorems 1.2 and 1.3. The two proofs are based on a reduction given by the following lemma.

**Lemma 4.4.** Given a hypergraph $H$ and a positive integer $k$, one can construct in polynomial time an oriented graph $D$ such that $\text{sinv}'_k(D) = \text{cc}(H)$ and $|V(D)| = |V(H)| + (2k+1)|E(H)| + 2k+1$.

*Proof.* Let $<$ be an arbitrary ordering on $V(H)$. We let $V(D)$ be the disjoint union of $V(H)$, sets of vertices $Z_e = \{z_e^1, \dots, z_e^{2k+1}\}$ for every $e \in E(H)$, and a set of vertices $W = \{w_1, \dots, w_{2k+1}\}$. We add arcs to $D$ such that $D\langle W \rangle$ is a $k$-arc-strong tournament. We let $A(D)$ contain an arc from $v$ to $w_i$ for every $v \in V(H)$ and every $i = 1, \dots, k$ and an arc from $w_i$ to $v$ for every $v \in V(H)$ and every $i = k+1, \dots, 2k$. Next for every $e \in E(H)$, we add arcs to $D$ such that $D\langle Z_e \rangle$ is a $k$-arc-strong tournament. Finally, for every $e \in E(H)$, consider $u, v \in e$ with $u < v$ and $v < v'$ for all $v' \in e \setminus \{u, v\}$. We add the arcs $uz_e^i$ and $z_e^iv$ for $i = 2, \dots, k$ and the arc $v'z_e^1$ for all $v' \in e$. This finishes the description of $D$. Observe that $|V(D)| = |V(H)| + (2k+1)|E(H)| + 2k+1$. We now show that $\text{sinv}'_k(D) = \text{cc}(H)$.

Let us first show that $\text{sinv}'_k(D) \le \text{cc}(H)$. Let $(X_1, \dots, X_{cc(H)})$ be a minimum-size cut cover of $H$. For every $e \in E(H)$, there is a smallest $\alpha(e)$ such that $e \cap X_{\alpha(e)}$ and $e \setminus X_{\alpha(e)}$ are nonempty. Now for $i \in [cc(H)]$, let $X'_i = X_i \cup \{z_e^1 : \alpha(e) = i\}$. Let $D'$ be the digraph obtained from $D$ by inverting $X'_1, \dots, X'_{cc(H)}$. We will show that $D'$ is $k$-arc-strong. Let $S \subseteq V(D)$ be non-empty and suppose that $\min\{d_{D'}^-(S), d_{D'}^+(S)\} < k$. By symmetry, we may suppose that $S \cap W \ne \emptyset$. As $D'\langle W \rangle = D\langle W \rangle$ is $k$-arc-strong, we obtain $W \subseteq S$. Next observe that in $D'$ every $v \in V(H)$ is incident to at least $k$ arcs coming from $W$ and $k$ arcs going to $W$. Thus $V(H) \subseteq S$. Now consider some $e \in E(H)$ and let $u, v \in e$ with $u < v$ and $v < v'$ for all $v' \in e \setminus \{u, v\}$. As $D'\langle Z_e \rangle = D\langle Z_e \rangle$ and $D\langle Z_e \rangle$ is $k$-arc-strong by construction, we obtain that either $Z_e \subseteq S$ or $Z_e \cap S = \emptyset$. Observe that, by construction, $z_e^1$ has an in-neighbour and an out-neighbour in $V(H)$ in $D'$. Further observe that $A(D')$ contains the arcs $uz_e^i$ and $z_e^iv$ for all $i \in \{2, \dots, k\}$. Thus $D'$ contains $k$ arcs from $V(H)$ to $Z_e$ and $k$ arcs from $Z_e$ to $V(H)$, and we obtain that $Z_e \subseteq S$. This yields $S = V(D')$, so $D'$ is $k$-arc-strong. Thus $\text{sinv}'_k(D) \le \text{cc}(H)$.

Let us now show that $\text{cc}(H) \le \text{sinv}'_k(D)$. Let $(X_1, \dots, X_t)$ be a minimum-size $k$-arc-strengthening family of $D$. Let $D' = \text{Inv}(D; (X_i)_{i \in [t]})$ and for $i \in [t]$, let $X'_i = X_i \cap V(H)$. We claim that $(X'_1, \dots, X'_t)$ is a cut cover of $H$. In other words, for every $e \in E(H)$, there is some $i \in [t]$ such that $X'_i \cap e \ne \emptyset$ and $e \setminus X'_i \ne \emptyset$.

Suppose otherwise. It follows that there is exactly one arc entering $Z_e$ incident to $z_e^j$ in $D'$, for every $j = 2, \dots, k$. As $D'$ is $k$-arc-strong, we obtain that in $D'$, there exists at least one arc entering $Z_e$ incident to $z_e^1$ and at least one arc entering $Z_e$ incident to $z_e^1$. By assumption, for every $i \in [t]$ either $e \subseteq X_i$ or $e \cap X_i = \emptyset$ holds. Thus we deduce that for every $j \in [k]$, either all the arcs corresponding to edges in $\partial_D(Z_e) \cap \partial_D(z_e^j)$ are inverted or none of them are, a contradiction. Therefore, $(X'_1, \dots, X'_t)$ is a cut cover of $H$, and so $\text{cc}(H) \le t = \text{sinv}'_k(D)$. $\square$

Let $k$ and $t$ be two positive integers. Lemma 4.4 and the NP-hardness of deciding whether a given hypergraph $H$ satisfies $\text{cc}(H) \le t$ for all $t \ge 1$ directly imply that deciding whether a given oriented graph $D$ satisfies $\text{sinv}'_k(D) \le t$ is NP-hard. This problem is clearly in NP because a family $\mathcal{X}$ such that $\text{Inv}(D; \mathcal{X})$ is $k$-arc-strong is a polynomial-size certificate that $\text{sinv}'_k(D) \le |\mathcal{X}|$. Hence it is NP-complete, which proves Theorem 1.2.

Moreover, Proposition 4.3 and Lemma 4.4 imply Theorem 1.3.

## 4.2 Inversions to become $k$-strong

In this subsection, we prove Theorems 1.4 and 1.5. The two proofs are based on a reduction given by the following lemma.

**Lemma 4.5.** Given a hypergraph $H$ and a positive integer $k$, one can construct in polynomial time a $k$-strengthenable oriented graph $D$ such that $\text{sinv}_k(D) = \text{cc}(H)$ and $|V(D)| = |V(H)| + (2k+1)|E(H)| + 2k+1$.

*Proof.* Let $V(D)$ be the disjoint union of $V(H)$, sets of vertices $Z_e = \{z_e^1, \dots, z_e^{2k+1}\}$ for every $e \in E(H)$, and a set of vertices $W = \{w_1, \dots, w_{2k+1}\}$. We add arcs to $D$ such that $D\langle W \rangle$ is a $k$-strong tournament.
Let $A(D)$ contain an arc from $v$ to $w_i$ for every $v \in V(H)$ and every $i \in [k]$ and an arc from $w_i$ to $v$ for every $v \in V(H)$ and every $i \in \{k+1, \dots, 2k\}$. Next for every $e \in E(H)$, we add arcs to $D$ such that $D\langle Z_e \rangle$ is a $k$-strong tournament. Further, for every $e \in E(H)$, $i \in [k]$ and $j \in [k-1]$, we add an arc from $z_e^i$ to $w_j$ and for every $e \in E(H)$, $i \in \{k+1, \dots, 2k\}$ and $j \in [k-1]$, we add an arc from $w_j$ to $z_e^i$. Finally, for every $e \in E(H)$ and $v \in e$, we add the arc $vz_e^1$. This finishes the description of $D$. Observe that $|V(D)| = |V(H)| + (2k+1)|E(H)| + 2k+1$. We now show that $\text{sinv}_k(D) = \text{cc}(H)$. Note that this implies that $\text{sinv}_k(D)$ is finite and thus $D$ is $k$-strengthenable.

We first show that $\text{sinv}_k(D) \le \text{cc}(H)$. Let $(X_1, \dots, X_t)$ be an optimal cut cover of $H$. Now for every $e \in E(H)$, there is a smallest $\alpha(e)$ such that $e \cap X_{\alpha(e)}$ and $e \setminus X_{\alpha(e)}$ are nonempty. Now for every $i \in [t]$, let $X_i' = X_i \cup \{z_e^1 : \alpha(e) = i\}$. Let $D'$ be the digraph obtained from $D$ by inverting $X_1', \dots, X_t'$. We will show that $D'$ is $k$-strong. Let $Y \subseteq V(D)$ with $|Y| \le k-1$. We need to show that $D' - Y$ is strongly connected. As $D\langle W \rangle$ is $k$-strong, we obtain that $W \setminus Y$ is contained in a single strongly connected component $S$ of $D' - Y$. Next observe that every $v \in V(H) \setminus Y$ has an in-neighbour and an out-neighbour in $S$, so $V(H) \setminus Y \subseteq S$. Now consider some $e \in E(H)$. As $D'\langle Z_e \rangle = D\langle Z_e \rangle$ is $k$-strong, we obtain that $Z_e \setminus Y$ is contained in a single strongly connected component of $D' - Y$. If $Y \ne \{w_1, \dots, w_{k-1}\}$, then there is at least one arc from $Z_e \setminus Y$ to $W \setminus Y$ and there is at least one arc from $W \setminus Y$ to $Z_e \setminus Y$, so $Z_e \setminus Y \subseteq S$. Finally, if $Y = \{w_1, \dots, w_{k-1}\}$, observe that, by construction, $D'$ contains an arc from $V(H)$ to $z_e^1$ and an arc from $z_e^1$ to $V(H)$. Again, we obtain $Z_e \setminus Y \subseteq S$. This yields that $D'$ is $k$-strong. We hence have $\text{sinv}_k(D) \le t = \text{cc}(H)$.

We now show that $\text{cc}(H) \le \text{sinv}_k(D)$. Let $(X_1, \dots, X_t)$ be a minimum $k$-strengthening family of $D$. For $i=1, \dots, t$, let $X_i' = X_i \cap V(H)$. We claim that $(X_1', \dots, X_t')$ is a cut cover of $H$. In other words, for every $e \in E(H)$, there is some $i \in \{1, \dots, t\}$ such that $e \cap X_i$ and $e \setminus X_i$ are nonempty.

Suppose otherwise, that is for every $i \in [t]$ either $e \subseteq X_i$ or $e \cap X_i = \emptyset$ holds. Thus all the arcs corresponding to edges in $\partial_D(Z_e) \cap \partial_D(z_e^1)$ are inverted or none of them. This yields that in $D' - \{w_1, \dots, w_{k-1}\}$, there is either no arc entering $Z_e$ or no arc leaving $Z_e$. Hence $D' - \{w_1, \dots, w_{k-1}\}$ is not strongly connected, a contradiction. Therefore, we obtain that $(X_1', \dots, X_t')$ is a cut cover for $H$. Thus $\text{cc}(H) \le t = \text{sinv}_k(D)$, and we conclude that $\text{cc}(H) = \text{sinv}_k(D)$. $\square$

Let $k$ and $t$ be two positive integers. Lemma 4.5 and the NP-hardness of deciding whether a given hypergraph $H$ satisfies $\text{cc}(H) \le t$ for all $t \ge 1$ directly imply that deciding whether a given oriented graph $D$ satisfies $\text{sinv}_k(D) \le t$ is NP-hard. This problem is clearly in NP because a family $\mathcal{X}$ such that $\text{Inv}(D; \mathcal{X})$ is $k$-strong is a polynomial-size certificate that $\text{sinv}_k(D) \le |\mathcal{X}|$. Hence it is NP-complete, which proves Theorem 1.4.

Moreover Proposition 4.3 and Lemma 4.5 imply Theorem 1.5.

Lemma 4.5 and the NP-hardness of deciding whether a given hypergraph $H$ satisfies $\text{cc}(H) \le t$ for all $t \ge 1$ directly imply the following.

**Corollary 4.6.** Let $t$ and $k$ be positive integers. Deciding whether $\text{sinv}_k(D) \le t$ for a given oriented graph $D$ is NP-complete.

# 5 Bounds on $M_k'$ and $M_k$

This section is dedicated to giving upper and lower bounds on $M_k$ and $M_k'$, in particular proving Theorems 1.7 and 1.8. First, in Section 5.1, we completely determine $M_k$ and $M_k'$ for some small values of $k$. Next, in Section 5.2, we prove Theorem 5.4, which is the lower bound in Theorem 1.7 and a slight extension of this result. In Section 5.3, we prove Theorem 5.8, which is the upper bound in Theorem 1.7. We further give a slight improvement of this result for tournaments on exactly $2k+1$ vertices. Finally, in Section 5.4, we give the somewhat involved, probabilistic proof of Theorem 1.8.

## 5.1 Values of $M_1'$, $M_1$, $M_2'$ and $M_2$

We here provide the exact values of $M_i$ and $M_i'$ for $i \in \{1, 2\}$.

**Proposition 5.1.** Let $T$ be a tournament of order $n \ge 3$. We have $\text{sinv}_1(T) = \text{sinv}_1'(T) = 0$ if $T$ is strong and $\text{sinv}_1(T) = \text{sinv}_1'(T) = 1$ otherwise. In particular, $m_1(n) = m_1'(n) = 1$ for all $n \ge 3$ and $M_1 = M_1' = 1$.
*Proof.* Trivially, if $T$ is strong, then $\text{sinv}_1(T) = 0$. If $T$ is not strong, then $\text{sinv}_1(T) \ge 1$. Now consider a hamiltonian path of $T$. Such a path does exist by Redei's Theorem (see e.g. Theorem 1.4.2 in [BJG09]). Let $x$ be its initial vertex and $y$ its terminal vertex. As $T$ is not strong, we have $xy \in A(T)$, and hence inverting $\{x, y\}$ yields a tournament with a directed hamiltonian cycle because $V(T) \setminus \{x, y\} \ne \emptyset$. It follows that this tournament is strong, and so $\text{sinv}_1(T) = 1$. $\square$

For every integer $n$, let $TT_n$ be the unique (up to isomorphism) acyclic tournament of order $n$. Let $\vec{C}_3$ be the directed triangle, and let $S_4$ be the unique (up to isomorphism) strong tournament of order 4. Its vertex set is $\{a, b, c, d\}$ and its arc set is $\{ab, bc, cd, da, ca, db\}$.

**Proposition 5.2.** $M_2 = M'_2 = 2$.

*Proof.* The rotative tournament $R_5$ of order 5 is the only 2-arc-strong tournament of order 5. As observed in [BBBP10], we have $\text{inv}(R_5) = 2$, so $\text{sinv}'_2(TT_5) = 2$. Hence $M_2 \ge M'_2 \ge 2$.

Let us now prove that $M_2 \le 2$. We shall prove by induction on $n$ that every tournament $T$ of order at least 5 satisfies $\text{sinv}_2(T) \le 2$.

Assume first that $T$ is a tournament of order 5. If $T$ is strong, then, by Camion's theorem [Cam59], it has a hamiltonian cycle $v_1v_2v_3v_4v_5v_1$. Let $A^+ = A(T) \cap \{v_1v_3, v_2v_4, v_3v_5, v_4v_1, v_5v_2\}$ and $A^- = A(T) \cap \{v_3v_1, v_4v_2, v_5v_3, v_1v_4, v_2v_5\}$. We have $|A^+| + |A^-| = 5$, so one of the two sets $A^+$, $A^-$ has at most two arcs. Reversing the arcs of this set, one after another, yields the 2-strong tournament $R_5$.

Assume now that $T$ is not strong. Then by possibly replacing $T$ by its **converse**, that is the tournament $\text{Inv}(D, V(D))$, one of the following property holds.

* $T = TT_5$ with hamiltonian path $v_1v_2v_3v_4v_5$. Then inverting $\{v_1, v_2, v_4, v_5\}$ and $\{v_1, v_5\}$ yields $R_5$.

* $S_4 \Rightarrow \{x\}$. Then inverting $\{c, d, x\}$ and $\{c, d\}$ yields $R_5$.

* $(\{x\} \Rightarrow \vec{C}_3) \Rightarrow \{y\}$ with $\vec{C}_3 = abca$. Then inverting $\{a, x, y\}$ yields $R_5$.

* $(\{x\} \Rightarrow \{y\}) \Rightarrow \vec{C}_3$ with $\vec{C}_3 = abca$. Then inverting $\{a, b, c, y\}$ and $\{a, x, y\}$ yields $R_5$.

As $\text{sinv}_2(\text{Inv}(D, V(D))) = \text{sinv}_2(D)$ for digraph $D$, the statement follows. Assume now that $T$ has at least 6 vertices.

Assume first $T$ has a vertex $v$ such that $\min\{d^+(v), d^-(v)\} \ge 2$. By the induction hypothesis, $\text{sinv}_2(T - v) \le 2$, so there is a family $\mathcal{X}$ of at most two subsets of $V(T - v)$ such that $\text{Inv}(T - v; \mathcal{X})$ is 2-strong. Now $\text{Inv}(T; \mathcal{X}) - v = \text{Inv}(T - v; \mathcal{X})$ and $\min\{d^+(v), d^-(v)\} \ge 2$. Thus, by Lemma 2.1, $\text{Inv}(T; \mathcal{X})$ is 2-strong, and it follows that $\text{sinv}_2(T) \le |\mathcal{X}| \le 2$.

Assume now that every vertex has either in-degree at most 1 or out-degree at most 1. Then necessarily $T$ must be the tournament $\vec{C}_3 \Rightarrow \vec{C}_3$. Let $V(T) = \{a, b, c, d, e, f\}$ with $\{a, b, c\} \Rightarrow \{d, e, f\}$. Then inverting $\{a, b, c, d\}$ and $\{a, d, e, f\}$ transforms $T$ into a 2-strong tournament. $\square$

## 5.2 Lower bound on $m'_k(2k + 1)$

We shall first show the lower bound $m'_k(2k + 1) = \Omega(\log k)$. We need the following result.

**Theorem 5.3 (McKay [McK90]).** Let $n$ be an odd integer. The number of labelled eulerian tournaments on $n$ vertices is

$$ \left(\frac{2^{n+1}}{\pi n}\right)^{\frac{n-1}{2}} \sqrt{\frac{n}{e}}(1+o(1)). $$

We are now ready to prove the lower bound in Theorem 1.7.

**Theorem 5.4.** For every sufficiently large $k$, $m'_k(2k + 1) \ge \frac{1}{2}\log(2k + 1)$.

*Proof.* By Theorem 5.3, we may choose an integer $k_0$ such that for all $k \ge k_0$ and for $n = 2k + 1$, the number of labelled eulerian tournaments on $n$ vertices is at most $\left(\frac{2^{n+1}}{\pi n}\right)^{\frac{n-1}{2}} \sqrt{n}$ and $\frac{n-1}{2}(\log \pi - 1) > \log n$. Now fix some $k \ge k_0$ and let $n = 2k + 1$. By Proposition 2.3, all the $k$-arc-strong tournaments on $n$ vertices are eulerian. For two labelled tournaments $T, T'$ on the same vertex set, we say that $T'$ is **reachable** from $T$ by $t$ inversions for some positive integer $t$, if there is a family of sets $(X_1, \dots, X_t)$
such that $\mathrm{Inv}(T; X_1, \dots, X_t) = T'$. Observe that there are $2^n$ possibilities to choose $X_i$ for $i = 1, \dots, t$, hence the number of tournaments reachable from $T$ by $t$ inversions is at most $(2^n)^t = 2^{nt}$. Therefore, the number of $n$-vertex labelled tournaments that are reachable by $t$ inversions from an eulerian one is at most

$$ 
\begin{aligned}
2^{nt} \left( \frac{2^{n+1}}{\pi n} \right)^{\frac{n-1}{2}} \sqrt{n} &= 2^{\binom{n}{2}} \cdot 2^{nt} \left( \frac{2}{\pi n} \right)^{\frac{n-1}{2}} \sqrt{n} \\
&= 2^{\binom{n}{2}} \cdot 2^{nt + \frac{n-1}{2}(1 - \log(\pi) - \log n) + \frac{1}{2} \log n} \\
&< 2^{\binom{n}{2}} \cdot 2^{nt - \frac{1}{2}n \log n}
\end{aligned}
$$

If $t \le \frac{1}{2} \log n$, then $nt - \frac{1}{2}n \log n \le 1$, so the number of such tournaments is fewer than $2^{\binom{n}{2}}$. It follows that there is at least one tournament $T^*$ on $2k+1$ vertices which cannot be reached from an eulerian tournament by at most $t$ inversions. Thus $\sin v_k^*(T^*) > t$. $\square$

Theorem 5.4 can be slightly generalised to tournaments on $2k+c$ vertices for small integers $c$. To do so, we will need the following generalisation of Theorem 5.3.

For a positive integer $n$ and a collection of integers $\alpha_1, \dots, \alpha_n$, we denote by $NT(n; \alpha_1, \dots, \alpha_n)$ the number of labelled tournaments on $[n]$ in which the vertex $i$ satisfies $d^+(i) - d^-(i) = \alpha_i$.

**Theorem 5.5** (Spencer [Spe74] and McKay [McK90]). Let $c$ be an integer and let $\epsilon > 0$. There is an integer $n_0$ such that for every $n \ge n_0$, for every $\alpha_1, \dots, \alpha_n \in [-c, c]$, we have

$$ NT(n, \alpha_1, \dots, \alpha_n) \le \left( \frac{2^{n+1}}{\pi n} \right)^{(n-1)/2} \sqrt{\frac{n}{e}} \exp \left( -\frac{1-\epsilon}{2n} \sum_{i=1}^{n} \alpha_i^2 \right). $$

**Corollary 5.6.** For all integers $k$ and $c$, the number of labelled tournaments $T$ on $n = 2k+c$ vertices such that every vertex has in- and out-degree at least $k$ is at most $2^{\log(2c)n} \left( \frac{2^{n+1}}{\pi n} \right)^{(n-1)/2} \sqrt{\frac{n}{e}}$ for $k$ large enough.

*Proof.* By Theorem 5.5 for $\epsilon = 1$, for $k$ large enough, the number of labelled tournaments $T$ on $n = 2k+c$ vertices such that every vertex has in- and out-degree at least $k$ is at most

$$ \left( \frac{2^{n+1}}{\pi n} \right)^{(n-1)/2} \sqrt{\frac{n}{e}} \sum_{(\alpha_1, \dots, \alpha_n) \in \{-c+1, \dots, c-1\}^n} 1, $$

which is

$$ \left( \frac{2^{n+1}}{\pi n} \right)^{(n-1)/2} \sqrt{\frac{n}{e}} (2c-1)^n $$

and the corollary follows from the fact that $(2c-1)^n \le 2^{\log(2c)n}$. $\square$

**Theorem 5.7.** For every fixed positive integer $c$, and for every positive integer $k$ large enough compared to $c$, there exists a tournament $T$ on $2k+c$ vertices such that $\sin v_k^*(T) > \frac{1}{2} \log(2k+c) - \log(2c)$. In particular, $m_k^*(2k+c)$ is unbounded for every fixed $c$.

*Proof.* By Corollary 5.6, the number of labelled tournaments $T$ on $n = 2k+c$ vertices with $\sin v_k^*(T) \le t$ is for $k$ large enough at most

$$ 2^{nt} 2^{\log(2c)n} \left( \frac{2^{n+1}}{\pi n} \right)^{(n-1)/2} \sqrt{\frac{n}{e}} < 2^{\binom{n}{2}} 2^{nt - \frac{1}{2}n \log n + \log(2c)n} $$

which is at most $2^{\binom{n}{2}}$ if $t \le \frac{1}{2} \log n - \log(2c)$. Hence there exists a tournament $T^*$ with $\sin v_k^*(T^*) > \frac{1}{2} \log(2k+c) - \log(2c)$. $\square$
## 5.3 Upper bounds on $M_k$ and transitive tournaments

In this section, we give some upper bounds on $M_k$ for all positive integers $k$. Most notably, we prove the upper bound in Theorem 1.7.

**Theorem 5.8.** $M_k \le 2k$.

*Proof.* Let $T$ be a tournament with $V(T) = \{v_1, \dots, v_n\}$ with $n \ge 2k+1$. Further, let $T'$ be a $k$-strong tournament on $\{v_1, \dots, v_{2k+1}\}$. We now define sets $X_1, \dots, X_{2k}$. Suppose that the sets $X_1, \dots, X_{i-1}$ have already been created and let $T_{i-1}$ be the graph obtained from $T$ by inverting $X_1, \dots, X_{i-1}$. Now let $X_i = \{v_i\} \cup A_i \cup B_i$, where $A_i$ is the set of vertices $v_j$ with $j \in \{i+1, \dots, 2k+1\}$ for which the edge $v_iv_j$ has a different orientation in $T'$ and $T_{i-1}$, and $B_i$ is, when $i \le k$ (resp. $i \ge k+1$), the set of vertices $v_j$ with $j \ge 2k+2$ for which $T_{i-1}$ contains the arc $v_iv_j$ (resp. $v_jv_i$).

We still need to show that $T_{2k}$ is $k$-strong. Observe that $T_{2k}(\{v_1, \dots, v_{2k+1}\}) = T'$ which is $k$-strong by assumption. Moreover, for any $j \ge 2k+2$, $T_{2k}$ contains the arcs $v_jv_i$ for $i = 1, \dots, k$ and the arcs $v_iv_j$ for $i = k+1, \dots, 2k$. Hence, by Lemma 2.1, $T_{2k}$ is $k$-strong. $\square$

Theorems 5.4 and 5.8 directly imply Theorem 1.7.

It is tempting to improve the upper bound in Theorem 1.7. While we are not able to provide an improvement for the general case, we show in the following that a small improvement can be achieved in a seemingly critical case, namely when the size of the tournament is exactly $2k+1$. We first need the following result.

**Theorem 5.9.** Let $n, k$ be integers with $n \ge 2k+1$.

$$ \sin v_k(TT_n) = \sin v'_k(TT_n) = \begin{cases} 2 & \text{if } 2k+1 \le n < 3k \\ 1 & \text{if } 3k \le n. \end{cases} $$

*Proof.* We first prove that $\sin v_k(n) \le 2$. Let $(v_1, \dots, v_n)$ be the unique ordering of $V(TT_n)$ such that $v_iv_j \in A(TT_n)$ for every $i < j$. Let $X_0 = \{v_i \mid i \text{ even}\}$ and $X_1 = \{v_i \mid i \text{ odd}\}$. We claim that $T' = \text{Inv}(TT_n; X_0, X_1)$ is $k$-strong. Consider a set $Y$ of at most $k-1$ vertices of $T'$. Let $i_0$ (resp. $j_0$) be the smallest (resp. largest) even integer $\ell$ such that $v_\ell \notin Y$, and let $i_1$ (resp. $j_1$) be the smallest (resp. largest) odd integer $\ell$ such that $v_\ell \notin Y$. Observe that $j_0 > i_1$ and $j_1 > i_0$ since $|Y| < k$ and $n \ge 2k+1$. In particular, $v_{i_1}v_{j_0}, v_{i_0}v_{j_1} \in A(T')$. Since $T'\langle X_0 \rangle - Y$ (resp. $T'\langle X_1 \rangle - Y$) is a transitive tournament with source $v_{j_0}$ and sink $v_{i_0}$ (resp. source $v_{j_1}$ and sink $v_{i_1}$), there are hamiltonian paths $P_0$ from $v_{j_0}$ to $v_{i_0}$ in $T'\langle X_0 \rangle - Y$ and $P_1$ from $v_{j_1}$ to $v_{i_1}$ in $T\langle X_1 \rangle - Y$. Finally $P_0v_{i_0}v_{j_1}P_1v_{i_1}v_{j_0}$ is an hamiltonian directed cycle of $T' - Y$, and so $T' - Y$ is strong. Hence $T'$ is $k$-strong, and $\sin v_k(TT_n) \le 2$.

Let us now prove that $\sin v'_k(TT_n) \ge 2$ if $n \le 3k-1$. Suppose for a contradiction that there exists $X \subseteq V(TT_n)$ such that $T' = \text{Inv}(TT_n; X)$ is $k$-arc-strong. Then, for every $i \le k$, since $v_i$ has in-degree $i-1$ in $TT_n$, we have $v_i \in X$. Similarly, for every $i \ge n-k+1$, since $v_i$ has out-degree $n-i$ in $TT_n$, we have $v_i \in X$. But then every out-neighbour of $v_1$ in $T'$ is in $\{v_{k+1}, \dots, v_{n-k}\}$ and so $d_{T'}^+(v_1) \le n-2k < k$. Hence $T'$ is not $k$-arc-strong, a contradiction.

Finally, let us show that $\sin v_k(TT_n) \le 1$ if $n \ge 3k$. Let $(v_1, \dots, v_n)$ be the unique ordering of $V(TT_n)$ such that $v_iv_j \in A(TT_n)$ for every $i < j$. Let $A = \{v_1, \dots, v_k\}$, $B = \{v_{k+1}, \dots, v_{2k}\}$ and $C = \{v_{2k+1}, \dots, v_n\}$. In $T' = \text{Inv}(TT_n; A \cup C)$, we have $A \Rightarrow B, B \Rightarrow C$ and $C \Rightarrow A$. Since $|A|, |B|, |C| \ge k$, $T'$ is $k$-strong. $\square$

As mentioned in the introduction, it was proven independently by Alon et al. [APS+24] and Aubian et al. [AHH+22] that $\text{inv}(n) \le n - \lfloor \log(n+1) \rfloor$. Hence, every tournament of order $2k+1$ can be made acyclic in at most $2k - \lfloor \log(k+1) \rfloor$ inversions, and $k$-strong in two more inversions by Theorem 5.9. Thus we have the following.

**Corollary 5.10.** $m_k(2k+1) \le 2k - \lfloor \log(k+1) \rfloor + 2$.

## 5.4 Upper bound on $M'_k$

This section is dedicated to proving Theorem 1.8. First, we give some auxiliary results in Section 5.4.1. Next, in Section 5.4.2, we show the result when restricting to tournaments of size exactly $2k+1$. We finally generalize this to bigger tournaments in Section 5.4.3.
### 5.4.1 Preliminaries

We here collect some auxiliary results we need for the proof of Theorem 1.8. We first need a basic result combining probability and linear algebra.

**Proposition 5.11.** Let $A \in \mathbb{F}_2^{q \times q'}$ be a matrix whose rank is $q$ for some integers $q, q'$ with $q \le q'$. Further, let $\vec{v} \in \mathbb{F}_2^q$ be a fixed vector and let another vector $\vec{w} \in \mathbb{F}_2^q$ be drawn uniformly at random. Then $\Pr(A\vec{w} = \vec{v}) = 2^{-q}$.

The simple proof of the following result is similar to the one of Theorem 5.8 (see [HHR24, Lemma 2.1]).

**Proposition 5.12.** Let $T_1, T_2$ be tournaments with $V(T_1) = V(T_2)$. Then there is a collection of $|V(T_1)| - 1$ subsets $X_1, \dots, X_{|V(T_1)|-1}$ of $V(T_1)$ such that $\mathrm{Inv}(T_1; X_1, \dots, X_{|V(T_1)|-1}) = T_2$.

We are now ready to give the last preliminary result.

**Proposition 5.13.** Let $T$ be a tournament on $2k+1$ vertices and $X \subseteq V(T)$ with $|X| \le \frac{2}{3}k$ such that $d_T^-(x) = d_T^+(x) = k$ for all $x \in X$. Then there exists a $k$-arc-strong tournament $T'$ on $V(T)$ such that all the edges in $E(UG(T)\langle X\rangle) \cup \delta_{\mathrm{UG}(T)}(X)$ have the same orientation in $T$ and $T'$.

*Proof.* Let $H$ be the mixed graph which is obtained from $UG(T)$ by giving all edges in $E(UG(T)\langle X\rangle) \cup \delta_{\mathrm{UG}(T)}(X)$ the orientation they have in $T$. Now consider some $S \subseteq V(T)$. Let $x \in S \cap X$. Since $d_H^+(x) = d_H^-(x)$, we have

$$ 
\begin{align*}
d_H^+(S \setminus \{x\}) - d_H^-(S \setminus \{x\}) &= (d_H^+(S) - d_H^+(x, V(H) \setminus S) + d_H^+(S \setminus \{x\}, x)) \\
&\quad - (d_H^-(S) - d_H^-(x, V(H) \setminus S) + d_H^-(S \setminus \{x\}, x)) \\
&= d_H^+(S) - d_H^+(S) \\
&\quad + d_H^+(S \setminus \{x\}, x) + d_H^+(V(H) \setminus S, x) \\
&\quad - d_H^+(x, V(H) \setminus S) - d_H^+(x, S \setminus \{x\})) \\
&= d_H^+(S) - d_H^+(S) + d_H^-(x) - d_H^+(x) \\
&= d_H^+(S) - d_H^-(S).
\end{align*}
$$

Repeatedly applying this argument, we obtain $d_H^+(S) - d_H^-(S) = d_H^+(S \setminus X) - d_H^-(S \setminus X) \le d_H^+(S \setminus X) \le |S \setminus X| \cdot |X|$ since every arc in $H$ has an extremity in $X$. Symmetrically, we obtain $d_H^+(S) - d_H^-(S) = d_H^-(V(H) \setminus S) - d_H^+(V(H) \setminus S) = d_H^-(V(H) \setminus (S \cup X)) - d_H^+(V(H) \setminus (S \cup X)) \le |V(H) \setminus (S \cup X)| \cdot |X|$. As $|X| \le \frac{2}{3}k \le \frac{1}{2}|V(H) \setminus X| = \frac{1}{2}(|S \setminus X| + |V(H) \setminus (S \cup X)|)$, we obtain

$$ 
\begin{align*}
d_H^+(S) - d_H^-(S) &\le \min\{|S \setminus X|, |V(H) \setminus (S \cup X)|\} \cdot |X| \\
&\le \min\{|S \setminus X|, |V(H) \setminus (S \cup X)|\} \cdot \frac{1}{2}(|S \setminus X| + |V(H) \setminus (S \cup X)|) \\
&\le \min\{|S \setminus X|, |V(H) \setminus (S \cup X)|\} \cdot \max\{|S \setminus X|, |V(H) \setminus (S \cup X)|\} \\
&= |S \setminus X| \cdot |V(H) \setminus (S \cup X)| \\
&= d_H(S).
\end{align*}
$$

Hence, by Proposition 2.4, there is an eulerian orientation $T'$ of $T$ such that all the edges in $UG(T)\langle X\rangle \cup \delta_{\mathrm{UG}(T)}(X)$ have the same orientation in $T$ and $T'$. As $|V(T)| = 2k+1$, the tournament $T'$ is $k$-arc-strong by Proposition 2.3. $\square$

### 5.4.2 Main proof for tournaments of size $2k+1$

We here give the proof of Theorem 1.8 for tournaments of size $2k+1$. More precisely, we prove the following statement.

**Theorem 5.14.** For every $\epsilon > 0$, there is an integer $k_0$ such that for every $k \ge k_0$ and for every tournament $T$ on $2k+1$ vertices, we have $\mathrm{sinv}'_k(T) \le (\frac{4}{3} + \epsilon)k$.
Proof. Let $\epsilon > 0$. We may assume $\epsilon \le 1/3$. We choose $k_0$ large enough so that for all $k \ge k_0$, the three following inequalities hold:

* $\lceil \log^2 k \rceil + \lceil \frac{1}{4} \log k \rceil + \frac{2k}{3\lceil \frac{1}{4} \log k \rceil} \le \epsilon k$

* $16 \log(k) \cdot \lceil \frac{1}{4} \log k \rceil \le \sqrt{k}$.

* $10 \log k \le k^{\frac{1}{8}}$,

In particular, the last inequality is wrong for $k = 2^{12}$ which implies $k_0 \ge 2^{12}$. Thus the following inequalities also hold for all $k \ge k_0$: $\lceil \frac{1}{4} \log k \rceil \le \frac{1}{3}k$; $\lceil \frac{1}{4} \log k \rceil \le \sqrt{k}$; $k \ge 13$; $3\lceil \frac{1}{4} \log k \rceil \le \log k$.

Let $T$ be a tournament on $2k+1$ vertices for some $k \ge k_0$. Let $A \subseteq V(T)$ be an arbitrary subset of $V(T)$ with $|A| = k$ and $B = V(T) \setminus A$. For some $b \in B$ and a tournament $\tilde{T}$ on $V(T)$, we denote $|k - d_{\tilde{T}}^r(b)|$ by $\text{def}_{\tilde{T}}(b)$, the defect of $b$ in $\tilde{T}$. Let $q = \lceil \frac{1}{4} \log k \rceil$ and $q^* = \lceil \log^2 k \rceil$. We now choose $q^*$ sets $X_1, \dots, X_{q^*} \subseteq V(T)$ independently and uniformly at random. Let $T' = \text{Inv}(T; X_1, \dots, X_{q^*})$. For some $b \in B$, we denote by $\tilde{b}$ the vector in $\mathbb{F}_2^{q^*}$ whose $i$-th entry is 1 if $b \in X_i$ and 0 otherwise for $i \in [q^*]$. Observe that by the choice of $X_1, \dots, X_{q^*}$, the vectors $\{\tilde{b} \mid b \in B\}$ follow a uniform distribution and are mutually independent.

We now define a list of possible events:

$E_1$: There is some $b \in B$ with $\text{def}_{T'}(b) \ge 2\sqrt{k} \log k$.

$E_2$: There are some $b_1, \dots, b_q \in B$ such that $\tilde{b}_1, \dots, \tilde{b}_q$ are linearly dependent.

$E_3$: There are some $b_1, \dots, b_q \in B$ such that $\tilde{b}_1, \dots, \tilde{b}_q$ are linearly independent and a sequence $(\star_1, \dots, \star_q) \in \{+, -\}^q$ such that $|\bigcap_{i=1}^q N_{T'}^{\star_i}(b_i) \cap A| \le 5\sqrt{k} \log k$.

**Lemma 5.15.** If none of $E_1$, $E_2$ and $E_3$ occur, then $\text{sinv}'_k(T) \le (\frac{4}{3} + \epsilon)k$.

*Proof.* Let $(B_1, \dots, B_t)$ be a maximal collection of disjoint subsets of $B$ with the following properties:

* $|B_i| = q$ for $i = 1, \dots, t$,

* $\text{def}_{T'}(b) \equiv \text{def}_{T'}(b') \bmod 2$ for all $b, b' \in B_i$ for $i = 1, \dots, t$,

* $tq \le \frac{2}{3}k$.

**Claim 5.15.1.** $|\bigcup_{i=1}^t B_i| \ge \frac{2}{3}k - q$.

*Proof of claim.* Suppose otherwise. Observe that, as $\lceil \frac{1}{4} \log k \rceil \le \frac{1}{3}k$, we have $|B \setminus (\bigcup_{i=1}^t B_i)| = |B| - |\bigcup_{i=1}^t B_i| \ge (k+1) - (\frac{2}{3}k - q) \ge \frac{1}{3}k + q \ge 2q$. By the Pigeonhole Principle, there exists a set $B_0 \subseteq B \setminus (\bigcup_{i=1}^t B_i)$ with $|B_0| = q$ such that $\text{def}_{T'}(b) \equiv \text{def}_{T'}(b') \bmod 2$ for all $b, b' \in B_0$. Hence $B_0$ can be added to $\mathcal{B}$ without violating any of the above conditions, a contradiction to the maximality of $(B_1, \dots, B_t)$. $\diamond$

**Claim 5.15.2.** Let $i \in [t]$. There is a set $Y_i \subseteq B_i \cup A$ such that $\text{def}_{\text{Inv}(T';Y_i)}(b) = 0$ for all $b \in B_i$.

*Proof of claim.* Let $p = \max\{\text{def}_{\text{Inv}(T';B_i)}(b) \mid b \in B_i\}$. Observe that $p \le \max\{\text{def}_{T'}(b) + q - 1 \mid b \in B_i\}$. Hence, as $E_1$ does not occur and $q = \lceil \frac{1}{4} \log k \rceil \le \sqrt{k} \log k$, we have $p \le 2\sqrt{k} \log k + \sqrt{k} \log k = 3\sqrt{k} \log k$. We shall now build a sequence of sets $Y_i^0, \dots, Y_i^p$ with the following properties:

* $Y_i^0 = B_i$,

* $Y_i^{j+1}$ is obtained from $Y_i^j$ by adding one vertex from $A \setminus Y_i^j$ for $j = 0, \dots, p-1$,

* $\max\{\text{def}_{\text{Inv}(T';Y_i^j)}(b) \mid b \in B_i\} = p-j$ for $j = 0, \dots, p$.
The statement then follows for $Y_i = Y_i^p$.

Suppose that we have already created the sets $Y_i^0, \dots, Y_i^j$ for some $j$ with $0 \le j \le p-1$ and now want to create $Y_i^{j+1}$. Let $(b_1, \dots, b_q)$ be an arbitrary ordering of the vertices in $B_i$. For every $\mu \in [q]$, if $\max\{\mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b) \mid b \in B_i\} = d_{\mathrm{Inv}(T';Y_i^j)}^{-}(b_\mu) - k$, let $\star_\mu = -$, if $\max\{\mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b) \mid b \in B_i\} = k - d_{\mathrm{Inv}(T';Y_i^j)}^{-}(b_\mu)$, let $\star_\mu = +$, otherwise choose $\star_\mu \in \{+, -\}$ arbitrarily. As $E_2$ does not occur, $\vec{b}_1, \dots, \vec{b}_q$ are linearly independent. Moreover, as $E_3$ does not occur, $|\bigcap_{\mu=1}^q N_{T'}^{\star_\mu}(b_\mu) \cap A| \ge 5\sqrt{k} \log k$. As $p \le 3\sqrt{k} \log k$, and $q \le \sqrt{k} \log k$, we have $|Y_i^j| \le p+q \le 4\sqrt{k} \log k$. Thus $(\bigcap_{\mu=1}^q N_{T'}^{\star_\mu}(b_\mu) \cap A) \setminus Y_i^j \ne \emptyset$. We can hence choose some $y \in (\bigcap_{\mu=1}^q N_{T'}^{\star_\mu}(b_\mu) \cap A) \setminus Y_i^j$ and define $Y_i^{j+1} = Y_i^j \cup \{y\}$. By definition, $Y_i^{j+1}$ is obtained from $Y_i^j$ by adding one vertex in $A \setminus Y_i^j$. In order to see that the last property holds, let $\mu \in [q]$. If $\max\{\mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b) \mid b \in B_i\} = d_{\mathrm{Inv}(T';Y_i^j)}^{-}(b_\mu) - k$, we have $\star_\mu = -$ and hence $y \in N_{\mathrm{Inv}(T';Y_i^j)}^{-}(b_\mu)$. As $d_{\mathrm{Inv}(T';Y_i^j)}^{-}(b_\mu) - k > 0$, we obtain $\mathrm{def}_{\mathrm{Inv}(T';Y_i^{j+1})}(b_\mu) = d_{\mathrm{Inv}(T';Y_i^{j+1})}^{-}(b_\mu) - k = d_{\mathrm{Inv}(T';Y_i^j)}^{-}(b_\mu) - k - 1 = p - j - 1 = p - (j+1)$. Similarly, if $\max\{\mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b) \mid b \in B_i\} = k - d_{\mathrm{Inv}(T';Y_i^j)}^{-}(b_\mu)$, then $\mathrm{def}_{\mathrm{Inv}(T';Y_i^{j+1})}(b) = p - (j+1)$. Otherwise, let $b' \in B$ with $\mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b') = p-j$. As $\mathrm{def}_{T'}(b_\mu) \equiv \mathrm{def}_{T'}(b') \mod 2$, we have $\mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b_\mu) \equiv \mathrm{def}_{T'}(b_\mu) + |Y_i^j| - 1 \equiv \mathrm{def}_{T'}(b') + |Y_i^j| - 1 \equiv \mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b') \mod 2$, hence $\mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b_\mu) \le \mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b') - 2$. This yields $\mathrm{def}_{\mathrm{Inv}(T';Y_i^{j+1})}(b_\mu) \le \mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b_\mu) + 1 \le \mathrm{def}_{\mathrm{Inv}(T';Y_i^j)}(b') - 2 + 1 = p - (j+1)$. $\diamond$

Let $T'' = \mathrm{Inv}(T'; (Y_1, \dots, Y_t))$. Observe that by definition of the sets $Y_i$, we have $\mathrm{def}_{T''}(b) = 0$ for all $b \in \bigcup_{i=1}^t B_i$. As $|\bigcup_{i=1}^t B_i| = qt \le \frac{2}{3}k$, we obtain by Proposition 5.13 that there is a $k$-arc-strong tournament $T'''$ on $V(T)$ such that all the edges in $\mathrm{UG}(T)(\bigcup_{i=1}^t B_i) \cup \delta_{\mathrm{UG}(T)}(\bigcup_{i=1}^t B_i)$ have the same orientation in $T''$ and $T''$. Further, by Proposition 5.12, there is a collection of $r = |V(T) \setminus \bigcup_{i=1}^t B_i| - 1$ subsets $Z_1, \dots, Z_r$ of $V(T) \setminus \bigcup_{i=1}^t B_i$ such that $\mathrm{Inv}(T''\langle V(T) \setminus \bigcup_{i=1}^t B_i\rangle; Z_1, \dots, Z_r) = T'''\langle V(T) \setminus \bigcup_{i=1}^t B_i\rangle$. We obtain that $\mathrm{Inv}(T; X_1, \dots, X_{q^*}, Y_1, \dots, Y_t, Z_1, \dots, Z_r) = \mathrm{Inv}(T'; Y_1, \dots, Y_t, Z_1, \dots, Z_r) = \mathrm{Inv}(T''; Z_1, \dots, Z_r) = T''$. As $T'''$ is $k$-arc-strong, we have $\mathrm{sinv}'_k(T) \le q^* + t + r$. Now $q^* = \lceil \log^2 k \rceil$, $t \le \frac{2k}{3q} = \frac{2k}{3\lceil \frac{1}{4} \log k \rceil}$, and $r = |V(T)| - |\bigcup_{i=1}^t B_i| - 1 \le 2k - (\frac{2}{3}k - q) = \frac{4}{3}k + q = \frac{4}{3}k + \lceil \frac{1}{4} \log k \rceil$ by Claim 5.15.1. Thus $\mathrm{sinv}'_k(T) \le \frac{4}{3}k + \lceil \log^2 k \rceil + \lceil \frac{1}{4} \log k \rceil + \frac{2k}{3\lceil \frac{1}{4} \log k \rceil} \le \frac{4}{3}k + \epsilon k$. $\square$

In the following lemmas, we show that the probability of each of $E_1$, $E_2$ and $E_3$ is small.

**Lemma 5.16.** $\mathrm{Pr}(E_1) < \frac{1}{3}$.

*Proof.* Let $b \in B$. We first bound the probability that $\vec{b} = \vec{0}$. Due to the independent and uniform choice of $(X_1, \dots, X_{q^*})$, we have $\mathrm{Pr}[\vec{b} = \vec{0}] = 2^{-q^*} \le 2^{-2\log k} = \frac{1}{k^2}$.

Now suppose that $\vec{b} \ne \vec{0}$. Once $\vec{b}$ has been revealed, for every $v \in V(T)$, let $\Gamma_v$ be a random variable which is 1 if $T'$ contains the arc $bv$ and 0 otherwise and let $\Gamma = \sum_{v \in V(T-b)} \Gamma_v$. Observe that, due to the independent and uniform choice of $(X_1, \dots, X_{q^*})$, we have $\mathrm{Pr}(\Gamma_v = 1) = \frac{1}{2}$ for all $v \in V(T-b)$ and the $\Gamma_v$ are independent. This yields that $\Gamma \sim \mathrm{Bin}(2k, \frac{1}{2})$. Further, observe that $\mathrm{def}_{T'}(b) \le 2\sqrt{k} \log k$ if and only if $k - 2\sqrt{k} \log k \le \Gamma \le k + 2\sqrt{k} \log k$. By Chernoff's Bound (Proposition 2.6), we obtain

$$ \begin{aligned} \mathrm{Pr} \left[ \Gamma < k - 2\sqrt{k} \log k \right] & \le \mathrm{Pr} \left[ \Gamma < \left( 1 - \frac{2\sqrt{k} \log k}{k} \right) k \right] \\ & \le \exp \left( - \frac{4k \log^2 k}{2k^2} k \right) \\ & \le \exp(-2 \log k) \\ & \le \exp(-2 \ln k) \\ & = \frac{1}{k^2}. \end{aligned} $$
Similarly, since $2k - \Gamma \sim \text{Bin}(2k, \frac{1}{2})$, we obtain that $\text{Pr}[\Gamma > k + 2\sqrt{k} \log k] \le \frac{1}{k^2}$. This yields that

$$
\begin{align*}
\Pr[\text{def}_{T'}(b) > 2\sqrt{k} \log k]
&= \Pr[\vec{b} = \vec{0}] \cdot \Pr[\text{def}_{T'}(b) > 2\sqrt{k} \log k \mid \vec{b} = \vec{0}] + \Pr[\vec{b} \neq \vec{0}] \cdot \Pr[\text{def}_{T'}(b) > 2\sqrt{k} \log k \mid \vec{b} \neq \vec{0}] \\
&\le \Pr[\vec{b} = \vec{0}] + \Pr[\Gamma < k - 2\sqrt{k} \log k \mid \vec{b} \neq \vec{0}] + \Pr[\Gamma > k + 2\sqrt{k} \log k \mid \vec{b} \neq \vec{0}] \\
&\le \frac{3}{k^2}.
\end{align*}
$$

As there are $k+1$ vertices contained in $B$, by the Union Bound (Proposition 2.5), $\text{Pr}(E_1) \le (k+1) \frac{3}{k^2} < \frac{1}{3}$, as $k \ge 10$. $\square$

**Lemma 5.17.** $\text{Pr}(E_2) < \frac{1}{3}$.

*Proof.* Let $b_1, \dots, b_q \in B$. Recall that $\vec{b}_1, \dots, \vec{b}_q$ are independent and uniformly distributed. For $i \in [q]$, observe that if $\vec{b}_1, \dots, \vec{b}_i$ are linearly independent, they span a vector space containing $2^i$ elements. Hence

$$
\begin{align*}
\Pr[\vec{b}_1, \dots, \vec{b}_q \text{ linearly dependent}] &= \sum_{i=1}^{q} \Pr[\vec{b}_1, \dots, \vec{b}_i \text{ linearly dependent} \mid \vec{b}_1, \dots, \vec{b}_{i-1} \text{ linearly independent}] \\
&\quad \times \Pr[\vec{b}_1, \dots, \vec{b}_{i-1} \text{ linearly independent}] \\
&\le \sum_{i=1}^{q} \Pr[\vec{b}_1, \dots, \vec{b}_i \text{ linearly dependent} \mid \vec{b}_1, \dots, \vec{b}_{i-1} \text{ linearly independent}] \\
&= \sum_{i=1}^{q} \frac{2^{i-1}}{2^{q^*}} \\
&\le \frac{2^q}{2^{q^*}} \\
&\le 2^{-2 \log(k)q} \quad \text{because } q^* \ge \log^2 k \ge 3 \log(k)q \ge 2 \log(k)q + q \\
&= k^{-2q}.
\end{align*}
$$

Observe that there are $\binom{k+1}{q}$ possibilities to choose $b_1, \dots, b_q$. Hence the Union Bound (Proposition 2.5) yields $\text{Pr}(E_2) \le \binom{k+1}{q}k^{-2q} \le (2k)^q k^{-2q} = \left(\frac{2}{k}\right)^q < \frac{1}{3}$ as $q \ge 1$ and $k \ge 7$. $\square$

**Lemma 5.18.** $\text{Pr}(E_3) < \frac{1}{3}$.

*Proof.* Let $b_1, \dots, b_q \in B$ such that $\vec{b}_1, \dots, \vec{b}_q$ are linearly independent and let $(\star_1, \dots, \star_q) \in \{+, -\}^q$. Once $\vec{b}_1, \dots, \vec{b}_q$ revealed, for every $a \in A$, let $\Gamma_a$ be a random variable that is 1 if $a \in \bigcap_{i=1}^q N_{T'}^*(b_i)$ and 0 otherwise and let $\Gamma = \sum_{a \in A} \Gamma_a$. Observe that, due to the independent and uniform choice of $(X_1, \dots, X_{q^*})$ and by Proposition 5.11, we have that $\text{Pr}[\Gamma_a = 1] = \frac{1}{2^q}$ for all $a \in A$ and that the $\Gamma_a$ are independent. This yields that $\Gamma \sim \text{Bin}(k, \frac{1}{2^q})$. Further observe that $\Gamma = |\bigcap_{i=1}^q N_{T'}^*(b_i) \cap A|$. Now, since $10 \log k \le k^{\frac{1}{8}}$ and $q = \lceil \frac{1}{4} \log k \rceil \le \frac{3}{8} \log k$, we obtain $5\sqrt{k} \log k \le \frac{1}{2}k^{\frac{5}{8}} = \frac{1}{2}k2^{-\frac{3}{8}} \log k \le \frac{1}{2}k2^{-q}$. By Chernoff's Bound (Proposition 2.6), we obtain

$$
\begin{align*}
\Pr[\Gamma < 5\sqrt{k} \log k] &\le \Pr \left[ \Gamma < \left(1 - \frac{1}{2}\right) k 2^{-q} \right] \\
&\le \exp \left(-\frac{1}{8} k 2^{-q} \right) \\
&\le \exp \left(-\frac{1}{8} \sqrt{k} \right) \\
&\le \exp(-2q \log k) \quad \text{because } \sqrt{k} \ge 16 \log k \lceil \frac{1}{4} \log k \rceil \\
&\le \exp(-2q \ln k) \\
&= k^{-2q}.
\end{align*}
$$
Observe that there are $\binom{k+1}{q}$ possibilities to choose $b_1, \dots, b_q$ and for each of those, there are $2^q$ possibilities to choose $(\star_1, \dots, \star_q)$. Hence the Union Bound (Proposition 2.5) yields $\Pr(E_3) \le \binom{k+1}{q} 2^q k^{-2q} \le (2k)^q 2^q k^{-2q} = \binom{4}{k}^q < \frac{1}{3}$, as $q \ge 1$ and $k \ge 13$. $\square$

We are now ready to conclude the proof of Theorem 5.14. By Lemmas 5.16, 5.17 and 5.18 and the Union Bound (Proposition 2.5), we obtain that, with positive probability, none of $E_1, E_2$ and $E_3$ occur. Hence the statement follows from Lemma 5.15. $\square$

### 5.4.3 Bigger tournaments

We now show how to extend this result to larger tournaments and derive Theorem 1.8 from Theorem 5.14.

**Theorem 1.8.** $M'_k \le \frac{4}{3}k + o(k)$.

*Proof.* Let $\epsilon > 0$. We shall prove that there is an integer $k^*$ such that for every $k \ge k^*$ and for every tournament $T$ on at least $2k+1$ vertices, we have $\sinv'_k(T) \le (\frac{4}{3} + \epsilon)k$.

By Theorem 5.14, there is an integer $k_0$ such that for every $k \ge k_0$ and for every tournament $T$ on at least $2k+1$ vertices, we have $\sinv'_k(T) \le (\frac{4}{3} + \frac{\epsilon}{2})k$. Further, let $k_1$ be an integer such that $\frac{\epsilon}{2}k \ge 6 \log k\sqrt{k} + 1$, $\sqrt{k} \ge 3 \log k$ and $\log k \ge 5$ hold for all $k \ge k_1$. Set $k^* = \max\{k_0, k_1\}$.

We now fix an integer $k \ge k^*$ and prove that for every tournament $T$ on $n \ge 2k+1$ vertices, we have $\sinv'_k(T) \le (\frac{4}{3} + \frac{\epsilon}{2})k + \min\{n - (2k+1), 6 \log k\sqrt{k} + 1\}$ from which the statement follows immediately. Suppose that $T$ is a tournament that does not satisfy this statement and whose number $n$ of vertices is minimum with respect to this property.

**Case 1.** $n > 4k - 2$.

By Proposition 2.2, there is some $v \in V(T)$ with $\min\{d_T^+(v), d_T^-(v)\} \ge k$. By the minimality of $T$, there is a collection $\mathcal{X}$ of $(\frac{4}{3} + \frac{\epsilon}{2})k + \min\{(n-1) - (2k+1), 6 \log k\sqrt{k} + 1\}$ subsets of $V(T - v)$ such that $\mathrm{Inv}(T - v; \mathcal{X})$ is $k$-arc-strong. By Proposition 2.1, we obtain that $\mathrm{Inv}(T; \mathcal{X})$ is $k$-arc-strong. As $(\frac{4}{3} + \frac{\epsilon}{2})k + \min\{(n-1) - (2k+1), 6 \log k\sqrt{k} + 1\} \le (\frac{4}{3} + \frac{\epsilon}{2})k + \min\{n - (2k+1), 6 \log k\sqrt{k} + 1\}$, we obtain a contradiction.

**Case 2.** $2k+1+6 \log k\sqrt{k} < n \le 4k-2$.

Let $A$ be an arbitrary subset of $V(T)$ of size $2k+1+|6\sqrt{k}\log k|$ and let $B = V(T) \setminus A$. We now choose a subset $X$ of $A$ uniformly at random and let $T' = \mathrm{Inv}(T; B \cup X)$. Now consider some $b \in B$. For every $a \in A$, let $\Gamma_a$ be the probability that $ab \in A(T')$ and observe that $\Gamma = \sum_{a \in A} \Gamma_a$ is exactly $|N_{T'}(b) \cap A|$. Due to the uniform choice of $X$, we have $\mathrm{Pr}[ab \in A(T)] = \frac{1}{2}$ and that the $\Gamma_a$ are independent. This yields $\Gamma \sim \mathrm{Bin}(2k+1 + \lfloor 6\sqrt{k}\log k \rfloor, \frac{1}{2})$. By Chernoff's Bound (Proposition 2.6), we obtain

$$ \begin{aligned} \mathrm{Pr}[\Gamma < k] &\le \mathrm{Pr} \left[ \Gamma < \left( 1 - \frac{\sqrt{k} \log k}{k} \right) \frac{1}{2} \left( 2k + 1 + \lfloor 6\sqrt{k} \log k \rfloor \right) \right] \\ &\le \exp(-\log^2(k)/2) \\ &\le \exp(-2 \log k) \quad \text{because } k \ge 16 \\ &\le \exp(-2 \ln k) \\ &\stackrel{\text{}}{=} \frac{1}{k^2}. \end{aligned} $$

Similarly, we obtain $\mathrm{Pr}[|N_{T'}^+(b) \cap A| < k] \le \frac{1}{k^2}$. As $B$ contains at most $(4k-3) - (2k+1 + \lfloor 6\sqrt{k}\log k \rfloor) \le 2k$ elements, the Union Bound (Proposition 2.5) yields that the probability that there is at least one $b \in B$ with $\min\{|N_{T'}^-(b) \cap A|, |N_{T'}^+(b) \cap A|\} \le k$ is at most $\frac{2}{k^2} 2k = \frac{4}{k} < 1$, as $k \ge 5$. Hence, with positive probability, we have $\min\{|N_{T'}^-(b) \cap A|, |N_{T'}^+(b) \cap A|\} \ge k$ for all $b \in B$. Thus there is $X_0$ such that every vertex of $B$ has at least $k$ in-neighbours and $k$ out-neighbours in $A$ in the tournament $T'_0 = \mathrm{Inv}(T; B \cup X_0)$. Further, by the minimality of $T$ and as $|V(T_0)| - 2k + 1 = 6\sqrt{k}\log k$, there is a collection $\mathcal{X}$ of $\sinv'_k(T_0\langle A\rangle) \le (\frac{4}{3} + \frac{\epsilon}{2})k + \lfloor 6 \log k\sqrt{k} \rfloor$ sets such that $\mathrm{Inv}(T'_0\langle A\rangle; \mathcal{X})$ is $k$-arc-strong. Hence, by Proposition 2.1, we obtain that $\mathrm{Inv}(T; \{X_0\} \cup \mathcal{X})$ is $k$-arc-strong, a contradiction.
**Case 3.** $2k+2 \le n \le 2k+6\sqrt{k}\log k$.

Let $v \in V(T)$ be an arbitrary vertex. We can then find a set $X \subseteq V(T)$ such that for $T' = \text{Inv}(T; X)$, we have $\min\{d_{T'}^+(v), d_{T'}^-(v)\} \ge k$. Further, by the minimality of $T$, there is a collection $\mathcal{X}$ of $\text{sinv}_k'(T' - v) \le (\frac{4}{3} + \frac{\epsilon}{2})k + n - (2k+1) - 1$ sets such that $\text{Inv}(T' - v; \mathcal{X})$ is $k$-arc-strong. Hence by Proposition 2.1, we obtain that $\text{Inv}(T; \{X\} \cup \mathcal{X})$ is $k$-arc-strong, a contradiction. $\square$

# 6 Upper bounds on $m_k(n)$

In this section, we prove several results showing that tournaments on significantly more than $2k$ vertices can be made $k$-strong by a small number of inversions. More precisely, in Subsection 6.1 we prove Theorem 6.1 and Proposition 1.13, in Subsection 6.2 we prove Theorem 1.10, in Subsection 6.3 we prove Theorem 1.14, and in Subsection 6.4, we prove Theorem 1.15.

## 6.1 First upper bounds on $m_k(n)$

In this subsection, we first establish that, for every fixed $k$, every tournament which is sufficiently large in comparison to $k$ can be made $k$-strong by a single inversion. While this result (Theorem 6.1) is clearly weaker than Theorem 1.10, it justifies some of the notation used later on, and may serve as a warm-up exercise of the more involved proof of Theorem 1.10.

**Theorem 6.1.** Let $n, k$ be positive integers and let $T$ be a tournament on $n$ vertices. If $n \ge (2k-1)2^{2k}$, then $\text{sinv}_k'(T) \le \text{sinv}_k(T) \le 1$.

*Proof.* Let $T$ be a tournament of order $n \ge (2k-1)2^{2k}$.

It is easy and well-known that if $D$ is an acyclic digraph, $x$ a source in $D$, and $D-x$ is contained (as a subdigraph) in every tournament of order $n$, then $D$ is contained (as a subdigraph) in every tournament of order $2n$. An easy induction yields that $T$ contains three sets $A_1, A_2, A_3$ such that $A_1 \Rightarrow (A_2 \cup A_3)$ and $A_2 \Rightarrow A_3$ with $|A_1| = |A_3| = k$ and $|A_2| = 2k-1$. Set $A = A_1 \cup A_2 \cup A_3$. Let $I$ be the set of vertices in $V(T) \setminus A$ that have either fewer than $k$ out-neighbours in $A$ or fewer than $k$ in-neighbours in $A$. Let $X = A_1 \cup A_3 \cup I$. Let us prove that $T' = \text{Inv}(T; X)$ is $k$-strong.

In $T'$, we have $A_1 \Rightarrow A_2 \Rightarrow A_3 \Rightarrow A_1$. Since the three sets $A_1, A_2$, and $A_3$ have size at least $k$, the tournament $T'\langle A \rangle$ is $k$-strong. Now consider a vertex $v$ in $V(T) \setminus A$. If $v \notin I$, then no arcs incident to $v$ have been reversed so its in- and out-degree have been unchanged and are at least $k$ by definition of $I$. If $v \in I$, then all the arcs between $v$ and $A_1 \cup A_3$ have been reversed and those between $v$ and $A_2$ are unchanged. If $v$ has fewer than $k$ out-neighbours in $A$ in $T$, then $|N_T^+(v) \cap A| \ge |N_T^-(v) \cap (A_1 \cup A_3)| \ge 2k - d_T^+(v) \ge k$, and $|N_T^-(v) \cap A| \ge |N_T^-(v) \cap A_2| \ge 2k - 1 - d_T^+(v) \ge k$. Similarly, if $v$ has fewer than $k$ in-neighbours in $A$ in $T$, then $|N_{T'}^+(v) \cap A| \ge k$ and $|N_{T'}^-(v) \cap A| \ge k$. Thus, by Lemma 2.1, $T'$ is $k$-strong. Hence $\text{sinv}_k(T) \le 1$. $\square$

## 6.2 Linear upper and lower bounds on $N_k(1)$

In this subsection, we shall prove Theorem 1.10 which states that $N_k(1) \le 19k - 2$. To prove it we need some preliminaries.

For a digraph $D$, let $\sigma = (v_1, v_2, \dots, v_n)$ be an ordering of the vertices of $D$. An arc $v_iv_j$ is **forward** (according to $\sigma$) if $i < j$ and **backward** (according to $\sigma$) if $j < i$. A **median order** of $D$ is an ordering of the vertices of $D$ with the maximum number of forward arcs, or, equivalently, the minimum number of backward arcs.

Let us note basic well-known properties of median orders of tournaments (the “feedback property” in [HT00]).

**Lemma 6.2.** Let $T$ be a tournament and $(v_1, v_2, \dots, v_n)$ a median order of $T$. Then, for any two indices $i, j$ with $1 \le i < j \le n$:

(M1) $(v_i, v_{i+1}, \dots, v_j)$ is a median order of the induced subtournament $T\langle\{v_i, v_{i+1}, \dots, v_j\}\rangle$.
(M2) the vertex $v_i$ is an in-neighbour of at least half of the vertices $v_{i+1}, v_{i+2}, \dots, v_j$, and the vertex $v_j$ is an out-neighbours of at least half of the vertices $v_i, v_{i+1}, \dots, v_{j-1}$. In particular, for every $1 \le i \le n-1$, $v_iv_{i+1} \in A(T)$.

Given two vertices $u, v$ of some digraph $D$, we say that $v$ is **reachable** from $u$ if $D$ contains a directed uv-path. For $v \in V(D)$, we use $R_D^+(v)$ (resp. $R_D^-(v)$) for the set of vertices which are reachable from $v$ in $D$ (resp. from which $v$ is reachable in $D$). Note that $v \in R_D^+(v) \cap R_D^-(v)$.

**Lemma 6.3.** Let $T$ be a tournament with median order $(v_1, v_2, \dots, v_n)$. Let $F$ be a subset of vertices such that $v_1 \notin F$. Then $|R_{T-F}^+(v_1)| \ge n - 2|F|$.

*Proof.* We prove the result by induction on $n + |F|$, the result holding trivially by (M2) if $|F| = 0$.

If all the out-neighbours of $v_1$ in $T$ are in $|F|$, then by (M2), $|N_T^-(v_1)| \le |N_T^+(v_1)| \le |F|$. Hence $n-1 \le 2|F|$, and the result holds. Henceforth we may assume that $v_1$ has an out-neighbour not in $F$. Let $i_0$ be the smallest index of such a vertex. Let $T_0 = T\langle\{v_1, \dots, v_{i_0-1}\}\rangle$, $T_1 = T\langle\{v_{i_0}, \dots, v_n\}\rangle$, $F_0 = F \cap V(T_0)$ and $F_1 = F \cap V(T_1)$. By (M1), $(v_1, v_2, \dots, v_{i_0-1})$ is a median order of $T_0$ and $(v_{i_0}, \dots, v_n)$ is a median order of $T_1$. By definition of $i_0$, all out-neighbours of $v_1$ in $T_0$ are in $F_0$. Thus, as above, we have $i_0 - 2 \le 2|F_0|$. By the induction hypothesis, $|R_{T_1-F_1}^+(v_{i_0})| \ge n - i_0 + 1 - 2|F_1|$. Now $R_{T_1-F_1}^+(v_{i_0}) \cup \{v_1\} \subseteq R_{T-F}^+(v_1)$. Hence

$$|R_{T-F}^+(v_1)| \ge |R_{T_1-F_1}^+(v_{i_0})| + 1 \ge n - i_0 + 2 - 2|F_1| \ge n - 2|F_0| - 2|F_1| = n - 2|F|.$$

□

We are now ready to prove the main lemma of the proof of Theorem 1.10.

**Lemma 6.4.** Let $k$ be a positive integer, let $T$ be a tournament on $12k$ vertices and let $(A, B)$ be a bipartition of $V(T)$ such that $|A| = |B| = 6k$. Then there is a set $X \subseteq V(T)$ with $|X \cap A| = |X \cap B| = 2k$ such that for $T' = \text{Inv}(T; X)$ and for any $Y \subseteq V(T)$ with $|Y| \le k-1$, we have that $T' - Y$ contains a directed path from $a$ to $B \setminus Y$ for every $a \in A \setminus Y$, and $T' - Y$ contains a directed path from $A \setminus Y$ to $b$ for every $b \in B \setminus Y$.

*Proof.* Let $(a_1, \dots, a_{6k})$ be a median order of $T\langle A\rangle$ and let $(b_1, \dots, b_{6k})$ be a median order of $T\langle B\rangle$. Let $A_0$ be the set of vertices in $\{a_{4k+1}, \dots, a_{6k}\}$ which have fewer than $k$ out-neighbours in $B$ in $T$. Further, let $A_1 = \{a_1, \dots, a_{2k-|A_0|}\}$. Observe that $|A_0 \cup A_1| = |A_0| + |A_1| = 2k$. Similarly, let $B_0$ be the set of vertices in $\{b_1, \dots, b_{2k}\}$ that have fewer than $k$ in-neighbours in $A$ and let $B_1 = \{b_{4k+|B_0|+1}, \dots, b_{6k}\}$. Observe that $|B_0 \cup B_1| = |B_0| + |B_1| = 2k$. Let $X = A_0 \cup A_1 \cup B_0 \cup B_1$ and let $T' = \text{Inv}(T; X)$. Consider any $Y \subseteq V(T)$ with $|Y| \le k-1$. In order show that $T'$ has the desired properties, by symmetry, it suffices to prove that $T' - Y$ contains a directed path from $a$ to $B \setminus Y$ for every $a \in A \setminus Y$. Suppose by contradiction that this is not true. Then there is a largest integer $i \in [6k]$ such that $a_i \in A \setminus Y$ and $T' - Y$ does not contain a directed path from $a_i$ to $B \setminus Y$. We will distinguish several cases.

**Case 1.** $i \in \{4k+1, \dots, 6k\}$ and $a_i \in A \setminus A_0$.

In this case, by the choice of $A_0$, we have

$$ \begin{aligned} |(N_{T'}^+(a_i) \cap B) \setminus Y| &\ge |N_{T'}^+(a_i) \cap B| - |Y| \\ &= |N_{T'}^+(a_i) \cap B| - |Y| \\ &\ge k - (k-1) \\ &= 1, \end{aligned} $$

so $a_i$ has an out-neighbour in $B \setminus Y$ in $T' - Y$, a contradiction.

**Case 2.** $i \in \{4k+1, \dots, 6k\}$ and $a_i \in A_0$.
In this case, by the choice of $A_0$, we have

$$
\begin{align*}
|(N_{T'}^{+}(a_i) \cap B) \setminus Y| &\ge |N_{T'}^{+}(a_i) \cap B| - |Y| \\
&\ge |N_{T'}^{+}(a_i) \cap (B_0 \cup B_1)| - |Y| \\
&= |B_0 \cup B_1| - |N_{T'}^{-}(a_i) \cap (B_0 \cup B_1)| - |Y| \\
&= |B_0 \cup B_1| - |N_{T}^{+}(a_i) \cap (B_0 \cup B_1)| - |Y| \\
&\ge |B_0 \cup B_1| - |N_{T}^{+}(a_i) \cap B| - |Y| \\
&\ge 2k - (k-1) - (k-1) \\
&= 2,
\end{align*}
$$

so $a_i$ has an out-neighbour in $B \setminus Y$ in $T' - Y$, a contradiction.

**Case 3.** $i \in \{2k - |A_0| + 1, \dots, 4k\}$.

As $(a_1, \dots, a_{6k})$ is a median order of $T\langle A\rangle$, and by (M2) applied to $T\langle A\rangle$, we have

$$
\begin{align*}
|(N_{T'}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{6k}\}) \setminus Y| &\ge |N_{T'}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{6k}\}| - |Y| \\
&= |N_{T}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{6k}\}| - |Y| \\
&\ge \frac{1}{2}|\{a_{i+1}, \dots, a_{6k}\}| - |Y| \\
&\ge \frac{1}{2}(6k - i) - (k - 1) \\
&= 2k + 1 - \frac{i}{2} \\
&\ge 2k + 1 - 2k \\
&= 1.
\end{align*}
$$

Hence there is some $j > i$ such that $a_j \in A \setminus Y$ and $T' - Y$ contains the arc $a_i a_j$. By the maximality of $i$, there is a directed path from $a_j$ to $B \setminus Y$ in $T' - Y$. Hence $T' - Y$ also contains a directed path from $a_i$ to $B \setminus Y$, a contradiction.

□

**Case 4.** $i \in \{1, \dots, 2k - |A_0|\}$.

As $(a_1, \dots, a_{6k})$ is a median order of $T\langle A\rangle$ and by (M2) applied to $T\langle A\rangle$, we have

$$
\begin{align*}
|(N_{T'}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{6k}\}) \setminus Y| &\ge |N_{T'}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{6k}\}| - |Y| \\
&\ge |N_{T}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{6k}\}| - |(A_0 \cup A_1) \cap \{a_{i+1}, \dots, a_{6k}\}| - |Y| \\
&\ge \frac{1}{2}|\{a_{i+1}, \dots, a_{6k}\}| - |(A_0 \cup A_1) \cap \{a_{i+1}, \dots, a_{6k}\}| - |Y| \\
&\ge \frac{1}{2}(6k - i) - (2k - i) - (k - 1) \\
&= \frac{i}{2} + 1 \\
&\ge 1.
\end{align*}
$$

Hence there is some $j > i$ such that $a_j \in A \setminus Y$ and $T' - Y$ contains the arc $a_i a_j$. By the maximality of $i$, there is a directed path from $a_j$ to $B \setminus Y$ in $T' - Y$. Hence $T' - Y$ also contains a directed path from $a_i$ to $B \setminus Y$, a contradiction. $\square$

We are now ready to prove Theorem 1.10, which states $N_k(1) \le 19k - 2$.

*Proof of Theorem 1.10.* Assume $n \ge 19k - 2$. Let $(v_1, \dots, v_n)$ be a median order of $T$. Let $B = \{v_1, \dots, v_{6k}\}$, $A = \{v_{n-6k+1}, \dots, v_n\}$ and $C = V(T) \setminus (A \cup B)$. We have $|C| \ge 7k - 2$. By Lemma 6.4, applied to $T\langle A \cup B\rangle$, there is a subset $X$ of $A \cup B$ such that, for $T_1 = \text{Inv}(T; X)$, we have

$$ (i) |X \cap B| = |X \cap A| = 2k; $$
(ii) for any $Y \subseteq V(T)$ with $|Y| \le k-1$, $T_1 - Y$ contains a directed path from $a$ to $B \setminus Y$ for every $a \in A \setminus Y$;

(iii) for any $Y \subseteq V(T)$ with $|Y| \le k-1$, $T_1 - Y$ contains a directed path from $A \setminus Y$ to $b$ for every $b \in B \setminus Y$.

Let us now prove that $T_1$ is $k$-strong, which implies $\text{inv}_k(T) \le 1$. Let $F$ be a set of at most $k-1$ vertices of $T_1$. We first need the following intermediate result.

**Claim 6.4.1.** Let $b \in B \setminus F$ and $a \in A \setminus F$. Then $T_1 - F$ contains a directed path from $b$ to $a$.

*Proof of claim.* By construction, there is some $i \in \{1, \dots, 6k\}$ such that $b = v_i$. Let $S = ((X \cap B) \cup F) \cap \{v_{i+1}, \dots, v_{n-6k}\}$ and let $T' = T(\{v_i, \dots, v_{n-6k}\})$. By (M2), every vertex in $S$ and every vertex in $C \setminus F$ is reachable from $b$ in $T'$. On the other hand, there is obviously no vertex in $S$ reachable from $b$ in $T' - S$. Further, by (M1), $(v_i, \dots, v_{n-6k})$ is a median order of $T'$. By Lemma 6.3 applied to $T'$ and $S$, this yields

$$ 
\begin{aligned}
2|S| &\ge |R_{T'}^{+}(b)| - |R_{T'_{-S}}^{+}(b)| \\
&= |R_{T'}^{+}(b) \cap B| - |R_{T'_{-S}}^{+}(b) \cap B| \\
&\quad + |R_{T'}^{+}(b) \cap (C \cap F)| - |R_{T'_{-S}}^{+}(b) \cap (C \cap F)| \\
&\quad + |R_{T'}^{+}(b) \cap (C \setminus F)| - |R_{T'_{-S}}^{+}(b) \cap (C \setminus F)| \\
&\ge |S| + |C \setminus F| - |R_{T'_{-S}}^{+}(b) \cap (C \setminus F)|.
\end{aligned}
$$

For every $v \in C \setminus F$, if $v$ is reachable from $b$ in $T' - S$, then $v$ is clearly reachable from $b$ in $T_1 - F$. Since $|X \cap B| \le 2k$ and $|F| \le k-1$, we obtain

$$ 
\begin{aligned}
|R_{T_1-F}^{+}(b) \cap (C \setminus F)| &\ge |R_{T'_{-S}}^{+}(b) \cap (C \setminus F)| \\
&\ge |C \setminus F| - |S| \\
&\ge |C \setminus F| - (|X \cap B| + |F|) \\
&\ge |C \setminus F| - (2k + (k-1)) \\
&= |C \setminus F| - (3k - 1).
\end{aligned}
$$

A similar argument shows that $|R_{T_1-F}^{-}(a) \cap (C \setminus F)| \ge |C \setminus F| - (3k-1)$. As $|C| \ge n - 12k \ge 7k-2$, we obtain

$$ 
\begin{aligned}
|(R_{T_1-F}^{+}(b) \cap (C \setminus F)) \cap (R_{T_1-F}^{-}(a) \cap (C \setminus F))| &= |R_{T_1-F}^{+}(b) \cap (C \setminus F)| + |R_{T_1-F}^{-}(a) \cap (C \setminus F)| \\
&\quad - |(R_{T_1-F}^{+}(b) \cap (C \setminus F)) \cup (R_{T_1-F}^{-}(a) \cap (C \setminus F))| \\
&\ge |R_{T_1-F}^{+}(b) \cap (C \setminus F)| + |R_{T_1-F}^{-}(a) \cap (C \setminus F)| - |C \setminus F| \\
&\ge 2(|C \setminus F| - (3k-1)) - |C \setminus F| \\
&= |C \setminus F| - 2(3k-1) \\
&\ge |C| - |F| - (6k-2) \\
&\ge (7k-2) - (k-1) - (6k-2) \\
&= 1.
\end{aligned}
$$

Hence there is a vertex $v^* \in \{v_{6k+1}, \dots, v_{n-6k}\} \cap (R_{T_1-F}^{+}(b) \cap (C \setminus F)) \cap (R_{T_1-F}^{-}(a) \cap (C \setminus F))$. By definition, $T_1 - F$ contains a directed path from $b$ to $v^*$ and a directed path from $v^*$ to $a$. Hence $T_1 - F$ contains a directed path from $b$ to $a$. $\diamond$

We are now ready to show that $T_1 - F$ is strong. Let $x$ and $y$ be two vertices in $T_1 - F$. It suffices to show that $y$ is reachable from $x$ in $T_1 - F$.

We first show that there is a path from $x$ to $B \setminus F$. Clearly, we may suppose that $x \in (A \cup C) \setminus F$. Then, since $|A| > 2|F|$, Lemma 6.3 implies that there is a vertex $x' \in A \setminus F$ reachable from $x$ in $T - F - B$, and so in $T_1 - F$. By (ii), there is a directed path from $x'$ to a vertex $u$ in $B \setminus F$ in $T_1 - F$. Hence
there is a directed path $P_x$ from $x$ to $u$ in $T_1 - F$. Similarly, by directional duality, in $T_1 - F$, there is a directed path $P_y$ from a vertex $w \in A \setminus F$ to $y$.

Finally, by Claim 6.4.1, there exists a path $Q$ from $u$ to $w$ in $T_1 - F$. Then $P_x Q P_y$ is a path from $x$ to $y$ in $T_1 - F$. This proves that $T_1 - F$ is strong. $\square$

Finally, we give the proof of Proposition 1.13, which states that $N_k(1) \ge 5k - 2$ and $N'_k(1) \ge 4k - 1$.

**Proof of Proposition 1.13.** Let $T_1$ be a tournament of order $5k - 3$ whose vertex set has a partition $(A, B, C)$ such that $T_1 \langle A \rangle$ and $T_1 \langle C \rangle$ are eulerian tournaments of order $2k - 1$, and $A \Rightarrow B \cup C$ and $B \Rightarrow C$. We shall prove that $\text{inv}_k(T_1) > 1$.

Assume for a contradiction that there is a set $X$ of vertices such that $T'_1 = \text{Inv}(T_1; X)$ is $k$-strong. Every vertex of $A$ (resp. $C$) has in-degree (resp. out-degree) $k - 1$ in $T_1$, and so belongs to $X$. Thus $A \cup C \subseteq X$, and so $C \Rightarrow A$ in $T'_1$. Hence $T'_1 - B$ is not strong. Since $|B| = k - 1$, $T'_1$ is not $k$-strong, a contradiction.

Now let $T_2$ be a tournament of order $4k - 2$ whose vertex set has a partition $(A, B)$ such that $T_2 \langle A \rangle$ and $T_2 \langle B \rangle$ are eulerian tournaments of order $2k - 1$, and $A \Rightarrow B$. We shall prove that $\text{inv}'_k(T_1) > 1$.

Assume for a contradiction that there is a set $X$ of vertices such that $T'_2 = \text{Inv}(T_2; X)$ is $k$-arc-strong. Every vertex of $A$ (resp. $B$) has in-degree (resp. out-degree) $k - 1$ in $T_2$, and so belongs to $X$. Thus $X = V(T_2)$, and so $T'_2$ is isomorphic to $T_2$. Hence $T'_2$ is not $k$-arc-strong, a contradiction. $\square$

## 6.3 Better upper bound on $N_k(3)$

This section is dedicated to the proof of Theorem 1.14. The structure is analogous to the proof of Theorem 1.10 in Section 6.2. First we show a result which is very similar to Lemma 6.4.

**Lemma 6.5.** Let $k$ be a positive integer, $T$ a tournament on $8k$ vertices and $(A, B)$ a bipartition of $V(T)$ such that $|A| = |B| = 4k$. There is a family $\mathcal{X}$ of three subsets of $V(T)$ such that the following hold with $T' = \text{Inv}(T; \mathcal{X})$.

(i) $T' \langle A \rangle = T \langle A \rangle$ and $T' \langle B \rangle = T \langle B \rangle$;

(ii) for any $Y \subseteq V(T)$ with $|Y| \le k - 1$, $T' - Y$ contains a directed path from $A$ to $B \setminus Y$ for every $a \in A \setminus Y$;

(iii) for any $Y \subseteq V(T)$ with $|Y| \le k - 1$, $T' - Y$ contains a directed path from $A \setminus Y$ to $b$ for every $b \in B \setminus Y$.

**Proof.** Let $(a_1, \dots, a_{4k})$ be a median order of $T \langle A \rangle$ and let $(b_1, \dots, b_{4k})$ be a median order of $T \langle B \rangle$. Let $A_0$ be the set of vertices in $\{a_{2k+1}, \dots, a_{4k}\}$ which have fewer than $k$ out-neighbours in $B$ in $T$. Further, let $A_1 = \{a_1, \dots, a_{2k-|A_0|}\}$. Observe that $|A_0 \cup A_1| = |A_0| + |A_1| = 2k$. Similarly, let $B_0$ be the set of vertices in $\{b_1, \dots, b_{2k}\}$ that have fewer than $k$ in-neighbours in $A$ and let $B_1 = \{b_{2k+|B_0|+1}, \dots, b_{4k}\}$. Observe that $|B_0 \cup B_1| = |B_0| + |B_1| = 2k$. Now let $X_1 = A_0 \cup A_1$, $X_2 = B_0 \cup B_1$, $X_3 = X_1 \cup X_2$, and $\mathcal{X} = (X_i)_{i \in [3]}$ Let $T' = \text{Inv}(T; \mathcal{X})$. Observe that $T'$ is obtained from $T$ by reversing the arcs between $X_1$ and $X_2$. In particular, (i) holds.

We only show (ii) as (iii) follows symmetrically. Let $Y \subseteq V(T)$ with $|Y| \le k - 1$. Suppose for the sake of a contradiction that (ii) does not hold. There is a largest integer $i \in [4k]$ such that $a_i \in A \setminus Y$ and $T' - Y$ does not contain a directed path from $a_i$ to $B \setminus Y$. We will distinguish several cases.

**Case 1.** $i \in \{2k + 1, \dots, 4k\}$ and $a_i \in A \setminus A_0$.

In this case, by the choice of $A_0$, we have

$$ \begin{align*} |(N_{T'}^{+}(a_i) \cap B) \setminus Y| &\ge |N_{T'}^{+}(a_i) \cap B| - |Y| \\ &= |N_{T'}^{+}(a_i) \cap B| - |Y| \\ &\ge k - (k - 1) \\ &= 1, \end{align*} $$

so $a_i$ has an out-neighbour in $B \setminus Y$ in $T' - Y$, a contradiction.
**Case 2.** $i \in \{2k+1, \dots, 4k\}$ and $a_i \in A_0$.

In this case, by the choice of $A_0$, we have

$$ 
\begin{aligned}
|(N_{T'}^{+}(a_i) \cap B) \setminus Y| &\ge |N_{T'}^{+}(a_i) \cap B| - |Y| \\
&\ge |N_{T'}^{+}(a_i) \cap (B_0 \cup B_1)| - |Y| \\
&= |B_0 \cup B_1| - |N_{T'}^{-}(a_i) \cap (B_0 \cup B_1)| - |Y| \\
&= |B_0 \cup B_1| - |N_{T'}^{+}(a_i) \cap (B_0 \cup B_1)| - |Y| \\
&\ge |B_0 \cup B_1| - |N_{T'}^{+}(a_i) \cap B| - |Y| \\
&\ge 2k - (k-1) - (k-1) \\
&= 2,
\end{aligned}
$$

so $a_i$ has an out-neighbour in $B \setminus Y$ in $T' - Y$, a contradiction.

**Case 3.** $i \in [2k]$.

As $(a_1, \dots, a_{4k})$ is a median order of $T\langle A\rangle = T'\langle A\rangle$, by (M2) we have

$$ 
\begin{aligned}
|(N_{T'}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{4k}\}) \setminus Y| &\ge |N_{T'}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{4k}\}| - |Y| \\
&= |N_{T'}^{+}(a_i) \cap \{a_{i+1}, \dots, a_{4k}\}| - |Y| \\
&\ge \frac{1}{2}\{|a_{i+1}, \dots, a_{4k}\}| - |Y| \\
&\ge \frac{1}{2}(4k - i) - (k - 1) \\
&= k + 1 - \frac{i}{2} \\
&\ge k + 1 - k \\
&= 1.
\end{aligned}
$$

Hence there is some $j > i$ such that $a_j \in A \setminus Y$ and $T' - Y$ contains the arc $a_ia_j$. By the maximality of $i$, there is a directed path from $a_j$ to $B \setminus Y$ in $T' - Y$. Hence $T' - Y$ also contains a directed path from $a_i$ to $B \setminus Y$, a contradiction. $\square$

We now prove the upper bound on $N_k(3)$, which we restate here.

**Theorem 1.14.** For any positive integer $k$, we have $N_k'(3) \le N_k(3) \le 11k - 2$.

*Proof.* Let $T$ be a tournament on $n \ge 11k - 2$ vertices. Let $(v_1, \dots, v_n)$ be a median order of $T$. Let $B = \{v_1, \dots, v_{4k}\}$, $A = \{v_{n-4k+1}, \dots, v_n\}$ and $C = V(T) \setminus (A \cup B)$. We have $|C| \ge 3k - 2$. By Lemma 6.5 applied to $T\langle A \cup B\rangle$, there is a family $\mathcal{X}$ of three subsets of $A \cup B$ such that for $T_1 = \text{Inv}(T; \mathcal{X})$ we have

(i) $T_1\langle A\rangle = T\langle A\rangle$ and $T_1\langle B\rangle = T\langle B\rangle$;

(ii) for any $Y \subseteq V(T)$ with $|Y| \le k - 1$, $T_1 - Y$ contains a directed path from $a$ to $B \setminus Y$ for every $a \in A \setminus Y$;

(iii) for any $Y \subseteq V(T)$ with $|Y| \le k - 1$, $T_1 - Y$ contains a directed path from $A \setminus Y$ to $b$ for every $b \in B \setminus Y$.

Let $T_1 = \text{Inv}(T; \mathcal{X})$. Let us now prove that $T_1$ is $k$-strong, which implies $\text{inv}_k(T) \le 3$. Note that $T\langle A \cup C\rangle$, as well as $T\langle B \cup C\rangle$ are unchanged by the inversions. Let $F$ be a set of at most $k-1$ vertices of $T_1$. Let us show that $T_1 - F$ is strong. Let $x$ and $y$ be two vertices in $T_1 - F$. It suffices to show that $y$ is reachable from $x$ in $T_1 - F$.

Let us first show that there is a vertex $u \in B \setminus F$ that is reachable from $x$ in $T_1 - F$. It is trivial if $x \in B$, so we may suppose that $x \in A \cup C$. Lemma 6.3 asserts that from any vertex of $(A \cup C) \setminus F$ one can reach a vertex of $A \setminus F$ in $T_1 - F$. Thus there exists a vertex $x' \in A \setminus F$ reachable from $x$ in $T_1 - F$. By (ii), there is a directed path from $x'$ to a vertex $u$ in $B \setminus F$ in $T_1 - F$. Hence there is a directed path
$P_x$ from $x$ to $u$ in $T_1 - F$. Similarly, by directional duality, in $T_1 - F$, there is a directed path $P_y$ from a vertex $w \in A \setminus F$ to $y$.

By Lemma 6.3, we have $|R_{T\langle B \cup C \rangle - F}^{+}(u) \cap (C \setminus F)| \ge |C| - 2|F \cap (B \cup C)| = |C \setminus F| - |F \cap C| - 2|F \cap B|$.
Similarly, we obtain $|R_{T\langle A \cup C \rangle - F}^{-}(w) \cap (C \setminus F)| \ge |C \setminus F| - |F \cap C| - 2|F \cap A|$.
This yields

$$
\begin{align*}
|R_{T\langle B \cup C \rangle - F}^{+}(u) \cap R_{T\langle A \cup C \rangle - F}^{-}(w)| &= |(R_{T\langle B \cup C \rangle - F}^{+}(u) \cap (C \setminus F)) \cap (R_{T\langle A \cup C \rangle - F}^{-}(w) \cap (C \setminus F))| \\
&= |R_{T\langle B \cup C \rangle - F}^{+}(u) \cap (C \setminus F)| + |R_{T\langle A \cup C \rangle - F}^{-}(w) \cap (C \setminus F)| \\
&\quad - |(R_{T\langle B \cup C \rangle - F}^{+}(u) \cap (C \setminus F)) \cap (R_{T\langle A \cup C \rangle - F}^{-}(w) \cap (C \setminus F))| \\
&\ge (|C \setminus F| - |F \cap C| - 2|F \cap B|) + (|C \setminus F| - |F \cap C| - 2|F \cap A|) - |C \setminus F| \\
&= |C \setminus F| - 2|F| \\
&\ge |C| - 3|F| \\
&\ge (3k - 2) - 3(k - 1) \\
&= 1.
\end{align*}
$$

Thus there is a vertex of $C \setminus F$ in $R_{T\langle B \cup C \rangle - F}^{+}(u) \cap R_{T\langle A \cup C \rangle - F}^{-}(w)$, and so there exists a directed path $Q$ from $u$ to $w$ in $T_1 - F$. Then $P_x Q P_y$ is a directed path from $x$ to $y$ in $T_1 - F$. $\square$

All the results of the previous subsections imply the following.

$$
\textbf{Corollary 6.6.} $m_k(n) \le \begin{cases} 2k & \text{if } n \ge 2k+1, \\ 3 & \text{if } n \ge 11k-2, \\ 1 & \text{if } n \ge 19k-2. \end{cases}
$$

6.4 Upper bounds for $k$ large

In this section, we show that if a tournament has at least $2k + 1 + \epsilon k$ vertices for some positive integer $k$ and some $\epsilon > 0$, then it can be made $k$-strong by inverting a family of sets whose cardinality only depends on $\epsilon$. The proof consists in drawing this family uniformly at random, under the constraint that every vertex is contained in at least one of the sets.

To analyse this procedure we will need Chernoff's Bound (Proposition 2.6) as well as the two following
technical lemmas.

**Lemma 6.7.** Let $\vec{u} \neq \vec{v} \in \mathbb{F}_2^t \setminus \{\vec{0}\}$ and $x, y \in \mathbb{F}_2$ be fixed, and let $\vec{w} \in \mathbb{F}_2^t \setminus \{\vec{0}\}$ be drawn uniformly at random. Then $\text{Pr}[\vec{u} \cdot \vec{w} = x, \vec{v} \cdot \vec{w} = y] \ge \frac{1}{4} - \frac{3}{4} \frac{1}{2^t - 1}$.

Proof. As $\vec{u} \neq \vec{v}$, the mapping $\mathbb{F}_2^t \to \mathbb{F}_2^2$, $\vec{w} \mapsto (\vec{u} \cdot \vec{w}, \vec{v} \cdot \vec{w})$ is surjective and linear. As a consequence, there are $\frac{1}{4}2^t$ vectors $\vec{w} \in \mathbb{F}_2^t$ which satisfy $\vec{u} \cdot \vec{w} = x$ and $\vec{v} \cdot \vec{w} = y$. Thus by possibly removing the solution $\vec{w} = 0$, we obtain $\text{Pr}[\vec{u} \cdot \vec{w} = x, \vec{v} \cdot \vec{w} = y] \ge \frac{2^{t-2}-1}{2^t-1} = \frac{1}{4} - \frac{3}{4} \frac{1}{2^t-1}$. $\square$

**Lemma 6.8.** Let $\epsilon > 0$, let $t \ge 16$ be an integer, and let $k \ge \frac{8t}{\epsilon}$ be an integer. Let $U, V \in (\mathbb{F}_2^t \setminus \{\vec{0}\})^{\lceil \epsilon k/8 \rceil}$ be drawn uniformly at random and $W \in \mathbb{F}_2^{\lceil \epsilon k/8 \rceil \times \lceil \epsilon k/8 \rceil}$ be fixed. Then $\text{Pr}[U^\top \cdot V = W] \le 2^{-\epsilon k/128}$.

Proof. Note that since $k \ge \frac{8t}{\epsilon}$, we have $\lceil \epsilon k/8 \rceil \ge t \ge t/2 + 1$. First we bound the probability that $\text{rk}(U) \le t/2$. If $U$ has rank at most $t/2$, then there is a choice of $\lfloor t/2 \rfloor$ columns of $U$ such that all the other ones are in the linear span of these selected columns. Since the linear span of $\lfloor t/2 \rfloor$ vectors has
dimension at most $t/2$, and so size at most $2^{t/2}$, we deduce the following.

$$
\begin{align*}
\Pr[\mathrm{rk}(U) \le t/2] &\le \binom{\lceil \epsilon k/8 \rceil}{\lfloor t/2 \rfloor} \binom{2^{\lceil t/2 \rceil} - 1}{2^t - 1}^{\lceil \epsilon k/8 \rceil - \lfloor t/2 \rfloor} \\
&\le \binom{\lceil \epsilon k/8 \rceil}{\lfloor t/2 \rfloor} \binom{2^{t/2} - 1}{2^t - 1}^{\epsilon k/8 - t/2} \\
&\le 2^{\epsilon k/8 + 1} \binom{2^{t/2} - 1}{2^t - 1}^{\epsilon k/16} \quad \text{because } \frac{t}{2} \le \frac{\epsilon k}{16} \text{ since } k \ge \frac{8t}{\epsilon} \\
&\le 2^{\epsilon k/4} (2^{t/2})^{-\epsilon k/16} \\
&\le 2^{\epsilon \mathrm{tk}/64} 2^{-\epsilon \mathrm{tk}/32} \quad \text{because } t \ge 16 \\
&= 2^{-\epsilon \mathrm{tk}/64}.
\end{align*}
$$

Now we assume that rk(U) > t/2. Then for every column v of V, v must be chosen in an affine space of dimension at most $t - \lfloor t/2 \rfloor - 1 \le t/2$. It follows that

$$
\begin{align*}
\Pr[U^\top \cdot V = W \mid \mathrm{rk}(U) > t/2] &\le \left( \frac{2^{t/2} - 1}{2^t - 1} \right)^{\lceil \epsilon k/8 \rceil} \\
&\le (2^{-t/2})^{\epsilon k/8} \\
&= 2^{-\epsilon \mathrm{tk}/16}.
\end{align*}
$$

Therefore

$$
\begin{align*}
\Pr[U^\top \cdot V = W] &\le \Pr[\mathrm{rk}(U) \le t/2] + \Pr[U^\top \cdot V = W \mid \mathrm{rk}(U) > t/2] \\
&\le 2^{-\epsilon \mathrm{tk}/64} + 2^{-\epsilon \mathrm{tk}/16} \le 2 \cdot 2^{-\epsilon \mathrm{tk}/64}.
\end{align*}
$$

We know that $\epsilon \mathrm{tk} \ge 8t^2 \ge 2 \cdot 64$, thus $2^{-\epsilon \mathrm{tk}/64} \le 1/4$. As $2x \le \sqrt{x}$ for any $x \in [0, 1/4]$, we end with $\Pr[U^\top \cdot V = W] \le 2 \cdot 2^{-\epsilon \mathrm{tk}/64} \le 2^{-\epsilon \mathrm{tk}/128}$. $\square$

For technical reasons, we prove the following seemingly weaker restatement of Theorem 1.15.

**Theorem 6.9.** There exists a function $f: \mathbb{R}_{>0} \to \mathbb{N}$ such that for every $\epsilon > 0$ and every positive integer $k$, if $T$ is an $n$-vertex tournament with $n \ge 2k + 2\epsilon k + 2$, then $\mathrm{sinv}_k(T) \le f(\epsilon)$.

It is not difficult to see that Theorem 6.9 actually implies Theorem 1.15. Indeed, given a function $f$ like in Theorem 6.9 at hand, define $f' : \mathbb{R}_{>0} \to \mathbb{N}$ by $f'(\epsilon) = \max\{\frac{4}{\epsilon}, f(\frac{\epsilon}{2})\}$. Let $T$ be a tournament with $|V(T)| \ge 2k + 1 + \epsilon k$ for some positive integer $k$. If $k \le \frac{2}{\epsilon}$, then Theorem 5.8 yields $\mathrm{sinv}_k(T) \le 2k \le \frac{4}{\epsilon} \le f'(\epsilon)$. Otherwise, we have $|V(T)| \ge 2k + 1 + \epsilon k \ge 2k + 2 + \frac{\epsilon}{2}k$, so $\mathrm{sinv}_k(T) \le f(\frac{\epsilon}{2}) \le f'(\epsilon)$ by Theorem 6.9.

*Proof.* Without loss of generality, we may assume $\epsilon \le \frac{1}{3}$. Let $C$ be a constant such that $\mathrm{sinv}_k(T) \le 1$ if $n \ge Ck$, which exists by Theorem 1.10. Let $t$ be the smallest integer such that

* $t \ge 16$,

* $t \ge \log(1 + \frac{48}{\epsilon})$, and

* $t \ge \frac{128}{\epsilon}(2C + 2 + \epsilon/4) + 16$.

Clearly, $t$ is well defined and depends only on $\epsilon$. Let $k_0$ be the smallest integer such that for every $k' \ge k_0$,

$$
(2^t - 1) \exp\left(-\epsilon^2 \frac{(2+\epsilon)k'}{24}\right) + 3(Ck')^2 \exp\left(-\epsilon^2 \frac{(2+\epsilon)k'}{4096}\right) + 2^{-k'} < 1. \quad (1)
$$
We now prove the statement for $f(\epsilon) = \max\{t, 2k_0-2, \lceil \frac{16t}{\epsilon} \rceil -2\}$. If $k < k_0$, then we conclude directly using Theorem 5.8 that $\text{sinv}_k(T) \le 2k \le 2k_0 - 2 \le f(\epsilon)$. Similarly, if $k \le \frac{8t}{\epsilon} - 1$, then we conclude by Theorem 5.8 that $\text{sinv}_k(T) \le \frac{16t}{\epsilon} - 2 \le f(\epsilon)$. Moreover, if $n \ge Ck$, we have $\text{sinv}_k(T) \le 1 \le f(\epsilon)$. Henceforth, we may assume $k \ge \max\{k_0, \frac{8t}{\epsilon} - 1\}$ and $n \le Ck$.

For every vertex $u \in V(T)$, we choose uniformly and independently at random a vector $\vec{u} \in \mathbb{F}_2^t \setminus \{\vec{0}\}$. For $i \in [t]$, let $X_i = \{u \in V(T) \mid \vec{u}_i = 1\}$. We will prove that with positive probability, the tournament $T' = \text{Inv}(T; X_1, \dots, X_t)$ is $k$-strong. Note that for every arc $uv \in A(T)$, we have $uv \in A(T')$ if and only if $\vec{u} \cdot \vec{v} = 0$. For two disjoint subsets $A$ and $B$ of vertices of $T'$, a **directed (A, B)-matching** is a set of arcs with tails in $A$, heads in $B$, and without common tail or common head.

**Claim 6.9.1.** If $T'$ is not $k$-strong, then at least one of the following events occurs:

$E_1$: there is a vector $\vec{z} \in \mathbb{F}_2^t \setminus \{\vec{0}\}$ such that $|\{v \in V(T) \mid \vec{v} \neq \vec{z}\}| < k$,

$E_2$: there are $u, v \in V(T)$ with $\vec{u} \neq \vec{v}$ such that $\min\{|N_{T'}^+(u) \cap N_{T'}^-(v)|, |N_{T'}^+(u) \cap N_{T'}^+(v)|, |N_{T'}^-(u) \cap N_{T'}^-(v)|\} \le (1 + \frac{\epsilon}{4}) \frac{k}{2}$,

$E_3$: there are disjoint sets $A, B \subseteq V(T')$ with $|A|, |B| \ge (1 + \frac{\epsilon}{4}) \frac{k}{2}$ with no directed (A, B)-matching of size at least $\frac{k}{2}$.

*Proof of claim.* Assume that none of $E_1$, $E_2$ and $E_3$ holds. Suppose for a contradiction that there is a set $X$ of at most $k-1$ vertices, and a partition $(V_1, V_2)$ of $V(T' - X)$ into nonempty sets such that $V_2 \Rightarrow V_1$ in $T' - X$. Since $E_1$ does not hold, there exist $x, y \in V_1 \cup V_2$ with $\vec{x} \neq \vec{y}$. If both $x$ and $y$ are in $V_1$ (resp. $V_2$), consider $v \in V_2$ (resp. $u \in V_1$) and either $\vec{x} \neq \vec{v}$ or $\vec{y} \neq \vec{v}$ (resp. $\vec{x} \neq \vec{u}$ or $\vec{y} \neq \vec{u}$). If $x \in V_1$ and $y \in V_2$ we set $u = x$ and $v = y$, and if $y \in V_2$ and $x \in V_1$ we set $u = y$ and $v = x$. In all cases, there are $u \in V_1$ and $v \in V_2$ with $\vec{u} \neq \vec{v}$.

Now, as $E_2$ does not hold, we have $|N_{T'}^+(u) \cap N_{T'}^-(v)|, |N_{T'}^+(u) \cap N_{T'}^+(v)|, |N_{T'}^-(u) \cap N_{T'}^-(v)| \ge (1+\epsilon/4)^{\frac{k}{2}}$. Finally, as $E_3$ does not hold, there is a directed $(N_{T'}^+(u) \cap N_{T'}^+(v), N_{T'}^-(u) \cap N_{T'}^-(v))$-matching $M$ of size at least $k/2$ in $T'$. For every arc $e = xy \in M$, observe that $P_e = uxyv$ is a directed $(u, v)$-path in $T'$. Furthermore, for every $x \in N_{T'}^+(u) \cap N_{T'}^-(v)$, observe that $P_x = uxv$ is a directed $(u, v)$-path in $T'$. This yields a collection of at least $k$ internally vertex-disjoint $(u, v)$-paths in $T'$, a contradiction since every $(u, v)$-path meets $X$ which has size at most $k-1$. $\diamond$

We will show that with positive probability none of the events $E_1$, $E_2$ and $E_3$ occurs.

**Claim 6.9.2.** $\text{Pr}(E_1) \le (2^t - 1) \exp(-\epsilon^2 \frac{n}{16})$

*Proof of claim.* If $\vec{c} \in \mathbb{F}_2^t \setminus \{\vec{0}\}$ is fixed, then $Y_{\vec{c}} = |\{u \in V(T) \mid \vec{u} \neq \vec{c}\}|$ is a random variable having a binomial law with parameters $n$ and $1 - \frac{1}{2^{t-1}}$. As $\epsilon \le \frac{1}{3}$ and $t \ge 2$, we have $k \le \frac{1}{2}n \le \frac{2}{3} \cdot \frac{5}{6}n \le (1 - \frac{1}{2^{t-1}})(1 - \frac{\epsilon}{2})n$. By Chernoff's Bound (Proposition 2.6), and because $t \ge 2$, we have

$$ \begin{aligned} \text{Pr}[\exists \vec{c} \in \mathbb{F}_2^t \setminus \{\vec{0}\}, Y_{\vec{c}} < k] &\le \sum_{\vec{c} \in \mathbb{F}_2^t \setminus \{0\}} \text{Pr}[Y_{\vec{c}} < k] \\ &\le \sum_{\vec{c} \in \mathbb{F}_2^t \setminus \{0\}} \text{Pr} \left[ Y_{\vec{c}} < \left(1 - \frac{\epsilon}{2}\right) \left(1 - \frac{1}{2^t - 1}\right) n \right] \\ &\le (2^t - 1) \exp \left( - \left(\frac{\epsilon}{2}\right)^2 \left(1 - \frac{1}{2^t - 1}\right) \frac{n}{2} \right) \\ &\le (2^t - 1) \exp \left( - \epsilon^2 \frac{n}{16} \right), \end{aligned} $$

as claimed.

$\diamond$

**Claim 6.9.3.** $\text{Pr}(E_2) \le 3n(n-1) \exp(-\epsilon^2 \frac{n-2}{4096})$
*Proof of claim.* Let $u, v$ be distinct vertices and let $A = N_{T'}^+(u) \cap N_{T'}^-(v)$, $B = N_{T'}^+(u) \cap N_{T'}^-(v)$ and $C = N_{T'}^-(u) \cap N_{T'}^+(v)$. Let $X \in \{A, B, C\}$. Once $\vec{u}$ and $\vec{v}$ have been revealed, for every vertex $w \neq u, v$, let $Y_w$ be a random variable with $Y_w = 1$ if $w \in X$, $Y_w = 0$ otherwise. By Lemma 6.7, $Y_w$ is a random variable following a Bernoulli distribution whose parameter is at least $\frac{1}{4}(1 - \frac{3}{2^{t-1}})$. Further, the $Y_w$ are mutually independent.

We now define a random variable $X_w$ for every $w \in V(T) \setminus \{u, v\}$ as follows. If $Y_w = 0$, set $X_w = 0$, and otherwise set $X_w = 1$ with probability $\frac{1}{\Pr[Y_w=1]}$ and $X_w = 0$ otherwise, where the latter random experiments are executed independently. Observe that, as the $Y_w$ are mutually independent, so are the $X_w$. Moreover, $\Pr[X_w = 1] = \frac{1}{4}(1 - \frac{3}{2^{t-1}})$ and $\sum_{w \in V(T) \setminus \{u, v\}} X_w \geq |X|$.

We have $(1 + \frac{\epsilon}{4}) \frac{k}{2} \leq \frac{1+\frac{\epsilon}{4}}{2+\epsilon}(n-2)/2 = \frac{1}{2}\left(1 - \frac{\epsilon}{1+\frac{\epsilon}{2}}\right) \frac{n-2}{2} \leq \frac{1}{4}\left(1 - \frac{\epsilon}{8}\right)(n-2)$ since $n \geq (2+\epsilon)k + 2$. Moreover, as $t \geq \log(\frac{48}{\epsilon} + 1)$ we have $\frac{1}{4}(1 - \epsilon/8) \leq \frac{1}{4}(1 - \epsilon/16)^2 \leq \frac{1}{4}\left(1 - \frac{3}{2^{t-1}}\right)(1 - \frac{\epsilon}{16}) = \left(\frac{1}{4} - \frac{3}{4(2^{t-1})}\right)(1 - \frac{\epsilon}{16})$. Hence $(1 + \frac{\epsilon}{4}) \frac{k}{2} \leq (1 - \frac{\epsilon}{16})\left(\frac{1}{4} - \frac{3}{4(2^{t-1})}\right)(n-2)$, and by Chernoff's Bound (Proposition 2.6)

$$ \begin{aligned} \Pr\left[|X| \leq \left(1 + \frac{\epsilon}{4}\right) \frac{k}{2}\right] &\leq \Pr\left[|X| \leq \left(1 - \frac{\epsilon}{16}\right) \left(\frac{1}{4} - \frac{3}{4(2^t - 1)}\right) (n-2)\right] \\ &\leq \exp\left(-\left(\frac{\epsilon}{16}\right)^2 \left(\frac{1}{4} - \frac{3}{4(2^t - 1)}\right) \frac{n-2}{2}\right) \\ &\leq \exp\left(-\epsilon^2 \frac{n-2}{4096}\right) \end{aligned} $$

since $t \geq 5$ implies $\frac{3}{2^{t-1}} \leq \frac{1}{8}$. Hence, by the Union Bound (Proposition 2.5), $\Pr[\min\{|A|, |B|, |C|\} \leq (1 + \frac{\epsilon}{4}) \frac{k}{2}] \leq \sum_{X \in \{A, B, C\}} \Pr[|X| \leq (1 + \frac{\epsilon}{4}) \frac{k}{2}] \leq 3\exp(-\epsilon^2 \frac{n-2}{4096})$. Finally, by the Union Bound over $u, v$, the probability that there exist $u, v$ distinct such that $\min\{|A|, |B|, |C|\} \leq (1 + \frac{\epsilon}{4}) \frac{k}{2}$ is at most $3n(n-1)\exp(-\epsilon^2 \frac{n-2}{4096})$. $\diamond$

For two disjoint sets of vertices $X, Y$ in $T'$, we denote by $\mu_{T'}(X, Y)$ the size of a largest directed $(X, Y)$-matching in $T'$.

**Claim 6.9.4.** $\Pr(E_3) \leq 2^{-k}$.

*Proof of claim.* Let $A, B \subseteq V(T')$ be disjoint sets of $\left\lceil \left(1 + \frac{\epsilon}{4}\right) \frac{k}{2} \right\rceil$ vertices. We shall prove that with high probability there is a directed $(A, B)$-matching in $T'$ of size at least $\frac{k}{2}$.

Let $M$ be a maximal directed $(A, B)$-matching and let $Y_A$ (resp. $Y_B$) the set of vertices in $A$ (resp. in $B$) incident to no arc of $M$. Then $Y_B \Rightarrow Y_A$ in $T'$ since $M$ is maximal. Moreover, if $|M| \leq k/2$, then $|Y_A|, |Y_B| \geq (1 + \frac{\epsilon}{4}) \frac{k}{2} - \frac{k}{2} = \frac{\epsilon}{8}k$.

For every such $Y_A \subseteq A$, $Y_B \subseteq B$, we identify $Y_A$ and $Y_B$ with the matrices whose columns are the $\vec{u}$ for $u \in Y_A$ (resp. $u \in Y_B$).

We also denote by $T(Y_B, Y_A)$ the $|Y_B| \times |Y_A|$ matrix over $\mathbb{F}_2$ whose cell $(b, a)$ equals 1 if and only if $ab \in A(T)$. Then observe that $Y_B \Rightarrow Y_A$ in $T'$ if and only if $Y_B^\top \cdot Y_A = T(Y_B, Y_A)$. By these observations, we have

$$ \begin{aligned} \Pr[\mu_{T'}(A, B) < k] &\leq \Pr[\exists Y_A \subseteq A, |Y_A| \geq \frac{\epsilon}{8}k, \exists Y_B \subseteq B, |Y_B| \geq \frac{\epsilon}{8}k, Y_B \Rightarrow Y_A \text{ in } T'] \\ &\leq \Pr[\exists Y_A \subseteq A, |Y_A| \geq \frac{\epsilon}{8}k, \exists Y_B \subseteq B, |Y_B| \geq \frac{\epsilon}{8}k, Y_B^\top \cdot Y_A = T(Y_B, Y_A)] \\ &\leq 2^{2\left\lceil \left(1 + \frac{\epsilon}{4}\right) \frac{k}{2} \right\rceil} 2^{-\frac{\epsilon k}{128}} \quad \text{by Lemma 6.8 and the Union Bound} \\ &\leq 2^{(1 + \frac{\epsilon}{4})k + 2} 2^{-\frac{\epsilon k}{128}} \\ &\leq 2^{-(2C+1)k} \end{aligned} $$

as $t \geq \frac{128}{\epsilon}(2C + 2 + \frac{\epsilon}{4}) + 16$ and $\frac{\epsilon k}{64} \geq \frac{1}{8}$. It follows from the Union Bound (Proposition 2.5) that $\Pr(E_3) \leq 2^{2n} 2^{-(2C+1)k} \leq 2^{-k}$ using the fact that $n \leq Ck$. $\diamond$
We can now conclude using Claims 6.9.1, 6.9.2, 6.9.3 and 6.9.4 and the Union Bound:

$$
\begin{align*}
\Pr[T' \text{ not } k\text{-strong}] &\le \Pr(E_1) + \Pr(E_2) + \Pr(E_3) \\
&\le (2^t - 1) \exp\left(-\epsilon^2 \frac{n}{16}\right) + 3n^2 \exp\left(-\epsilon^2 \frac{n-2}{4096}\right) + 2^{-k} \\
&\le (2^t - 1) \exp\left(-\epsilon^2 \frac{(2+\epsilon)k}{16}\right) + 3(Ck)^2 \exp\left(-\epsilon^2 \frac{(2+\epsilon)k}{4096}\right) + 2^{-k} \\
&< 1,
\end{align*}
$$

by (1). This proves that there exist $X_1, \dots, X_t \subseteq V(T)$ such that $T' = \text{Inv}(T; X_1, \dots, X_t)$ is $k$-strong. $\square$

# 7 Conclusion

In this paper, we investigated the minimum number of inversions needed to make a digraph $k$-strong or $k$-arc-strong. Many open questions remain.

From an algorithmic perspective, it would be interesting to gain a deeper understanding of the complexity when the problem is restricted to tournaments. While the complexity for fixed $k$ is settled by Corollary 1.16, the following question remains open:

**Problem 7.1.** What is the complexity of computing $\text{inv}_k(T)$ (resp. $\text{inv}'_k(T)$) for a given tournament $T$ if $k$ is part of the input ?

Regarding bounds, we provided many on $\text{inv}_k(n)$ and $\text{inv}'_k(n)$. But those functions still need to be better understood.

Firstly, it would be nice to better understand the asymptotic behaviour of $\text{inv}_k(n)$ and determine whether an analogue of Theorem 1.1 exists for $\text{inv}_k$.

**Problem 7.2.** Find good lower and upper bounds on $\text{inv}_k(n)$.

Secondly, we posed Conjecture 1.11 which we restate.

**Conjecture 1.11.** Let $k$ be a positive integer.

(i) $m_k$ and $m'_k$ are non-increasing mappings.

(ii) $M_k = m_k(2k + 1)$ and $M'_k = m'_k(2k + 1)$.

Conjecture 1.11 is motivated by the following consideration. By Proposition 2.2, every tournament $T$ of order $n > 4k - 2$ has a vertex $v$ with $d_T^-(v) \ge k$ and $d_T^+(v) \ge k$. Moreover, adding a vertex with in- and out-degree at least $k$ to a $k$-(arc-)strong digraph results in a $k$-(arc-)strong digraph. Hence any $k$-(arc)-strengthening family of $T - v$ is also a $k$-(arc-)strengthening family of $T$. Thus $\text{inv}_k(T) \le \text{inv}_k(T - v) \le m_k(n - 1)$ and $\text{inv}'_k(T) \le \text{inv}'_k(T - v) \le m'_k(n - 1)$. Hence $m_k(n) \le m_k(n - 1)$ and $m'_k(n) \le m'_k(n - 1)$. Therefore, in order to approach Conjecture 1.11 and Problem 1.9, it is sufficient to consider tournaments whose order is in the range from $2k + 1$ to $4k - 2$.

Another intriguing question is whether $M_k = M'_k$.

**Problem 7.3.** Is it true that $M_k = M'_k$ for every positive integer $k$ ?

In Subsection 5.1, we proved that this is the case for $k = 1, 2$.

Furthermore, there is still a significant gap between the logarithmic lower bounds and the linear upper bounds on $M'_k$ and $M_k$. Therefore it would be good to improve these. A first question is the following.

**Problem 7.4.** Are $M'_k$ and $M_k$ sublinear functions of $k$ ?

We also proved a collection of bounds for $N_k(1)$ and $N_k(3)$. It would be interesting to have stronger bounds on $N_k(i)$ for any integer $i$. In particular, a tight bound for $N_k(1)$ would be satisfying.

Finally, Theorem 1.15 states that every tournament that is a constant factor bigger than $2k$ can be made $k$-strong by a constant number of inversions. It would be interesting to know if this result can be strengthened in the following way:
**Problem 7.5.** Is there an integer $t$ such that for every $\epsilon > 0$, there is an integer $k_0$ such that for every $k \ge k_0$, for every tournament $T$ on at least $(2 + \epsilon)k$ vertices, we have $\text{sinv}_k(T) \le t$?

Proposition 1.13 shows that such an integer would have to satisfy $t \ge 2$, so $t = 2$ is the first open case. The analogous statement for $\text{sinv}'_k$ is also open.

## References

[ACN08] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. *Journal of the ACM*, 55(5), 2008.

[AHH$^{+}$22] Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud, and Quentin Vermande. Problems, proofs, and disproofs on the inversion number, 2022. arXiv:2212.09188.

[AHH$^{+}$25] Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Kingelhoefer, N. Nisse, Clément Rambaud, and Quentin Vermande. Problems, proofs, and disproofs on the inversion number. *The Electronic Journal of Combinatorics*, 32(1), 2025.

[Alo06] Noga Alon. Ranking tournaments. *SIAM Journal on Discrete Mathematics*, 20:137–142, 2006.

[APS$^{+}$24] Noga Alon, Emil Powierski, Michael Savery, Alex Scott, and Elizabeth Wilmer. Invertibility of digraphs and tournaments. *SIAM Journal on Discrete Mathematics*, 38(1):327–347, 2024. arXiv:2212.11969.

[BBBP10] Houmem Belkhechine, Moncef Bouaziz, Imed Boudabbous, and Maurice Pouzet. Inversion dans les tournois. *Comptes Rendus Mathematique*, 348(13-14):703–707, 2010.

[BJdSH22] Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, and Frédéric Havet. On the inversion number of oriented graphs. *Discrete Mathematics & Theoretical Computer Science*, 23(2):#8, 2022. arXiv:2105.04137.

[BJG09] Jørgen Bang-Jensen and Gregory Z. Gutin. *Digraphs: theory, algorithms and applications*. Springer-Verlag, London, 2009.

[BJH18] Jørgen Bang-Jensen and Frédéric Havet. *Tournaments and Semicomplete Digraphs*, volume 11 of Springer Monographs in Mathematics, chapter 2, pages 35–124. Springer, 2018.

[BJHK23] Jørgen Bang-Jensen, Florian Hörsch, and Matthias Kriesell. Complexity of (arc)-connectivity problems involving arc-reversals or deorientations. *Theoretical Computer Science*, 973:114097, 2023. arXiv:2303.03296.

[BJJY23] Jørgen Bang-Jensen, Kasper S. Johansen, and Anders Yeo. Making a tournament $k$-strong. *Journal of Graph Theory*, 103(1):5–11, 2023.

[BJY04] Jørgen Bang-Jensen and Anders Yeo. Making a tournament $k$-arc-strong by reversing or deorienting arcs. *Discrete Applied Mathematics*, 136(2):161–171, 2004. The 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization.

[Cam59] Paul Camion. Chemins et circuits hamiltoniens des graphes complets. *Comptes rendus hebdomadaires des séances de l'académie des sciences*, 249(21):2151–2152, 1959.

[CTY07] Pierre Charbit, Stéphan Thomassé, and Anders Yeo. The minimum feedback arc set problem is NP-hard for tournaments. *Combinatorics, Probability and Computing*, 16:1–4, 2007.

[DS05] Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. *Annals of Mathematics, Second Series*, 162(1):439–485, 2005.

[Dur20] Olivier Durand de Gevigney. On Frank's conjecture on $k$-connected orientations. *Journal of Combinatorial Theory, Series B*, 141:105–114, 2020. arXiv:1212.4086.
[ENSS95] Guy Even, Joseph Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multi-cuts in directed graphs. In Egon Balas and Jens Clausen, editors, *Integer Programming and Combinatorial Optimization, 4th International IPCO Conference, Copenhagen, Denmark, May 29-31, 1995, Proceedings*, volume 920 of Lecture Notes in Computer Science, pages 14–28. Springer, 1995.

[ET75] Shimon Even and R. Endre Tarjan. Network flow and testing graph connectivity. *SIAM Journal on Computing*, 4(4):507–518, 1975.

[Fer83] Wenceslas Fernandez de la Vega. On the maximum cardinality of a consistent set of arcs in a random tournament. *Journal of Combinatorial Theory, Series B*, 35(3):328–332, 1983.

[FF10] Lester R. Ford and Delbert R. Fulkerson. *Flows in Networks*. Princeton University Press, USA, 2010.

[Gab91] Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. In *Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing*, STOC '91, page 112–122, 1991.

[Gal80] Zvi Galil. Finding the vertex connectivity of graphs. *SIAM Journal on Computing*, 9(1):197–219, 1980.

[GHS00] V. Guruswami, J. Hastad, and M. Sudan. Hardness of approximate hypergraph coloring. In *Proceedings 41st Annual Symposium on Foundations of Computer Science*, pages 149–158, 2000.

[HHM77] Frank Harary, Derbiau Hsu, and Zevi Miller. The biparticity of a graph. *Journal of Graph Theory*, 1(2):131–133, 1977.

[HHR24] Frédéric Havet, Florian Hörsch, and Clément Rambaud. Diameter of the inversion graph, 2024. arXiv:2405.04119.

[HT00] Frédéric Havet and Stéphan Thomassé. Median orders of tournaments: A tool for the second neighborhood problem and sumner's conjecture. *Journal of Graph Theory*, 35(4):244–256, 2000.

[Kan92] Vido Kann. *On the Approximability of NP-complete Optimization Problems*. PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992.

[Kar72] Richard M. Karp. Reducibility among combinatorial problems. In *Complexity of Computer Computations*, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.

[KMS07] 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*, STOC '07, page 95–103, 2007.

[KS06] Zoltán Király and Zoltán Szigeti. Simultaneous well-balanced orientations of graphs. *Journal of Combinatorial Theory, Series B*, 96(5):684–692, 2006.

[McK90] Brendan D. McKay. The asymptotic numbers of regular tournaments, eulerian digraphs and eulerian oriented graphs. *Combinatorica*, 10(4):367–377, 1990.

[MR02] Michael Molloy and Bruce Reed. *Graph colouring and the probabilistic method*, volume 23. Springer Science & Business Media, 2002.

[MS89] Yishay Mansour and Baruch Schieber. Finding the edge connectivity of directed graphs. *Journal of Algorithms*, 10(1):76–85, 1989.

[NW60] Crispin St J.A. Nash-Williams. On orientations, connectivity and odd-vertex-pairings in finite graphs. *Canadian Journal of Mathematics*, 12:555–567, 1960.
[Rob39] Herbert E. Robbins. A theorem on graphs, with an application to a problem on traffic control. *American Mathematical Monthly*, 46(5):281–283, 1939.

[Sch78] Thomas J. Schaefer. The complexity of satisfiability problems. In *Proceedings of the tenth annual ACM symposium on Theory of computing*, pages 216–226, 1978.

[Spe74] Joel H. Spencer. Random regular tournaments. *Periodica Mathematica Hungarica*, 5(2):105–120, 1974.

[Tho15] Carsten Thomassen. Strongly 2-connected orientations of graphs. *Journal of Combinatorial Theory, Series B*, 110:67–78, 2015.

[TSKP22] Bhalchandra Thatte, Hamza Si Kaddour, and Maurice Pouzet. On the boolean dimension of a graph and other related parameters. *Discrete Mathematics & Theoretical Computer Science*, 23, 2022. arXiv:2105.00206.