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

Keywords: inversion, tournament, k-strong, k-arc-strong

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 the minimum number of inversions needed to transform D into a k-arc-

for some tournament T of order 2k + 1; (v) if T is a tournament of order at least 19k -2 (resp. 11k -2), then sinv ′ k (T ) ≤ sinv k (T ) ≤ 1 (resp. sinv k (T ) ≤ 3);

(vi) for every ϵ > 0, there exists C such that sinv ′ k (T ) ≤ sinv k (T ) ≤ C for every tournament T on at least 2k + 1 + ϵk vertices.

Introduction

Notation not given below is consistent with [START_REF] Bang | Digraphs: theory, algorithms and applications[END_REF]. We denote by [k] the set {1, 2, . . . , k}. A digraph may contain digons, that 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 feedback arc set in a digraph is a set of arcs whose reversal results in an acyclic digraph. Finding a mininum cardinality feedback arc set is an important and heavily studied problem. It is one of the first problems shown to be NP-hard listed by Karp in [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. 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. [START_REF] Even | Approximating minimum feedback sets and multi-cuts in directed graphs[END_REF]. It was proven to be APX-hard by Kann [START_REF] Vido Kann | On the Approximability of NP-complete Optimization Problems[END_REF]. 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 1.36 [START_REF] Dinur | On the hardness of approximating minimum vertex cover[END_REF]. For tournaments, which are orientations of complete graphs, the problem was proven to be remain NP-complete, independently by Alon [START_REF] Alon | Ranking tournaments[END_REF] and Charbit, Thomassé et Yeo [START_REF] Charbit | The minimum feedback arc set problem is NP-hard for tournaments[END_REF]. On the other hand, a polynomial-time approximation scheme was provided by Kenyon-Mathieu and Schudy [START_REF] Kenyon | How to rank with few errors[END_REF], improving on an earlier 3-approximation algorithm by Ailon Charikar and Newman [START_REF] Ailon | Aggregating inconsistent information: Ranking and clustering[END_REF].

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⟨X⟩. We say that we invert X in D. The resulting digraph is denoted by Inv(D; X). If (X i ) i∈I is a family of subsets of V (D), then Inv(D; (X i ) i∈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 : Inv(D; (X i ) i∈I ) is obtained from D by reversing the arcs such that an odd number of the X i contain its two endvertices. A decycling family of a digraph D is a family (X i ) i∈I of subsets of V (D) such that Inv(D; (X i ) i∈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 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. It was first introduced by Belkhechine et al. in [START_REF] Belkhechine | Inversion dans les tournois[END_REF] and then studied in several papers [BJdSH22, TSKP22, AHH + 22, APS + 22]. In particular, Belkhechine et al. in [START_REF] Belkhechine | Inversion dans les tournois[END_REF] proved that, for any fixed integer k, deciding whether a given tournament has inversion number at most k is polynomialtime solvable. In contrast, Bang-Jensen et al. [START_REF] Bang-Jensen | On the inversion number of oriented graphs[END_REF] proved that deciding whether a given digraph has inversion number 1 is NP-complete. This was generalized by Alon et al. [APS + 22]: for any fixed positive integer k, deciding whether a given digraph has inversion number at most k is NP-complete. The maximum inv(n) over all inversion numbers of digraphs of order n has also been investigated. Independently, Aubian et 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 ̸ = ∅ 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 ̸ = ∅
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)| ≥ k + 1 and G -S is connected for every S ⊆ V (G) with |S| ≤ k -1. For a given digraph D, we denote by UG(D) the undirected (multi)graph that we obtain by suppressing the orientations of the arcs. A digraph is k-connected (resp. k-edge-connected) if its underlying (multi)graph is. Clearly, a digraph D can be made k-arc-strong by reversing some arcs if and only if the edges of UG(D) can be oriented such that the resulting digraph is k-arc-strong. Robbins' Theorem [START_REF] Robbins | A theorem on graphs, with an application to a problem on traffic control[END_REF] 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 [START_REF] St | On orientations, connectivity and odd-vertex-pairings in finite graphs[END_REF], 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 by applying arc reversals, applying standard flow algorithms to its underlying graph. Furthermore, it is well-known that, if this is the case, 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 [START_REF] Bang | Digraphs: theory, algorithms and applications[END_REF] for details. It is easy to see that the number of necessary arc reversals to make a 2k-edgeconnected 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 [START_REF] Bang | Making a tournament k-arc-strong by reversing or deorienting arcs[END_REF] 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 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∈I of subsets of V (D) such that Inv(D; (X i ) i∈I ) is k-arc-strong. The karc-strong inversion number of a digraph D, denoted by 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-strengthening family. We first deal with the extremal behaviour of 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 sinv ′ k (n) = max{sinv ′ k (D) | D 2k-edge-connected digraph of order n}. It turns out that sinv ′ k (n) is an unbounded, but slowly growing, function. We are able to determine sinv ′ k (n) up to a constant multiplicative factor of roughly 2. More precisely, we show the following result: Theorem 1.4. Deciding whether a given k-strengthenable oriented graph D satisfies sinv k (D) ≤ t is NP-complete for all pairs of positive integers k and t.

Theorem 1.5. Unless P=NP, for any positive integer k, there is no (2 -ϵ)-approximation algorithm for computing sinv k (D) for oriented graphs for any ϵ > 0.

In the remainder of this article, we focus on a particular kind of oriented graphs, namely tournaments. It is not hard to show that every tournament of order at least 2k + 1 is k-strengthenable and that it can be made k-strong by reversing the orientation of at most 1 4 (4k -2)(4k -3) arcs, see e.g. [START_REF] Bang | Digraphs: theory, algorithms and applications[END_REF], p. 379. Further, the following improvement was conjectured by Bang-Jensen. (See [START_REF] Bang | Digraphs: theory, algorithms and applications[END_REF].) Conjecture 1.6 (Bang-Jensen, 1994). Every tournament on at least 2k + 1 vertices can be made k-strong by reversing at most 1 2 k(k + 1) arcs. It would be tight as shown by the transitive tournaments. Bang-Jensen, Johansen, and Yeo [START_REF] Bang-Jensen | Making a tournament k-strong[END_REF] proved this conjecture for tournaments of order at least 3k -1.

It is then natural to ask whether or not we can make a tournament k-strong or k-arc-strong using significantly less than 1 2 k(k + 1) inversions. This leads to consider M k = max{sinv k (T ) | T tournament of order at least 2k + 1} and M ′ k = max{sinv ′ k (T ) | T tournament of order at least 2k + 1}. We show that these numbers are indeed significantly smaller than 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

1 2 log(2k + 1) ≤ M ′ k ≤ M k ≤ 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 value of k. Theorem 1.8. M ′ k ≤ 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. If n ≥ (2k -1)2 2k , then sinv k (T ) ≤ 1.
This leads us to the study of the functions m k (n) = max{sinv k (T ) | T tournament of order n} and m ′ k (n) = max{sinv k (T ) | T tournament of order n} for all n ≥ 2k + 1. We believe that m k and m ′ k have the following monotonic behaviour.

Conjecture 1.11.

(i) m k and m ′ k are non-increasing mappings. (ii) M k = M ′ k = m k (2k + 1) = 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 nonincreasing for n > 4k -2. Indeed, it is well-known that every tournament T of order n > 4k -2 has a vertex v with

d - T (v) ≥ k and d + T (v) ≥ k.
(T ) ≤ sinv k (T -v) ≤ m k (n -1) and sinv ′ k (T ) ≤ sinv ′ k (T -v) ≤ m ′ k (n -1). Hence m k (n) ≤ m k (n -1) and m ′ k (n) ≤ m ′ k (n -1)
. 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) ≤ i for all n ≥ 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) ≤ i for all n ≥ N ′ k (i). Since m ′ k (n) ≤ m k (n) for all k and n, we have N ′ k (i) ≤ N k (i)
for all k and i. It is natural to ask the following questions.

Problem 1.12. What is the minimum integer N k (i) such that sinv k (T ) ≤ i for every tournament T of order at least

N k (i) ? What is the minimum integer N ′ k (i) such that sinv ′ k (T ) ≤ i for every tournament T of order at least N ′ k (i) ?
Our most important result on Problem 1.12 is the following significant improvement on Theorem 1.10.

Theorem 1.13. For any positive integer k, we have

N ′ k (1) ≤ N k (1) ≤ 19k -2.
Concerning lower bounds for N k (1), we have the following result.

Proposition 1.14. For any positive integer k, we have N k (1) ≥ 5k -2.

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

Theorem 1.15. For any positive integer k, we have

N ′ k (3) ≤ N k (3) ≤ 11k -2.
Finally, using probabilistic methods, we manage to 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.16. There exists a function f : R >0 → N such that for every ϵ > 0 and every positive integer k, if T is an n-vertex tournament with n ≥ 2k + 1 + ϵk, then sinv k (T ) ≤ f (ϵ).

The fact that m k (n) = 1 for n sufficiently large implies that the set F k of tournaments T such that sinv k (T ) > 1 is finite. This implies that computing sinv k and sinv ′ k for fixed k can be done in polynomial time for tournaments.

Corollary 1.17. Let k be a positive integer. We can compute sinv k (T ) (resp. 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 F k . If yes, then we can return sinv k (T ) and sinv ′ k (T ) that may be stored in some precomputed table. If not, then sinv ′ k (T ) ≤ sinv k (T ) ≤ 1. We then check in O(n 7/2 ) using algorithms due to Even and Tarjan [START_REF] Even | Network flow and testing graph connectivity[END_REF] or Galil [START_REF] Galil | Finding the vertex connectivity of graphs[END_REF] based on flow (resp. O(n 2 ) using Mansour and Schieber [START_REF] Mansour | Finding the edge connectivity of directed graphs[END_REF] algorithm based on flow or Gabow's algorithm [START_REF] Harold | A matroid approach to finding edge connectivity and packing arborescences[END_REF] based on matroids) whether T is k-strong (resp. k-arc-strong) to determine whether sinv k (T )

(reps sinv ′ k (T )) is equal to 0 or 1.
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 1.10, 1.13,1.15 and 1.16 and Proposition 1.14.

Preliminaries

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

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 graph 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. 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 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 be a set of vertices in a mixed graph G. We denote by δ G (S) the set of edges of E(G) with exactly one endvertex in S. We also denote by δ + G (S) (resp. δ - G (S)) the set of arcs in A(G) with tail (resp. head) in S and head (resp. tail) out of S. The degree (resp. out-degree, in-degree

) of S in G is d G (S) = |δ G (S)| (resp. d + G (S) = |δ + G (S)|, d - G (S) = |δ - G (S)|). Let N G (S) (resp. N + G (S), N - G (S)) denote the set of vertices in V (G) \ S that are incident to at least one edge (arc) in δ G (S) (resp. δ + G (S), δ - 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}))
. Furthermore, for two disjoint sets S 1 , S 2 , let d G (S 1 , S 2 ) be the number of edges in E with one endvertex in S 1 and one endvertex in S 2 , let d + G (S 1 , S 2 ) be the number of arcs in A whose tail is in S 1 and whose head is in S 2 , and let d - G (S 1 , S 2 ) be d + G (S 2 , S 1 ). 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 Let u, v two distinct vertices in D. The strong-connectivity from u to v in D, denoted by κ D (u, v), is the maximal number α such that D-X contains a (u, v)-path for every X ⊆ V (D)\{u, v} with |X| ≤ α-1. For some S ⊆ V (D) and positive integer k, we say that

D is eulerian if d - D (v) = d + D (v)
S is k-strong in D if κ D (u, v) ≥ k for all u, v ∈ S.

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 ∈ [k](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 ∈ V (D) \ S. If v has at least k in-neighbours in S and at least k out-neighbours in S, then S ∪ {v} is k-strong in D.

Proof. Suppose for the sake of a contradiction that there is a set X ⊆ V (D) of size at most k -1 and a pair (s, t) of vertices in S ∪ {v} \ X such that there is no (s, t)-path in D -X. If s, t ∈ S, then this contradicts the fact that D is k-strong in S. Thus exactly one of s and t is v. Without loss of generality, suppose s ∈ S and t = v. Since |N -(v) ∩ S| ≥ k, v has an in-neighbour t 0 ∈ S -X, and as D 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.

The following result is helpful for applying Proposition 2.1.

Proposition 2.2. Let T be a tournament on at least 4k -2 vertices for some positive integer k. Then there exists some v ∈ V (T ) with min{d + T (v), d - T (v)} ≥ k. We need the following simple characterization of eulerian tournaments.

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

We need the following orientation property of mixed graphs that can be found in [START_REF] Ford | Flows in Networks[END_REF].

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 E(H) (S) ≥ d + A(H) (S) -d - A(H) (S)
for all S ⊆ V (H). Finally, we state two basic tools from probability theory. Proposition 2.5 (Union Bound). Let E 1 , . . . , E ℓ be a set of events in a random experiment and E the event that at least one of E 1 , . . . , E ℓ occurs. Then Pr(E) ≤ ℓ i=1 Pr(E i ). Proposition 2.6 (Chernoff's Bound). If X is a random variable following a binomial law with parameters p ∈ [0, 1] and n ≥ 0, then for every ϵ ∈ [0, 1]

Pr[X ≤ (1 -ϵ)pn] ≤ exp - ϵ 2 2 pn .
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.

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 ≥ 2k + 1, we have

1 2 log(n -k + 1) ≤ sinv ′ k (n) ≤ log n + 4k -3.
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 , . . . , 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 [START_REF] Bang-Jensen | Complexity of (arc)-connectivity problems involving arc-reversals or deorientations[END_REF], is a direct consequence of Corollary 2 in [START_REF] Király | Simultaneous well-balanced orientations of graphs[END_REF].

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 ), . . . , (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, . . . , t.

The following result is part of a draft of a forthcoming paper by a group containing the authors. Theorem 3.2 ( [IWG]). Let G be an n-vertex d-degenerate graph G. For any two orientations ⃗ G 1 , ⃗ G 2 of G, one can transform ⃗ G 1 into ⃗ G 2 by inverting at most log n + 2d -1 sets.

For sake of completeness, we give the proof of this theorem. We denote by F 2 the field with two elements 0 and 1. Given two vectors ⃗ x, ⃗ y ∈ F t 2 , we denote by ⃗ x • ⃗ y their inner product, that is

t i=1 ⃗ x i ⃗ y i ∈ F 2 . Proof. Set t = log n+2d-1. Let ⃗ G 1 , ⃗ G 2 be two orientations of G.
For every edge uv ∈ E(G), we define c(uv) ∈ F 2 such that c(uv) = 0 if and only if uv is oriented the same in ⃗ G 1 and in ⃗ G 2 . Let (v 1 , . . . , v n ) be a d-degenerate ordering of G. We will iteratively build vectors ⃗ v 1 , . . . , ⃗ v n ∈ F t 2 such that, for every i ∈ [n], the following conditions hold: A i : for every ℓ > i, the vectors of {⃗ v j | 1 ≤ j ≤ i and v j ∈ N (v ℓ )} are linearly independent, and

B i : for every edge v j v j ′ with j, j ′ ≤ i, ⃗ v j • ⃗ v j ′ = c(v j v j ′ ).
This will prove the theorem. Indeed, given such vectors, we can define the inversions X i = {u | ⃗ u i = 1} for every i ∈ {1, . . . , t}. Then the arc uv is reversed by X 1 , . . . , X t if and only if ⃗ u

• ⃗ v = 1. Hence Condition B n implies that Inv( ⃗ G 1 ; X 1 , . . . , X t ) = ⃗ G 2
. We now build this family of vectors as follows. For i = 1, we take ⃗ v 1 ∈ F t 2 \ { ⃗ 0} arbitrarily. Now suppose that we have ⃗ v 1 , . . . , ⃗ v i satisfying A i and B i . We shall now choose ⃗ v i+1 . Satisfying A i+1 forbids a vector space of dimension at most d -1 for each neighbour v ℓ of v i+1 with ℓ > i + 1, because v ℓ has at most d -1 neighbours in {v 1 , . . . , v i } by d-degeneracy of G. So, in total, satisfying A i+1 forbids the union of those vector spaces, whose size is at most 1 + n(2 d-1 -1). Satisfying B i+1 allows at least 2 t-d values for ⃗ v i+1 . Indeed, according to B i the vectors of {⃗ v j | 1 ≤ j ≤ i and v j ∈ N (v i+1 )} are linearly independent, so the affine space of the solutions of the system of equations ⃗ v j • ⃗ v i+1 = c(v j v i+1 ) for the at most d indices j such that 1 ≤ j ≤ i and v j ∈ N (v i+1 ), has dimension at least t -d. Since 2 t-d = 2 d-1+log n > 1 + n(2 d-1 -1), there is a vector ⃗ v i+1 ∈ F t 2 such that both A i+1 and B i+1 are satisfied. This concludes the proof of the theorem.

In a multigraph G, for every pair (u, v) of vertices, a (u, v)-cut is a set F of edges such that every (u, v)-path in G intersects F . A cut is a (u, v)-cut for some u, v. Note that a multigraph is k-edge-connected if and only if for every pair u, v of vertices, there is no (u, v)-cut of size at most k -1 in G.

A multigraph G is minimally k-edge-connected if it is k-edge-connected and G \ e is not k-edge-connected for any edge e ∈ E(G). Equivalently, every edge is in a cut of size exactly k. Lemma 3.3. Let k be a positive integer and let G be an n-vertex multigraph. If for every edge uv ∈ 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 , . . . , F k be a set of k edge-disjoint spanning forests in G such that

k i=1 |E(F i )| is maximized. If there is an edge e = uv ∈ E(G) \ k i=1 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 ∈ [k].
Hence G \ e does not contain any (u, v)-cut whose size is smaller than k, a contradiction to the fact e is contained in a cut of size at most k. This yields

|E(G)| = k i=1 |E(F i )| ≤ k(n -1).
We are now ready to prove the upper bound in Theorem 1.1. Lemma 3.4. For every 2k-edge-connected n-vertex digraph D, sinv ′ k (D) ≤ 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 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 Inv(D, X ) is k-arc-strong, and so sinv ′ k (D) ≤ log n + 4k -3.

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 + 2 t-1 +1 2 vertices with a specified vertex s such that in 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 {s1,s2} as well as the arcs s 1 v {s1,s2} and s 2 v {s1,s2} for every {s 1 , s 2 } ⊆ 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 + 2 t-1 +1 2 . Now let D ′ be obtained from D by inverting a collection of t -1 sets X 1 , . . . , X t-1 ⊆ V (D). As |S| = 2 t-1 + 1, there exist vertices s 1 , s 2 ∈ S such that for i = 1, . . . , t -1, we have either {s 1 , s 2 } ⊆ X i or {s 1 , s 2 } ∩ X i = ∅. Then in each of the t -1 inversions, either both or none of the arcs incident to v {s1,s2} are inverted. We obtain that v {s1,s2} is either a source or a sink in D ′ . The statement hence follows for an arbitrary s ∈ S.

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 ≥ 3, there is a 2-edge-connected digraph D on n vertices such that any digraph obtained from D by applying at most 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 ≥ 5 and hence

3 2 √ 2 √ n ≤ 1 2 . Let n ′ = 2 1 2 ⌈log n⌉-1 + 1 + 2 1 2 ⌈log n⌉-1 +1 2
. By Lemma 3.5, there is a digraph D ′ on n ′ vertices together with a vertex s ∈ V (D ′ ) such that every graph obtained from D ′ by applying at most 1 2 ⌈log n⌉ -1 inversions contains a sink or source distinct from s.

Next observe that

n ′ = 2 1 2 ⌈log n⌉-1 + 1 + 2 1 2 ⌈log n⌉-1 + 1 2 = 2 1 2 ⌈log n⌉-1 + 1 + 1 2 (2 1 2 ⌈log n⌉-1 + 1)2 1 2 ⌈log n⌉-1 ≤ 2 1 2 log n-1 2 + 1 + 1 2 (2 1 2 log n-1 2 + 1)2 1 2 log n-1 2 = √ n √ 2 + 1 + 1 2 ( √ n √ 2 + 1) √ n √ 2 = n 4 + 3 2 √ 2 √ n + 1 = n 4 + 3 2 √ 2 √ n n + 1 ≤ n 4 + n 2 + n 4 = n.
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 1 2 ⌈log n⌉ -1 inversions, one of the vertices in V (D ′ ) \ {s} is a source or a sink. 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 ≥ 2k + 1, there is a 2k-edge-connected digraph D on n vertices such that sinv ′ k (D) ≥ 1 2 log(n -k + 1).
Proof. By assumption, we have n -k + 1 ≥ k + 2 ≥ 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 less than 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.

Consider now a family of subsets X such that

D ′ = Inv(D; X ) is k-arc-strong. Any vertex v ∈ 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 |X | ≥ 1 2 log(n -k + 1). Therefore sinv ′ k (D) ≥ 1 2 log(n -k + 1
). Finally, Lemmas 3.4 and 3.7 imply Theorem 1.1.

Complexity of computing sinv k and sinv ′ k

In this section, we deal with the complexity of computing the parameters sinv k (D) and sinv ′ k (D) for a given digraph D. More concretely, we prove Theorems 1.2,1.3,1.4, and 1.5.

In Subsection 4.1, we prove Theorems 1.2 and 1.4, for t = 1 and every positive integer k. In Subsection 4.3 (resp. Subsection 4.2), we prove Theorem 1.4 (resp. Theorem 1.2), in the remaining cases, that is for every t ≥ 2 and every positive integer k. Finally, in Subsection 4.4 we prove Theorems 1.5 and 1.3. Note that all the studied decision problems are in NP since a k-strenghtening (resp. k-arc-strenghthening) family X is a certificate as checking whether Inv(D; X ) is k-strong (resp. k-arc-strong) can be done in polynomial time. Therefore we just need to prove their hardness.

One single inversion

In this section, we show hardness results for the case that a connectivity property is supposed to be achieved by a single inversion.

We need the following problem. For some integer k ≥ 1, an instance of the MONOTONE EQUITABLE k-SAT problem (MEkSAT) consists of a set of variables X and a set of clauses C each of which contains exactly 2k + 1 nonnegated variables and the question is whether there is a truth assignment ϕ : X → {true, false} such that every clause in C contains at least k true and k false variables with respect to ϕ.

Proposition 4.1. MEkSAT is NP-hard for every k ≥ 1.

Proof. For k = 1, we exactly have the MNAE3SAT problem, which is well-known to be NP-hard, see for example [START_REF] Thomas | The complexity of satisfiability problems[END_REF]. We now proceed by induction. We fix some integer k ≥ 1, assume that MEkSAT is NP-hard and show through a reduction from MEkSAT that so is ME(k + 1)SAT.

Let (X, C) be an instance of MEkSAT. We now create an instance

(X ′ , C ′ ) of ME(k + 1)SAT. First, let Y = {y 1 , . . . , y k+3 } and Z = {z 1 , . . . , z k+3 } be sets of new variables. Now let C 1 the the set of all clauses C ⊆ Y ∪ Z with |C| = 2k + 3 and k + 1 ≤ |C ∩ Y | ≤ k + 2. Moreover, we define C 2 = {C ∪ {y 1 , z 1 } | C ∈ C}. Finally, we set X ′ = X ∪ Y ∪ Z and C ′ = C 1 ∪ C 2 .
Before giving the main proof that our reduction works indeed, we show the following intermediate result.

Claim 4.1.1. For any mapping ϕ :

Y ∪ Z → {true, false} that satisfies (Y ∪ Z, C 1 ), we have ϕ(y 1 ) = . . . = ϕ(y k+3 ) ̸ = ϕ(z 1 ) = . . . = ϕ(z k+3 ).
Proof of claim. First suppose that both Y and Z contain both true and false variables with respect to ϕ, say ϕ(y 1 ) = ϕ(z 1 ) = true and ϕ(y

2 ) = ϕ(z 2 ) = false. Let C 1 = Y ∪ Z \ {y 2 , z 2 , z 3 } and C 2 = Y ∪ X \ {y 1 , z 1 , z 3 }.
Further, let α 1 , α 2 be the number of true variables with respect to ϕ in C 1 and C 2 , respectively. As

C 1 , C 2 ∈ C 1 , we have k + 1 ≤ α i ≤ k + 2 for i = 1, 2.
On the other hand, by assumption, we have

α 2 = α 1 -2. This yields k + 1 ≤ α 2 = α 1 -2 ≤ (k + 2) -2 = k, a contradiction.
We may hence suppose by symmetry that ϕ(y 1 ) = . . . = ϕ(y k+3 ) = true. Suppose that Z contains a true variable with respect to ϕ, say ϕ(z 1 ) = true. Then consider the clause C = Y ∪ Z \ {y 1 , z 2 , z 3 }. We obtain that C contains at most k negative variables with respect to ϕ, a contradiction, as C ∈ C 1 . This proves the claim.

♢

We now show that (X ′ , C ′ ) is a positive instance of ME(k + 1)SAT if and only if (X, C) is a positive instance of MEkSAT.

First suppose that (X, C) is a positive instance of MEkSAT, so there is an assignment ϕ : X → {true, false} such that every clause in C contains at least k true and at least k false variables with respect to ϕ. Define ϕ ′ : X ′ → {true, false} by ϕ ′ (x) = ϕ(x) for all x ∈ X and ϕ ′ (y i ) = true and ϕ ′ (z i ) = false for all i ∈ [k + 3]. By construction, every clause in C 1 contains at least k + 1 true and at least k + 1 false variables with respect to ϕ ′ . Further, for every clause C ∪ {y 1 , z 1 } ∈ C 2 , the clause C contains at least k true and at least k false variables with respect to ϕ. As ϕ ′ (y 1 ) = true and ϕ ′ (z 1 ) = false, we obtain that C ∪ {y 1 , z 1 } contains at least k + 1 true and at least k + 1 false variables with respect to ϕ ′ . Hence (X ′ , C ′ ) is a positive instance of ME(k + 1)SAT.

Now suppose that (X ′ , C ′ ) is a positive instance of ME(k + 1)SAT, so there is an assignment ϕ ′ : X ′ → {true, false} such that every clause in C ′ contains at least k + 1 true and at least k + 1 false variables with respect to ϕ ′ . By Claim 4.1.1, we have ϕ ′ (y 1 ) = . . .

= ϕ ′ (y k+3 ) ̸ = ϕ ′ (z 1 ) = . . . = ϕ ′ (z k+3 ).
By symmetry and Claim 4.1.1, we may suppose that ϕ ′ (y i ) = true and ϕ ′ (z i ) = false for all i ∈ [k + 3]. Let ϕ be the restriction of ϕ ′ to X. For every C ∈ C, the clause C ∪ {y 1 , z 1 } contains at least k + 1 true and at least k + 1 false variables with respect to ϕ ′ . As ϕ ′ (y 1 ) = true and ϕ ′ (z 1 ) = false, we obtain that C contains at least k true and at least k false variables with respect to ϕ. Hence (X, C) is a positive instance of MEkSAT. This proves the lemma.

We can now prove the following results. The proof of Theorems 4.2 and 4.3 is a reduction from MEkSAT which is NP-hard by Proposition 4.1. Fix some k ≥ 2 and let (X, C) be an instance of MEkSAT. We construct an oriented graph D(X, C) as follows. We start from the disjoint union of a k-strong tournament T with vertex set {s 1 , . . . , s 2k+1 } and two stable sets V = {v x | x ∈ X} and W = {w C | C ∈ C}. Next, for every i ∈ [k] and every x ∈ X, we add an arc from s i to v x and for every i = {k + 1, . . . , 2k} and every x ∈ X, we add an arc from v x to s i . Finally, for every x ∈ X and C ∈ C with x ∈ C, we add an arc from v x to w C .

Observe that the digraph D(X, C) is k-strengthenable. Indeed D(X, C)⟨S⟩ is k-strong and hence S is k-strong in D(X, C). Hence by Proposition 2.1, S ∪ V is k-strong in D(X, C). Now, for every C ∈ C, we reverse k arcs between w C and its 2k + 1 neighbours in V . Then each w C has at least k in-neighbours and k-out-neighbours in S ∪ V . So, by Proposition 2.1 again, the resulting digraph is k-strong.

The main technical part of the reduction is contained in the proof of the following result. Suppose that (i) holds, so there is an assignment ϕ : X → {true, false} such that every clause in C contains at least k true and at least k false variables with respect to ϕ. Let Z = W ∪ {v x | x ∈ X, ϕ(x) = true} and let D ′ be the oriented graph obtained from D by inverting Z. Clearly, S is k-strong in D ′ . Next, by Lemma 2.1, we obtain that S ∪ V is k-strong in D ′ . Now consider some C ∈ C. As ϕ is equitable, C contains at least k variables x which satisfy ϕ(x) = true. Hence, by construction, w C has at least k out-neighbours in S ∪ V in D ′ . Further, as ϕ is equitable, C contains at least k variables x which satisfy ϕ(x) = false. Hence, by construction,

w C has at least k in-neighbours in S ∪ V in D ′ . By Lemma 2.1, D ′ is k-strong, so (ii) is satisfied.
Clearly, (ii) implies (iii). Now suppose that (iii) holds, so D can be transformed into a k-arc-strong oriented graph D ′ by inverting a single set Z. We now define an assignment ϕ : X → {true, false} in the following way: if v x ∈ Z, we set ϕ(x) = true, otherwise we set ϕ(x) = false. In order to prove that ϕ has the desired properties, consider some clause C ∈ C. As D ′ is k-arc-strong, w C has at least k outgoing arcs in D ′ . It follows that w C ∈ Z and there are at least k variables in X with x ∈ C and v x ∈ Z. Hence C contains at least k variables x with ϕ(x) = true. Next, as D ′ is k-arc-strong, w C has at least k incoming arcs in D ′ . As w C ∈ Z, it follows that there are at least k variables in X with x ∈ C and v x / ∈ Z. Hence C contains at least k variables x with ϕ(x) = false. We obtain that ϕ has the desired properties, so (iii) is satisfied. ♢

Clearly, the size of D(X, C) is polynomial in the size of (X, C) for fixed k, and D(X, C) can be constructed in polynomial time from (X, C). Hence Claim 4.3.1 implies Theorems 4.2 and 4.3.

Several inversions to become k-arc-strong

In order to prove Theorems 1.4 and 1.2 for t ≥ 2 and all k, we shall use another well-studied graph parameter. Let

G be a graph. A cut cover of G is a collection X 1 , . . . , X t of subsets of V (G) such that ∪ t i=1 δ G (X i ) = E(G).
The cut covering number of G, denoted by cc(G), is the minimum integer t such that there is a cut cover of size t. The following well-known result shows a close relationship between the cut covering number and the classical chromatic number.

Proposition 4.4. For any graph G, we have cc(G) = ⌈log(χ(G))⌉.

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 ≥ 3, see [START_REF] Thomas | The complexity of satisfiability problems[END_REF]. It hence follows from Proposition 4.4 that deciding whether the cut covering number of a given graph is at most t is NP-hard for any integer t ≥ 2. We show show a reduction from this problem to the one of deciding whether sinv ′ k (D) ≤ t for a given oriented graph D. Given a digraph D and a set X of vertices in D, we denote by ∂ D (X) the set of edges of UG(D) with exactly one endvertex in X: ∂ D (X) = δ UG(D) (X). The main technical part of the reduction is contained in the following Lemma that will be reused in Section 4.4.0 Proof. Let < be an arbitrary ordering on V (G). We let V (D) contain V (G), a set of vertices Z e = {z 1 e , . . . , z 2k+1 e } for every e ∈ E(G) and a set of vertices X = {x 1 , . . . , x 2k+1 }. We add arcs to D such that D⟨X⟩ is a k-arcstrong tournament. We let A(D) contain an arc from v to x i for every v ∈ V (G) and every i = 1, . . . , k and an arc from x i to v for every v ∈ V (G) and every i = k + 1, . . . , 2k. Next for every e ∈ E(G), we add arcs to D such that D⟨Z e ⟩ is a k-arc-strong tournament. Finally, for every e = uv ∈ E(G) with u < v, we add the arcs uz i e for i = 1, . . . , k, the arcs z i e v for i = 2, . . . , k and the arc vz 1 e . This finishes the description of D. Observe that

|V (D)| = |V (G)| + (2k + 1)|E(G)| + 2k + 1. We now show that sinv ′ k (D) = cc(G). We first show that sinv ′ k (D) ≤ cc(G). Let (X 1 , . . . , X cc(G)
) be an optimal cut cover of G. Now for every e = uv ∈ E(G), there is a smallest α(e) such that exactly one of u and v is contained in

X α(e) . Now for i ∈ [cc(G)], let X ′ i = X i ∪ {z 1 e : α(e) = i}. Let D ′ be the digraph obtained from D by inverting X ′ 1 , . . . , X ′ cc(G) . We will show that D ′ is k-arc-strong. Let S ⊆ V (D) and suppose that min{d - D ′ (S), d + D ′ (S)} < k . By symmetry, we may suppose that S ∩ X ̸ = ∅. As D ′ ⟨X⟩ = D⟨X⟩ is k-arc-strong, we obtain X ⊆ S. Next observe that in D ′ every v ∈ V (G)
is incident to at least k arcs coming from X and k arcs going to X. Thus V (G) ⊆ S. Now consider some e = uv ∈ E(G) with u < v. As D ′ by construction contains k arcs from V (G) to Z e and k arcs from Z e to V (G), we obtain that Z e ⊆ S. Observe that either vz

1 e , z 1 e u ∈ A(D ′ ) (if u ∈ X α(e) ) or z 1 e v, uz 1 e ∈ A(D ′ ) (if v ∈ X α(e)
). Thus D ′ contains k arcs from V (G) to Z e and k arcs from Z e to V (G), and we obtain that Z e ⊆ S. This yields

S = V (D ′ ), so D ′ is k-arc-strong. We hence have sinv ′ k (D) ≤ cc(G).
We now show that cc(G) ≤ sinv ′ k (D). Let (X 1 , . . . , X t ) be a smallest collection of sets whose inversion makes Lemma 4.5 and the NP-hardness of deciding whether a given graph G satisfies cc(G) ≤ t for all t ≥ 2 directly imply the following.

D k-arc-strong. Let D ′ = Inv(D; (X i ) i∈[t] ) and for i ∈ [t], let X ′ i = X i ∩ V (G). Claim 4.5.1. Let e = uv ∈ E(G). Then there is some i ∈ [t] such that X ′ i contains
Corollary 4.6. Let t be an integer greater than 1 and k a positive integer. Deciding whether sinv ′ k (D) ≤ t for a given oriented graph D is NP-complete.

Clearly, Theorem 4.2 and Corollary 4.6 imply Theorem 1.2.

Several inversions to become k-strong

In this subsection, we give a reduction from the cut covering problem to the problem of deciding whether sinv k (D) ≤ t for a given oriented graph D. The main technical part of the reduction is contained in the following lemma that will be reused in Section 4.4. We now show that sinv k (D) = cc(G). Note that this implies that sinv k (D) is finite and thus D is k-strengthenable. We first show that sinv k (D) ≤ cc(G). Let (X 1 , . . . , X t ) be an optimal cut cover of G. For every e = uv ∈ E(G), there is a smallest integer α(e) such that exactly one of u and v is contained in X α(e) . Now for every i ∈ [t], let X ′ i = X i ∪ {z 1 e : α(e) = i}. Let D ′ be the digraph obtained from D by inverting X ′ 1 , . . . , X ′ t . We will show that We now show that cc(G) ≤ sinv k (D). Let (X 1 , . . . , X t ) be a smallest collection of sets whose inversion makes D k-strong. For i = 1, . . . , t, let

D ′ is k-strong. Let Y ⊆ V (D) with |Y | ≤ k -1. We need to show that D -Y is strongly connected. As D⟨W ⟩ is k-strong, we obtain that W \ Y is contained in a single strongly connected component S of D ′ -Y . Next observe that every v ∈ V (G) \ Y has an in-neighbour and an out-neighbour in S, so V (G) \ Y ⊆ S. Now consider some e = uv ∈ E(G). As D ′ ⟨Z e ⟩ = D⟨Z e ⟩ is k-strong, we obtain that Z e \ Y is contained in a single strongly connected component of D ′ -Y . If Y ̸ = {w 1 , . . . , w k-1 },
X ′ i = X i ∩ V (G). Claim 4.7.1. Let e = uv ∈ E(G).
Then there is some i ∈ {1, . . . , t} such that X i contains exactly one of u and v.

Proof of claim. Suppose otherwise, that is for every i ∈ [t] either both u and v or none of u and v are in X i . Thus both the arcs corresponding to edges in ∂ D (Z e ) ∩ ∂ D (z 1 e ) are inverted or none of them. This yields that in D ′ -{w 1 , . . . , w k-1 }, there are either zero or two arcs entering Z e . Hence D ′ -{w 1 , . . . , w k-1 } is not strongly connected, a contradiction. ♢ By Claim 4.7.1, we obtain that (X ′ 1 , . . . , X ′ t ) is a cut cover for G. Thus cc(G) ≤ t = sinv k (D), and we conclude that cc(G) = sinv k (D).

Lemma 4.7 and the NP-hardness of deciding whether a given graph G satisfies cc(G) ≤ t for all t ≥ 2 directly imply the following.

Corollary 4.8. Let t be an integer greater than 1 and k a positive integer. Deciding whether sinv k (D) ≤ t for a given oriented graph D is NP-complete.

Clearly, Theorem 4.3 and Corollary 4.8 imply Theorem 1.2.

Unapproximability

In order to prove Theorems 1.3 and 1.5, we need the following result of Zuckerman [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF].

Proposition 4.9 ([Zuc07]). Unless P=NP, there is no polynomial-time O(n 1-ϵ )-approximation algorithm for computing χ(G) for any ϵ > 0.

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

Proposition 4.10. Unless P=NP, there is no polynomial-time (2 -ϵ)-approximation algorithm for computing the cut covering number of a given graph for any ϵ > 0.

Proof. Suppose that there exists a polynomial-time (2 -ϵ)-approximation algorithm A for computing the cut covering number of a given graph for some ϵ > 0. Now choose ϵ ′ with 0 < ϵ ′ < ϵ and consider a graph G on n ≥ 4 1 ϵ-ϵ ′ vertices. Let A ′ be the algorithm that takes G as input and returns 2 α where α is the output of A applied to G. Clearly, as A runs in polynomial time, so does A ′ . Further, by Proposition 4.4, we have 2 α ≥ 2 cc(G) ≥ 2 log(χ(G)) = χ(G). Finally, by Proposition 4.4, we have

2 α ≤ 2 (2-ϵ)⌈log(χ(G))⌉ ≤ 2 (2-ϵ)(log(χ(G))+1) = 2 2-ϵ 2 log(χ(G))(1-ϵ) 2 log(χ(G)) ≤ 4χ(G) 1-ϵ χ(G) ≤ 4n 1-ϵ χ(G) ≤ n 1-ϵ ′ χ(G).
Hence A ′ is a n 1-ϵ ′ -approximation algorithm for the chromatic number, so the statement follows by Proposition 4.9. Now Proposition 4.10 and Lemma 4.5 imply Theorem 1.3, and Proposition 4.10 and Lemma 4.7 imply Theorem 1.5.

Bounds on M ′ k and M k

In this section, we prove Theorem 1.7, that is 1 2 log(2k + 1) ≤ M k ≤ 2k for all sufficently large k. The left hand-side inequality is proved in Theorem 5.2, and the right-hand side one in Theorem 5.8.

Lower bound on m

′ k (2k + 1)
We shall first show the lower bound m ′ k (2k + 1) = Ω(log k). We need the following result.

Theorem 5.1 (McKay [START_REF] Mckay | The asymptotic numbers of regular tournaments, eulerian digraphs and eulerian oriented graphs[END_REF]). The number of labelled eulerian tournaments on n vertices is

2 n+1 πn n-1 2 n e (1 + o(1)).
We are now ready to prove the lower bound in Theorem 1.7.

Theorem 5.2. For every sufficiently large k, m ′ k (2k + 1) ≥ 1 2 log(2k + 1). Proof. By Theorem 5.1, we may choose an integer k 0 such that for all k ≥ k 0 and for n = 2k + 1, the number of labelled tournaments on n vertices is at most 2 n+1 πn n-1 2

√ n and n-1 2 (log π -1) > log n. Now fix some k ≥ k 0 and let n = 2k + 1. By Proposition 2.3, all the k-arc-strong tournaments on n vertices are eulerian. For two 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 , . . . , X t ) such that Inv(T ; X 1 , . . . , X t ) = T ′ . Observe that there are 2 n possibilities to choose X i for i = 1, . . . , t, hence the number of tournaments reachable from T by t inversions is at most (2 n ) t = 2 nt . Therefore, the number of labelled n-vertex tournaments that are reachable by t inversions from an eulerian one is at most

2 nt 2 n+1 πn n-1 2 √ n = 2 ( n 2 ) • 2 nt 2 πn n-1 2 √ n = 2 ( n 2 ) • 2 nt+ n-1 2 (1-log(π)-log n)+ 1 2 log n < 2 ( n 2 ) • 2 nt-1 2 n log n If t ≤ 1 2 log n, then nt -1 2 n log n ≤ 1
, so the number of such tournaments is less than 2 ( 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 sinv ′ k (T * ) > t.

Theorem 5.2 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.1.

For a positive integer n and a collection of integers α 1 , . . . , α n , we denote by N T (n; α 1 , . . . , α n ) the number of labelled tournaments on [n] in which the vertex i satisfies d

+ (i) -d -(i) = α i .
Theorem 5.3 (Spencer [START_REF] Spencer | Random regular tournaments[END_REF] and McKay [START_REF] Mckay | The asymptotic numbers of regular tournaments, eulerian digraphs and eulerian oriented graphs[END_REF]). Let n be a positive odd integer and let α 1 , . . . , α n be integers. Then

N T (n, α 1 , . . . , α n ) ≤ 2 n+1 πn (n-1)/2 n e exp - 1 + o(1) 2n n i=1 α 2 i .
Corollary 5.4. For all integers k and c, the number of 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 2 n+1 πn (n-1)/2 n e for k large enough.

Proof. By Theorem 5.3, the number of tournaments T on n = 2k + c vertices such that every vertex has in-and out-degree at least k is at most

2 n+1 πn (n-
α 2 i = n i=1 c-1 α=-c+1 exp - 1 + o(1) 2n α 2 ≤ n i=1 c-1 α=-c+1 1 + o(1) = (2c -1 + o(1)) n ≤ 2 log(2c)n
for n large enough, and the result follows.

Theorem 5.5. For every positive integer c fixed, and for every positive integer k large enough compared to c, there exists a tournament T on 2k + c vertices such that sinv ′ k (T ) > 1 2 log(2k + c) -log(2c). In particular, m ′ k (2k + c) is unbounded for every fixed c.

Proof. By Corollary 5.4, the number of tournaments T on n = 2k + c vertices with sinv ′ k (T ) ≤ t is for k large enough at most

2 nt 2 log(2c)n 2 n+1 πn (n-1)/2 n e ≤ 2 ( n 2 ) 2 nt-1 2 n log n+log(2c)n
which is smaller than 2 ( n 2 ) if t ≤ 1 2 log n -log(2c). Hence there exists a tournament T * with sinv ′ k (T * ) > 1 2 log(2k + c) -log(2c).

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 ∈ {1, 2}.

Proposition 5.6. Let T be a tournament of order n ≥ 3. We have sinv 1 (T ) = sinv ′ 1 (T ) = 0 if T is strong and

sinv 1 (T ) = sinv ′ 1 (T ) = 1 otherwise. In particular, m 1 (n) = m ′ 1 (n) = 1 for all n ≥ 3 and M 1 = M ′ 1 = 1.
Proof. (i) Trivially, if T is strong, then sinv 1 (T ) = 0. If T is not strong, then sinv 1 (T ) ≥ 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 [START_REF] Bang | Digraphs: theory, algorithms and applications[END_REF]). Let x be its initial vertex and y its terminal vertex. Then inverting {x, y} yields a tournament with a directed hamiltonian cycle because V (T ) \ {x, y} ̸ = ∅, so a strong tournament. Hence sinv 1 (T ) = 1.

A non-strong tournament is said to be reducible. By definition, a reducible tournament has a reduction T 1 ⇒ T 2 that is two subtournaments T 1 , T 2 such that (V (T 1 ), V (T 2 )) is a partition of V (T ) and V (T 1 ) ⇒ V (T 2 ).

Let S 4 be the unique 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.7. 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 inv(R 5 ) = 2, so sinv ′ 2 (T T 5 ) = 2. Hence M 2 ≥ M ′ 2 ≥ 2.
Let us now prove that M 2 ≤ 2. We shall prove by induction on n that every tournament T of order at least 5 satisfies sinv 2 (T ) ≤ 2.

Assume first that T is a tournament of order 5. If T is strong, then, by Camion's theorem [START_REF] Camion | Chemins et circuits hamiltoniens des graphes complets[END_REF], it has a hamiltonian cycle

v 1 v 2 v 3 v 4 v 5 v 1 . Let A + = A(T ) ∩ {v 1 v 3 , v 2 v 4 , v 3 v 5 , v 4 v 1 , v 5 v 2 } and A -= A(T ) ∩ {v 3 v 1 , v 4 v 2 , v 5 v 3 , v 1 v 4 , v 2 v 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 it must be isomorphic to one of the following tournaments or their converse, where the converse of a digraph D is defined to be Inv(D, V (D)).

• T T 5 with hamiltonian path v 1 v 2 v 3 v 4 v 5 . Then inverting {v 1 , v 2 , v 4 , v 5 } and {v 1 , v 5 } yields R 5 .

• S 4 ⇒ {x}. Then inverting {c, d, x} and {c, d} yields R 5 .

• {x} ⇒ ⃗ C 3 ⇒ {y} with ⃗ C 3 = abca. Then inverting {a, x, y} yields R 5 .

• {x} ⇒ {y} ⇒ ⃗ C 3 with ⃗ C 3 = abca. Then inverting {a, b, c, y} and {a, x, y} yields R 5 .

As sinv 2 (Inv(D, V (D))) = 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)} ≥ 2. By the induction hypothesis, sinv 2 (T -v) ≤ 2, so there is a family X of at most two subsets of

V (T -v) such that Inv(T -v; X ) is 2-strong. Now Inv(T ; X ) - v = Inv(T -v; X ) and min{d + (v), d -(v)} ≥ 2.
Thus, by Lemma 2.1, Inv(T ; X ) is 2-strong, and it follows that sinv 2 (T ) ≤ |X | ≤ 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

⃗ C 3 ⇒ ⃗ C 3 . Let V (T ) = {a

Upper bounds on M k and transitive tournaments

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

Theorem 5.8. M k ≤ 2k.

Proof. Let D be a tournament with V (D) = {v 1 , . . . , v n } with n ≥ 2k + 1. Further, let T be a k-strong tournament on {v 1 , . . . , v 2k+1 }. We now define sets X 1 , . . . , X 2k . Suppose that the sets X 1 , . . . , X i-1 have already been created and let D i-1 be the graph obtained from D by inverting X 1 , . . . , X i-1 . Now let X i = {v i } ∪ A i ∪ B i , where A i is the set of vertices v j with j ∈ {i + 1, . . . , 2k + 1} for which the edge v i v j has a different orientation in T and D i-1 , and B i is, when i ≤ k (resp. i ≥ k + 1), the set of vertices v j with j ≥ 2k + 2 for which D i-1 contains the arc v i v j (resp. v j v i ).

We still need to show that D 2k is k-strong. Observe that D 2k ⟨{v 1 , . . . , v 2k+1 }⟩ = T which is k-strong by assumption. However, for any j ≥ 2k + 2, D 2k contains the arcs v j v i for i = 1, . . . , k and the arcs v i v j for i = k + 1, . . . , 2k. Hence, by Lemma 2.1, D 2k is k-strong.

Theorems 5.2 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 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 ≥ 2k + 1.

sinv k (T T n ) = sinv ′ k (T T n ) = 2 if 2k + 1 ≤ n < 3k 1 if 3k ≤ n. Proof. Let (v 1 , . . . , v n ) be an ordering of V (T T n ) such that v i v j ∈ A(T T n ) for every i < j. Let X 0 = {v i | i even} and X 1 = {v i | i odd}. We claim that T ′ = Inv(T T 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 ℓ such that v ℓ ̸ ∈ Y , and let i 1 (resp. j 1 ) be the smallest (resp. largest) odd integer ℓ such that v ℓ ̸ ∈ Y . Observe that j 0 > i 1 and j 1 > i 0 since |Y | < k and n ≥ 2k+1.

In particular,

v i1 v j0 , v i0 v j1 ∈ A(T ′ ). Since T ′ ⟨X 0 ⟩ -Y (resp. T ′ ⟨X 1 ⟩ -Y
) is a transitive tournament with source v j0 and sink v i0 (resp. source v j1 and sink v i1 ), there are hamiltonian paths

P 0 from v j0 to v i0 in T ′ ⟨X 0 ⟩ -Y and P 1 from v j1 to v i1 in T ⟨X 1 ⟩ -Y . Finally P 0 v i0 v j1 P 1 v i1 v j0 is an hamiltonian directed cycle of T ′ -Y , and so T ′ -Y is strong. Hence T ′ is k-strong, and sinv k (T T n ) ≤ 2. Let us now prove that sinv ′ k (T T n ) ≥ 2 if n ≤ 3k -1. Suppose for a contradiction that there exists X ⊆ V (T T n ) such that T ′ = Inv(T T n ; X) is k-arc-strong. Then, for every i ≤ k, since v i has in-degree i -1 in T T n , we have v i ∈ X. Similarly, for every i ≥ n -k + 1, since v i has out-degree n -i in T T n , we have v i ∈ X. But then every out-neighbour of v 1 in T ′ is in {v k+1 , . . . , v n-k } and so d - T ′ (v 1 ) ≤ n -2k < k. Hence T ′ is not k-arc-strong, a contradiction.
Finally, let us show that sinv k (T

T n ) ≤ 1 if n ≥ 3k. Let (v 1 , . . . , v n ) be an ordering of V (T T n ) such that v i v j ∈ A(T T n ) for every i < j. Let A = {v 1 , . . . , v k }, B = {v k+1 , . . . , v 2k } and C = {v 2k+1 , . . . , v n }. In T ′ = Inv(T T n ; A ∪ C), we have A ⇒ B, B ⇒ C and C ⇒ A. Since |A|, |B|, |C| ≥ k, T ′ is k-strong.
As mentioned in the introduction, it was proven independently by Alon et al. [APS + 22] and Aubian et al.

[AHH + 22] that inv(n) ≤ n -⌈log(n + 1)⌉. Hence , every tournament of order 2k + 1 can be made acyclic in at most 2k -⌈log(k + 1)⌉ inversions, and k-strong in two more inversions by Theorem 5.9. Thus we have the following.

Corollary 5.10. m k (2k + 1) ≤ 2k -⌈log(k + 1)⌉ + 2.

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.

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 ∈ F q×q ′ 2 be a matrix whose rank is q for some integers q, q ′ with q ≤ q ′ . Further, let ⃗ v ∈ F q 2 be a fixed vector and let another vector ⃗ w ∈ F q ′ 2 be drawn uniformly at random. Then

Pr(A ⃗ w = ⃗ v) = 2 -q .
The simple proof of the following result is similar to the one of Theorem 5.8. It will appear fully in [IWG].

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 , . . . , X |V (T1)|-1 of V (T 1 ) such that Inv(T 1 ; X 1 , . . . , X |V (T1)|-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 ⊆ V (T ) with |X| ≤ 2 3 k such that d - T (x) = d + T (x) = k for all x ∈ X.
Then there exists a k-arc-strong tournament T ′ on V (T ) such that all the edges in UG(T )⟨X⟩ ∪ δ 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 )⟨X⟩) ∪ δ UG(T ) (X) the orientation they have in T . Now consider some

S ⊆ V (T ). Let x ∈ S ∩ X. Since d + H (x) = d - H (x), we have d + H (S \ {x}) -d - H (S \ {x}) = d + H (S) -d + H (x, V (H) \ (S ∪ {x})) + d + H (S \ {x}, x) -d - H (S) -d - H (x, V (H) \ (S ∪ {x})) + d - H (S \ {x}, x) = d + H (S) -d + H (S) + d + H (S \ {x}, x) + d + H (V (H) \ (S ∪ {x}), x) -d + H (x, V (H) \ (S ∪ {x})) -d + H (x, S \ {x})) = d + H (S) -d + H (S) + d - H (x) -d + H (x) = d + H (S) -d - H (S).
Repeatedly applying this argument, we obtain

d + H (S)-d - H (S) = d + H (S \X)-d - H (S \X) ≤ d + H (S \X) ≤ |S \X|•|X| since every arc in H have an extremity in X. Symmetrically, we obtain d + H (S)-d - H (S) = d - H (V (H)\S)-d + H (V (H)\ S) = d - H (V (H) \ (S ∪ X)) -d + H (V (H) \ (S ∪ X)) ≤ |V (H) \ (S ∪ X)| • |X|. As |X| ≤ 2 3 k ≤ 1 2 |V (H) \ X| = 1 2 (|S \ X| + |V (H) \ (S ∪ X)|), we obtain d + H (S) -d - H (S) ≤ min{|S \ X|, |V (H) \ (S ∪ X)|} • |X| ≤ min{|S \ X|, |V (H) \ (S ∪ X)|} • 1 2 (|S \ X| + |V (H) \ (S ∪ X)|) ≤ min{|S \ X|, |V (H) \ (S ∪ X)|} • max{|S \ X|, |V (H) \ (S ∪ X)|} = |S \ X| • |V (H) \ (S ∪ X)| = d H (S).
Hence, by Proposition 2.4, there is an eulerian orientation T ′ of T such that all the edges in UG(T )⟨X⟩ ∪ δ 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.

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 ϵ > 0, there is an integer k 0 such that for every k ≥ k 0 and for every tournament T on 2k + 1 vertices, we have sinv ′ k (T ) ≤ ( 4 3 + ϵ)k. Proof. Let ϵ > 0. We may assume ϵ ≤ 1/3. We choose k 0 large enough so that for all k ≥ k 0 , the two following inequalities hold:

• ⌈log 2 k⌉ + ⌈ 1 4 log k⌉ + 2k 3⌈ 1 4 log k⌉ ≤ ϵk • 10 log k ≤ k 1 8 ,
In particular, the later inequality implies that k 0 > 2 12 . Thus the following inequalities also hold for all k ≥ k 0 :

⌈ 1 4 log k⌉ ≤ 1 3 k; ⌈ 1 4 log k⌉ ≤ √ k; k ≥ 13; 3⌈ 1 4 log k⌉ ≤ log k; 16 log k⌈ 1 4 log k⌉ ≤ √ k.
Let T be a tournament on 2k + 1 vertices for some k ≥ k 0 . Let A ⊆ V (T ) be an arbitrary subset of V (T ) with |A| = k and B = V (T ) \ A. For some b ∈ B and a tournament T on V (T ), we denote |k -d - T (b)| by def T (b). Let q = ⌈ 1 4 log k⌉ and q * = ⌈log 2 k⌉. We now choose q * sets X 1 , . . . , X q * ⊆ V (T ) independently and uniformly at random. Let T ′ = Inv(T ; X 1 , . . . , X q * ). For some b ∈ B, we denote by ⃗ b the vector in F q * 2 whose i-th entry is 1 if b ∈ X i and 0 otherwise for i ∈ [q * ]. Observe that by the choice of X 1 , . . . , X q * , the vectors { ⃗ b | b ∈ B} follow a uniform distribution and are mutually independent.

We now define a list of possible events:

E 1 : There is some b ∈ B with def T ′ (b) ≥ 2 log k √ k.
E 2 : There are some b 1 , . . . , b q ∈ B such that ⃗ b 1 , . . . , ⃗ b q are linearly dependent.

E 3 : There are some b 1 , . . . , b q ∈ B such that ⃗ b 1 , . . . , ⃗ b q are linearly independent and a sequence (⋆ 1 , . . . , ⋆ q ) ∈ {+, -} q such that |

q i=1 N ⋆i T ′ (b i ) ∩ A| ≤ 5 log k √ k.
Lemma 5.15. If none of E 1 , E 2 and E 3 occur, then sinv ′ k (T ) ≤ ( 4 3 + ϵ)k. Proof. Let (B 1 , . . . , B t ) be a maximal collection of disjoint subsets of B with the following properties:

• |B i | = q for i = 1, . . . , t, • def T ′ (b) ≡ def T ′ (b ′ ) mod 2 for all b, b ′ ∈ B i for i = 1, . . . , t, • tq ≤ 2 3 k. Claim 5.15.1. | t i=1 B i | ≥ 2 3 k -q.
Proof of claim. Suppose otherwise. Observe that, as

⌈ 1 4 log k⌉ ≤ 1 3 k, we have |B \ ( t i=1 B i )| = |B| -| t i=1 B i | ≥ (k + 1) -( 2 3 k -q) ≥ 1 3 k + q ≥ 2q
. By the Pigeonhole Principle, there exists a set B 0 ⊆ B \ (

t i=1 B i ) with |B 0 | = q such that def T ′ (b) ≡ def T ′ (b ′ ) mod 2 for all b, b ′ ∈ B 0 .
Hence B 0 can be added to B without violating any of the above conditions, a contradiction to the maximality of (B 1 , . . . , B t ).

♢ Claim 5.15.2. Let i ∈ [t]. There is a set Y i ⊆ B i ∪ A such that def Inv(T ′ ;Yi) (b) = 0 for all b ∈ B i . Proof of claim. Let p = max{def Inv(T ′ ;Bi) (b) | b ∈ B i }. Observe that p ≤ max{def T ′ (b) + q -1 | b ∈ B i }. Hence, as E 1 does not occur and q = ⌈ 1 4 log k⌉ ≤ log k √ k, we have p ≤ 2 log k √ k + log k √ k = 3 log k √ k.
We shall now build a sequence of sets Y 0 i , . . . , Y p i with the following properties:

• Y 0 i = B i ,
• Y j+1 i is obtained from Y j i by adding one vertex from A \ Y j i for j = 0, . . . , p -1,

• max{def Inv(T ′ ;Y j i ) (b) | b ∈ B i } = p -j for j = 0, . . . , p.
The statement then follows for Y i = Y p i . Suppose that we have already created the sets Y 0 i , . . . , Y j i for some j with 0 ≤ j ≤ p -1 and now want to create Y j+1 i . Let (b 1 , . . . , b q ) be an arbitrary ordering of the vertices in B i . For every µ ∈

[q], if max{def Inv(T ′ ;Y j i ) (b) | b ∈ B i } = d - Inv(T ′ ;Y j i ) (b µ ) -k, let ⋆ µ = -, if max{def Inv(T ′ ;Y j i ) (b) | b ∈ B i } = k -d - Inv(T ′ ;Y j i ) (b µ ), let ⋆ µ = +, otherwise choose ⋆ µ ∈ {+, -} arbitrarily. As E 2 does not occur, ⃗ b 1 , . . . , ⃗ b q are linearly independent. Moreover, as E 3 does not occur, | q µ=1 N ⋆µ T ′ (b µ ) ∩ A| ≥ 5 log k √ k. As p ≤ 3 log k √ k, and q ≤ log k √ k, we have |Y j i | ≤ p + q ≤ 4 log k √ k. Thus ( q µ=1 N ⋆µ T ′ (b µ ) ∩ A) \ Y j i ̸ = ∅.
We can hence choose some y ∈ (

q µ=1 N ⋆µ (b µ ) ∩ A) \ Y j i and define Y j+1 i = Y j i ∪ {y}. By definition, Y j+1 i is obtained from Y j i by adding one vertex in A \ Y j i .
In order to see that the last property holds, let µ ∈

[q]. If max{def Inv(T ′ ;Y j i ) (b) | b ∈ B i } = d - Inv(T ′ ;Y j i ) (b µ ) -k, we have ⋆ µ = -and hence y ∈ N - Inv(T ′ ;Y j i ) (b µ ). As d - Inv(T ′ ;Y j i ) (b µ ) -k > 0, we obtain def Inv(T ′ ;Y j+1 i ) (b µ ) = d - Inv(T ′ ;Y j+1 i ) (b µ ) -k = d - Inv(T ′ ;Y j i ) (b µ )-k -1 = p-j -1 = p-(j +1). Similarly, if max{def Inv(T ′ ;Y j i ) (b) | b ∈ B i } = k -d - Inv(T ′ ;Y j i ) (b µ ), then def Inv(T ′ ;Y j+1 i ) (b) = p -(j + 1). Otherwise, let b ′ ∈ B with def Inv(T ′ ;Y j i ) (b ′ ) = p -j. As def T ′ (b µ ) ≡ def T ′ (b ′ ) mod 2, we have def Inv(T ′ ;Y j i ) (b µ ) ≡ def T ′ (b µ ) + |Y j i | -1 ≡ def T ′ (b ′ ) + |Y j i | -1 ≡ def Inv(T ′ ;Y j i ) (b ′ ) mod 2, hence def Inv(T ′ ;Y j i ) (b µ ) ≤ def Inv(T ′ ;Y j i ) (b ′ ) -2. This yields def Inv(T ′ ;Y j+1 i ) (b µ ) ≤ def Inv(T ′ ;Y j i ) (b µ ) + 1 ≤ def Inv(T ′ ;Y j i ) (b ′ ) -2 + 1 = p -(j + 1). ♢ Let T ′′ = Inv(T ′ ; (Y 1 , . . . , Y t )).
Observe that by definition of the sets Y i , we have def

T ′′ (b) = 0 for all b ∈ t i=1 B i . As | t i=1 B i | = qt ≤ 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 UG(T )⟨

t i=1 B i ⟩ ∪ δ UG(T ) ( t i=1 B i )
have the same orientation in T ′′ and T ′′′ . Further, by Proposition 5.12, there is a collection of r = |V (T )

\ t i=1 B i | -1 subsets Z 1 , . . . , Z r of V (T ) \ t i=1 B i such that Inv(T ′′ ⟨V (T ) \ t i=1 B i ⟩; Z 1 , . . . , Z r ) = T ′′′ ⟨V (T ) \ t i=1 B i ⟩. We obtain that Inv(T ; X 1 , . . . , X q * , Y 1 , . . . , Y t , Z 1 , . . . , Z r ) = Inv(T ′ ; Y 1 , . . . , Y t , Z 1 , . . . , Z r ) = Inv(T ′′ ; Z 1 , . . . , Z r ) = T ′′′ . As T ′′′ is k-arc-strong, we have sinv ′ k (T ) ≤ q * + t + r. Now q * = ⌈log 2 k⌉, t ≤ 2k 3q = 2k 3⌈ 1 4 log k⌉ , and r = |V (T )| -| t i=1 B i | -1 ≤ 2k -( 2 3 k -q) = 4 3 k +q = 4 3 k +⌈ 1 4 log k⌉ by Claim 5.15.1. Thus sinv ′ k (T ) ≤ 4 3 k +⌈log 2 k⌉+⌈ 1 4 log k⌉+ 2k 3⌈ 1 4 log k⌉ ≤ 4 3 k + ϵk.
In the following lemmas, we show that the probability for each of E 1 , E 2 and E 3 is small.

Lemma 5.16. Pr(E 1 ) < 1 3 .

Proof. Let b ∈ B. We first bound the probability that ⃗ b = ⃗ 0. Due to the independent and uniform choice of (X 1 , . . . , X q * ), we have

Pr[ ⃗ b = ⃗ 0] = 2 -q * ≤ 2 -2 log k = 1 k 2 . Now suppose that ⃗ b ̸ = ⃗ 0.
Once ⃗ b revealed, for every v ∈ V (T ), let Γ v be a random variable which is 1 if T ′ contains the arc bv and 0 otherwise and let Γ = v∈V (T -b) Γ v . Observe that, due to the independent and uniform choice of (X 1 , . . . , X q * ), we have Pr(Γ v = 1) = 1 2 for all v ∈ V (T -b) and the Γ v are independent. This yields that Γ ∼ Bin(2k, 1 2 ). Further, observe that def

T ′ (b) ≤ 2 log k √ k if and only if k -2 log k √ k ≤ Γ ≤ k + 2 log k √ k. By Chernoff's Bound (Proposition 2.6), we obtain Pr[Γ < k -2 log k √ k] ≤ Pr Γ < 1 - 2 log k √ k k k ≤ exp - 4k log 2 k 2k 2 k ≤ exp(-2 log k) ≤ exp(-2 ln k) = 1 k 2 .
Similarly, since 2k -Γ ∼ Bin(2k, 1 2 ), we obtain that

Pr[Γ > k + 2 log k √ k] ≤ 1 k 2 . This yields that Pr[def T ′ (b) > 2 log k √ k] = Pr[ ⃗ b = ⃗ 0] • Pr[def T ′ (b) > 2 log k √ k | ⃗ b = ⃗ 0] + Pr[ ⃗ b ̸ = 0] • Pr[def T ′ (b) > 2 log k √ k | ⃗ b ̸ = ⃗ 0] ≤ Pr[ ⃗ b = ⃗ 0] + Pr[Γ < k -2 log k √ k | ⃗ b ̸ = ⃗ 0] + Pr[Γ > k + 2 log k √ k | ⃗ b ̸ = ⃗ 0] ≤ 3 k 2 .
As there are k + 1 vertices contained in B, by the Union Bound (Proposition 2.5), Pr(E 1 ) ≤ (k + 1) 3 k 2 < 1 3 , as k ≥ 10.

Lemma 5.17. Pr(E 2 ) < 1 3 .

Proof. Let b 1 , . . . , b q ∈ B. Recall that ⃗ b 1 , . . . , ⃗ b q are independent and uniformly distributed. For i ∈ [q], observe that if ⃗ b 1 , . . . , ⃗ b i are linearly independent, they span a vector space containing 2 i elements. Hence

Pr[ ⃗ b 1 , . . . , ⃗ b q linearly dependent] = q i=1 Pr[ ⃗ b 1 , . . . , ⃗ b i linearly dependent | ⃗ b 1 , . . . , ⃗ b i-1 linearly independent ] × Pr[ ⃗ b 1 , . . . , ⃗ b i-1 linearly independent] ≤ q i=1 Pr[ ⃗ b 1 , . . . , ⃗ b i linearly dependent | ⃗ b 1 , . . . , ⃗ b i-1 linearly independent] = q i=1 2 i-1 2 q * ≤ 2 q 2 q * ≤ 2 -2 log(k)q because q * ≥ log 2 k ≥ 3 log(k)q ≥ 2 log(k)q + q = k -2q .
Observe that there are k+1 q possibilities to choose b 1 , . . . , b q . Hence the Union Bound (Proposition 2.5) yields Pr(E 2 ) ≤ k+1 q k -2q ≤ (2k) q k -2q = 2 k q < 1 3 as q ≥ 1 and k ≥ 7.

Lemma 5.18. Pr(E 3 ) < 1 3 .

Proof. Let b 1 , . . . , b q ∈ B such that ⃗ b 1 , . . . , ⃗ b q are linearly independent and let (⋆ 1 , . . . , ⋆ q ) ∈ {+, -} q . Once ⃗ b 1 , . . . , ⃗ b q revealed, for every a ∈ A, let Γ a be a random variable that is 1 if a ∈ q i=1 N ⋆i T ′ (b i ) and 0 otherwise and let Γ = a∈A Γ a . Observe that, due to the independent and uniform choice of (X 1 , . . . , X q * ) and by Proposition 5.11, we have that Pr[Γ a = 1] = 1 2 q for all a ∈ a and that the Γ a are independent. This yields that Γ ∼ Bin(k, 1 2 q ). Further observe that

Γ = | q i=1 N ⋆i T ′ (b i ) ∩ A|. Now, since 10 log k ≤ k 1 8 and q = ⌈ 1 4 log k⌉ ≤ 3 8 log k, we obtain 5 log k √ k ≤ 1 2 k 5 8 = 1 2 k2 -3 8 log k ≤ 1 2 k2 -q
. By Chernoff's Bound (Proposition 2.6), we obtain

Pr[Γ < 5 log k √ k] ≤ Pr Γ < 1 - 1 2 k2 -q ≤ exp - 1 8 k2 -q ≤ exp - 1 8 k 1 2 ≤ exp(-2q log k) because √ k ≥ 16 log k⌈ 1 4 log k⌉ ≤ exp(-2q ln k) = k -2q .
Observe that there are k+1 q possibilities to choose b 1 , . . . , b q and for each of those, there are 2 q possibilities to choose (⋆ 1 , . . . , ⋆ q ). Hence the Union Bound (Proposition 2.5) yields Pr(E 3 ) ≤ k+1 q 2 q k -2q ≤ (2k) q 2 q k -2q = 4 k q < 1 3 , as q ≥ 1 and k ≥ 13. 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.

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 ≤ 4 3 k + o(k). Proof. Let ϵ > 0.
We shall prove that there is an integer k * such that for every k ≥ k * and for every tournament T on at least 2k + 1 vertices, we have sinv ′ k (T ) ≤ ( 4 3 + ϵ)k. By Theorem 5.14, there is an integer k 0 such that for every k ≥ k 0 and for every tournament T on at least 2k + 1 vertices, we have

sinv ′ k (T ) ≤ ( 4 3 + ϵ 2 )k. Further, let k 1 be an integer such that ϵ 2 k ≥ 6 log k √ k + 1, √ k ≥ 3 log k and log k ≥ 5 hold for all k ≥ k 1 . Set k * = max{k 0 , k 1 }.
We now fix an integer k ≥ k * and prove that for every tournament T on n ≥ 2k + 1 vertices, we have

sinv ′ k (T ) ≤ ( 4 3 + ϵ 2 )k + min{n -(2k + 1), 6 log k √ 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 ∈ V (T ) with min{d + T (v), d - T (v)} ≥ k. By the minimality of T , there is a collection X of ( 4 3 + ϵ 2 )k + min{(n -1) -(2k + 1), 6 log k √ k + 1} subsets of V (T -v) such that Inv(T -v; X ) is k-arc-strong. By Proposition 2.1, we obtain that Inv(T ; X ) is k-arc-strong. As ( 4 3 + ϵ 2 )k + min{(n -1) -(2k + 1), 6 log k √ k + 1} ≤ ( 4 3 + ϵ 2 )k + min{n -(2k + 1), 6 log k √ k + 1}, we obtain a contradiction. Case 2. 2k + 1 + 6 log √ k ≤ n ≤ 4k -2.
Let A be an arbitrary subset of V (T ) of size 2k + 1 + 6 log k √ k and let B = V (T ) \ A. We now choose a subset X of A uniformly at random and let T ′ = Inv(T ; B ∪ X). Now consider some b ∈ B. For every a ∈ A, let Γ a be the probability that ab ∈ A(T ′ ) and observe that Γ = a∈A Γ a is exactly |N - T ′ (b) ∩ A|. Due to the uniform choice of X, we have Pr[ab ∈ A(T )] = 1 2 and that the Γ a are independent. This yields Γ ∼ Bin(2k + 1 + 6 log k √ k, 1 2 ). By Chernoff's Bound (Proposition 2.6), we obtain

Pr[Γ < k] ≤ Pr Γ < 1 - log k √ k k 1 2 2k + 1 + 6 log k √ k ≤ exp(-log 2 (k)/2) ≤ exp(-2 log k) because k ≥ 16 ≤ exp(-2 ln k) = 1 k 2 .
Similarly, we obtain

Pr[|N + T ′ (b) ∩ A| < k] ≤ 1 k 2 . As B contains at most (4k -3) -(2k + 1 + 2 log k √ k) ≤ 2k
elements, the Union Bound (Proposition 2.5) yields that the probability that there is at least one

b ∈ B with min{|N - T ′ (b) ∩ A|, |N + T ′ (b) ∩ A|} ≤ k is at most 2 k 2 2k = 4 k < 1, as k ≥ 5.
Hence, with positive probability, we have min{|N -

T ′ (b) ∩ A|, |N + T ′ (b) ∩ A|} ≥ k for all b ∈ B.
Thus there is X 0 such that every vertex of B has in-and out-degree at least k in T ′ 0 = Inv(T ; B ∪ X 0 ). Further, by the minimality of T , there is a collection

X of sinv ′ k (T 0 ⟨A⟩) ≤ ( 4 3 + ϵ 2 )k + 6 log k √ k sets such that Inv(T ′ 0 ⟨A⟩) is k-arc-strong.
Hence, by Proposition 2.1, we obtain that Inv(T ; {X 0 } ∪ X ) is k-arc-strong, a contradiction.

Case 3. 2k + 2 ≤ n ≤ 2k + 6 log k √ k.
Let v ∈ V (T ) be an arbitrary vertex. We can then find a set X ⊆ V (T ) such that for T ′ = Inv(T ; X), we have

min{d + T ′ (v), d - T ′ (v)} ≥ k.
Further, by the minimality of T , there is a collection X of sinv ′ k (T ) ≤ ( 4 3 + ϵ 2 )k + n -(2k + 1) -1 sets such that Inv(T ′ ⟨A⟩; X ) is 2-arc-strong. Hence by Proposition 2.1, we obtain that Inv(T ; {X} ∪ X ) is k-arc-strong, a contradiction.

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 kstrong by a small number of inversions. More precisely, in Subsection 6.1, we prove Theorem 1.10, in Subsection 6.2, we prove Theorem 1.13, in Subsection 6.3, we prove Theorem 1.15, and in Subsection 6.4, we prove Theorem 1.16.

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. More precisely, we prove Theorem 1.10. While Theorem 1.10 is clearly weaker than Theorem 1.13, this result justifies some of the notation used later on, and may serve as a warm-up exercise of the more involved proof of Theorem 1.13.

Proof of Theorem 1.10. Let T be a tournament of order n ≥ (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 ⇒ (A 2 ∪ A 3 ) and A 2 ⇒ A 3 with |A 1 | = |A 3 | = k and |A 2 | = 2k -1. Set A = A 1 ∪ A 2 ∪ A 3 . Let I be the set of vertices in V (T ) \ A that have either less than k out-neighbours in A or less than k in-neighbours in A. Let X = A 1 ∪ A 3 ∪ I. Let us prove that T ′ = Inv(T ; X) is k-strong.
In T ′ , we have A 1 ⇒ A 2 ⇒ A 3 ⇒ A 1 . Since the three sets A 1 , A 2 , and A 3 have size at least k, the tournament

T ′ ⟨A⟩ is k-strong. Now consider a vertex v in V (T ) \ A. If v /
∈ 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 ∈ I, then all the arcs between v and A 1 ∪ A 3 have been reversed and those between v and A 2 are unchanged. If v has less than k out-neighbours in A in T , then

|N + T ′ (v)∩A| ≥ |N - T (v)∩(A 1 ∪A 3 )| ≥ 2k-d + T (v) ≥ k, and |N - T ′ (v)∩A| ≥ |N - T (v)∩A 2 | ≥ 2k-1-d + T (v) ≥ k. Similarly, if v has less than k in-neighbours in A in T , then |N + T ′ (v) ∩ A| ≥ k and |N - T ′ (v) ∩ A| ≥ k.
Thus, by Lemma 2.1, T ′ is k-strong. Hence sinv k (T ) ≤ 1.

Linear upper bound on N k (1)

In this subsection, we shall prove Theorem 1.13 which states that N k (1) ≤ 19k -2. To prove it we need some preliminaries.

For a digraph D, let σ = (v 1 , v 2 , . . . , v n ) be an ordering of the vertices of D. An arc v i v j is forward (according to σ) if i < j and backward (according to σ) 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 [START_REF] Havet | Median orders of tournaments: A tool for the second neighborhood problem and sumner's conjecture[END_REF]).

Lemma 6.1. Let T be a tournament and (v 1 , v 2 , . . . , v n ) a median order of T . Then, for any two indices i, j with 1 ≤ i < j ≤ n:

(M1) (v i , v i+1 , . . . , v j
) is a median order of the induced subtournament T ⟨{v i , v i+1 , . . . , v j }⟩.

(M2) the vertex v i dominates at least half of the vertices v i+1 , v i+2 , . . . , v j , and the vertex v j is dominated by at least half of the vertices v i , v i+1 , . . . , v j-1 . In particular, each vertex v i , 1 ≤ i < n, dominates its successor v i+1 .

Let v be a vertex of a digraph D. We denote by R + D (v) (resp. R - D (v)) the set of vertices which are reachable from v (resp. vertices that can reach v) in D, that are the vertices w such that there is a directed (v, w)-path (resp. (w, v)path) in D. Note that v ∈ R + D (v). Lemma 6.2. Let T be a tournament with median order (v 1 , v 2 , . . . , v n ). Let F be a subset of vertices such that Hence n -1 ≤ 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 ⟨{v 1 , . . . , v i0-1 }⟩, T 1 = T ⟨{v i0 , . . . , v n }⟩, F 0 = F ∩ V (T 0 ) and F 1 = F ∩ V (T 1 ). By (M1), (v 1 , v 2 , . . . , v i0-1 ) is a median order of T 0 and (v i0 , . . . , 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 ≤ 2|F 0 |. By the induction hypothesis,

v 1 / ∈ F . Then |R + T -F (v 1 )| ≥ n -2|F |.
|R + T1-F1 (v i0 )| ≥ n -i 0 + 1 -2|F 1 |. Now R + T1-F1 (v i0 ) ∪ {v 1 } ⊆ R + T -F (v). Hence |R + T -F (v)| ≥ |R + T1-F1 (v i0 )| + 1 ≥ n -i 0 + 2 -2|F 1 | ≥ n -2|F 0 | -2|F 1 | = n -2|F |.
Lemma 6.3. Let T be a tournament with median order (v 1 , v 2 , . . . , v n ). For any i ∈ [n] and any

F ⊆ V (T ) \ {v i }, we have |R + T -F (v i )| ≥ n + 1 -i -2|F |, and R - T -F (v i ) ≥ i -2|F |.
Proof. By (M1), (v i , . . . , v n ) is a median order of T ⟨{v i , . . . , v n }⟩ on which we can apply Lemma 6.2 to obtain the bound on R + T -F (v i ). Symmetrically, (v i , v i-1 , . . . , v 1 ) is a median order of the converse of T ⟨{v 1 , . . . , v i }⟩, and applying Lemma 6.2 to the converse of T yields the bound on R - T -F (v i ).

We are now ready to prove the main lemma of the proof of Theorem 1.13. Proof. Let (a 1 , . . . , a 6k ) be a median order of T ⟨A⟩ and let (b 1 , . . . , b 6k ) be a median order of T ⟨B⟩. Let A 0 be the set of vertices in {a 4k+1 , . . . , a 6k } which have less than k out-neighbours in B in T . Further, let

A 1 = {a 1 , . . . , a 2k-|A0| }. Observe that |A 0 ∪ A 1 | = |A 0 | + |A 1 | = 2k.
Similarly, let B 0 be the set of vertices in {b 1 , . . . , b 2k } that have less than k in-neighbours in A and let B 1 = {b 4k+|B0|+1 , . . . , b 6k }. Observe that

|B 0 ∪ B 1 | = |B 0 | + |B 1 | = 2k. Let X = A 0 ∪ A 1 ∪ B 0 ∪ B 1 and let T ′ = Inv(T ; X). Consider any Y ⊆ V (T ) with |Y | ≤ 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 \ Y for every a ∈ A \ Y . Suppose by contradiction that this is not true. Then there is a largest integer i ∈ [6k] such that a i ∈ A \ Y and T ′ -Y does not contain a directed path from a i to B \ Y . We will distinguish several cases.

Case 1. i ∈ {4k + 1, . . . , 6k} and a i ∈ A \ A 0 .

In this case, by the choice of A 0 , we have

|(N + T ′ (a i ) ∩ B) \ Y | ≥ |N + T ′ (a i ) ∩ B| -|Y | = |N + T (a i ) ∩ B| -|Y | ≥ k -(k -1) = 1, so a i has an out-neighbour in B \ Y in T ′ -Y , a contradiction.
Case 2. i ∈ {4k + 1, . . . , 6k} and a i ∈ A 0 .

In this case, by the choice of A 0 , we have

|(N + T ′ (a i ) ∩ B) \ Y | ≥ |N + T ′ (a i ) ∩ B| -|Y | ≥ |N + T ′ (a i ) ∩ (B 0 ∪ B 1 )| -|Y | = |B 0 ∪ B 1 | -|N - T ′ (a i ) ∩ (B 0 ∪ B 1 )| -|Y | = |B 0 ∪ B 1 | -|N + T (a i ) ∩ (B 0 ∪ B 1 )| -|Y | ≥ |B 0 ∪ B 1 | -|N + T (a i ) ∩ B| -|Y | ≥ 2k -(k -1) -(k -1) = 2, so a i has an out-neighbour in B \ Y in T ′ -Y , a contradiction. Case 3. i ∈ {2k -|A 0 | + 1, . . . , 4k}.
As (a 1 , . . . , a 6k ) is a median order of T ⟨A⟩, and by (M2) applied to T ⟨A⟩, we have

|(N + T ′ (a i ) ∩ {a i+1 , . . . , a 6k }) \ Y | ≥ |N + T ′ (a i ) ∩ {a i+1 , . . . , a 6k }| -|Y | ≥ |N + T (a i ) ∩ {a i+1 , . . . , a 6k }| -|Y | ≥ 1 2 |{a i+1 , . . . , a 6k }| -|Y | ≥ 1 2 (6k -i) -(k -1) = 2k + 1 - i 2 ≥ 2k + 1 -2k = 1.
Hence there is some j > i such that a j ∈ A \ 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 \ Y in T ′ -Y . Hence T ′ -Y also contains a directed path from a i to B \ Y , a contradiction. Case 4. i ∈ {1, . . . , 2k -|A 0 |}.

As (a 1 , . . . , a 6k ) is a median order of T ⟨A⟩ and by (M2) applied to T ⟨A⟩, we have

|(N + T ′ (a i ) ∩ {a i+1 , . . . , a 6k }) -Y | ≥ |N + T ′ (a i ) ∩ {a i+1 , . . . , a 6k }| -|Y | ≥ |N + T (a i ) ∩ {a i+1 , . . . , a 6k }| -|(A 0 ∪ A 1 ) ∩ {a i+1 , . . . , a 6k }| -|Y | ≥ 1 2 |{a i+1 , . . . , a 6k }| -|(A 0 ∪ A 1 ) ∩ {a i+1 , . . . , a 6k }| -|Y | ≥ 1 2 (6k -i) -(2k -i) -(k -1) = i 2 + 1 ≥ 1.
Hence there is some j > i such that a j ∈ A \ 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 \ Y in T ′ -Y . Hence T ′ -Y also contains a directed path from a i to B \ Y , a contradiction.

We are now ready to prove Theorem 1.13 which states

N k (1) ≤ 19k -2. Proof of Theorem 1.13. Assume n ≥ 19k -2. Let (v 1 , . . . , v n ) be a median order of T . Let B = {v 1 , . . . , v 6k }, A = {v n-6k+1 , . . . , v n } and C = V (T ) \ (A ∪ B).
We have |C| ≥ 7k -2. By Lemma 6.4, applied to T ⟨A ∪ B⟩, there is a subset X of A ∪ B such that, for T ′ = Inv(T ; X), we have Let T 1 = Inv(T ; X). Let us now prove that T 1 is k-strong, which implies sinv k (T ) ≤ 1. Let F be a set of at most k -1 vertices of T 1 . We first need the following intermediate result. Proof of claim. By construction, there is some i ∈ {1, . . . , 6k} such that b = v i . Let T ′ = T ⟨{v i , . . . , v n-6k }⟩. By (M2), every vertex in ((X ∩ B) ∪ F ) ∩ {v i , . . . , v n-6k } and every vertex in C \ F is reachable from b in T ′ . On the other hand, there is obviously no vertex in ((

X ∩ B) ∪ F ) ∩ {v i , . . . , v n-6k } reachable from b in T ′ -((X ∩ B) ∪ F ). By Lemma 6.3, this yields 2|((X ∩ B) ∪ F ) ∩ {v i , . . . , v n-6k }| ≥ |R + T ′ (b)| -|R + T ′ -((X∩B)∪F ) (b)| = |R + T ′ (b) ∩ B| -|R + T ′ -((X∩B)∪F ) (b) ∩ B| + |R + T ′ (b) ∩ (C ∩ F )| -|R + T ′ -((X∩B)∪F ) (b) ∩ (C ∩ F )| + |R + T ′ (b) ∩ (C \ F )| -|R + T ′ -((X∩B)∪F ) (b) ∩ (C \ F )| ≥ |((X ∩ B) ∪ F ) ∩ {v i , . . . , v n-6k }| + |C \ F | -|R + T ′ -((X∩B)∪F ) (b) ∩ (C \ F )|. For every v ∈ C \ F , if v is reachable from b in T ′ -((X ∩ B) ∪ F ), then v is clearly reachable from b in T 1 -F . Since |X ∩ B| ≤ 2k and |F | ≤ k -1, we obtain |R + T1-F (b) ∩ (C \ F )| ≥ |R + T ′ -((X∩B)∪F ) (b) ∩ (C \ F )| ≥ |C \ F | -|((X ∩ B) ∪ F ) ∩ {v i , . . . , v n-6k }| ≥ |C \ F | -(|X ∩ B| + |F |) ≥ |C \ F | -(2k + (k -1)) = |C \ F | -(3k -1). A similar argument shows that |R - T1-F (a) ∩ (C \ F )| ≥ |C \ F | -(3k -1). As |C| ≥ n -12k ≥ 7k -2, we obtain |(R + T1-F (b) ∩ (C \ F )) ∩ (R - T1-F (a) ∩ (C \ F ))| = |R + T1-F (b) ∩ (C \ F )| + |R - T1-F (a) ∩ (C \ F )| -|(R + T1-F (b) ∩ (C \ F )) ∪ (R - T1-F (a) ∩ (C \ F ))| ≥ |R + T1-F (b) ∩ (C \ F )| + |R - T1-F (a) ∩ (C \ F )| -|C \ F | ≥ 2(|C \ F | -(3k -1)) -|C \ F | = |C \ F | -2(3k -1) ≥ |C| -|F | -(6k -2) ≥ (7k -2) -(k -1) -(6k -2) ≥ 1. Hence there is a vertex v * ∈ {v 6k+1 , . . . , v n-6k } ∩ (R + T1 (b) ∩ (C \ F )) ∩ (R - T1 (a) ∩ (C \ 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. ♢

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 \ F . Clearly, we may suppose that x ∈ (A ∪ C) \ F. Then, since |A| > 2|F |, Lemma 6.2 implies that there is a vertex x ′ ∈ A \ F reachable from x in T -F -B, and so in T 1 -F . By (iii), there is a directed path from x ′ to a vertex u in B \ 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 ∈ A \ 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 QP y is a path from x to y in T 1 -F . This proves that T 1 -F is strong.

Finally, we give the proof of Proposition 1.14, which states N k (1) ≥ 5k -2.

Proof of Proposition 1.14. Let T be a tournament of order 5k -3 whose vertex set has a partition (A, B, C) such that T ⟨A⟩ and T ⟨C⟩ are (k -1)-diregular tournaments of order 2k -1, and A ⇒ B ∪ C and B ⇒ C. We shall prove that sinv ′ k (T ) > 1.

Assume for a contradiction that there is a set X of vertices such that T ′ = Inv(T ; X) is k-strong. Every vertex of A (resp. C) has in-degree (resp. out-degree) k -1 in T , and so belongs to X. Thus A ∪ C ⊆ X, and so

C ⇒ A in T ′ . Hence T ′ -B is not strong. Since |B| = k -1, T ′ is not k-strong, a contradiction.

Better upper bound on N k (3)

This section is dedicated to the proof of Theorem 1.15. The structure is analogous to the proof of Theorem 1.13 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 X of three subsets of V (T ) such that the following hold with T ′ = Inv(T ; X ).

(i) T ′ ⟨A⟩ = T ⟨A⟩ and T ′ ⟨B⟩ = T ⟨B⟩ ; (ii) for any Y ⊆ V (T ) with |Y | ≤ k -1, T ′ -Y contains a directed path from a to B \ Y for every a ∈ A \ Y ; (iii) for any Y ⊆ V (T ) with |Y | ≤ k -1, T ′ -Y contains a directed path from A \ Y to b for every b ∈ B \ Y .
Proof. Let (a 1 , . . . , a 4k ) be a median order of T ⟨A⟩ and let (b 1 , . . . , b 4k ) be a median order of T ⟨B⟩. Let A 0 be the set of vertices in {a 2k+1 , . . . , a 4k } which have less than k out-neighbours in B in T . Further, let

A 1 = {a 1 , . . . , a 2k-|A0| }. Observe that |A 0 ∪ A 1 | = |A 0 | + |A 1 | = 2k.
Similarly, let B 0 be the set of vertices in {b 1 , . . . , b 2k } that have less than k in-neighbours in A and let B 1 = {b 2k+|B0|+1 , . . . , b 4k }. Observe that

|B 0 ∪ B 1 | = |B 0 | + |B 1 | = 2k. Now let X 1 = A 0 ∪ A 1 , X 2 = B 0 ∪ B 1 , X 3 = X 1 ∪ X 2 , and X = (X i ) i∈[3]
Let T ′ = Inv(T ; 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 ⊆ V (T ) with |Y | ≤ k -1. Suppose for the sake of a contradiction that (ii) does not hold. There is a largest integer i ∈ [4k] such that a i ∈ A \ Y and T ′ -Y does not contain a directed path from a i to B \ Y . We will distinguish several cases.

Case 1. i ∈ {2k + 1, . . . , 4k} and a i ∈ A \ A 0 .

In this case, by the choice of A 0 , we have

|(N + T ′ (a i ) ∩ B) \ Y | ≥ |N + T ′ (a i ) ∩ B| -|Y | = |N + T (a i ) ∩ B| -|Y | ≥ k -(k -1) = 1,
= k + 1 - i 2 ≥ k + 1 -k = 1.
• t ≥ 128 ϵ (2C + 2 + ϵ/4) + 16. Clearly, t is well defined and depends only on ϵ. Let k 0 (ϵ) be the smallest integer such that for every k ′ ≥ k 0 (ϵ) (2 t -1) exp -ϵ 2 (2 + ϵ)k ′ 24 + 3(Ck ′ ) 2 exp -ϵ 2 (2 + ϵ)k ′ 4096 + 2 -k ′ < 1.

(1)

We now prove the statement for f (ϵ) = max{t, 2k 0 (ϵ) -2, ⌈ 16t ϵ ⌉ -2}. If k < k 0 (ϵ), then we conclude directly using Theorem 5.8 that sinv k (T ) ≤ 2k ≤ 2k 0 (ϵ) -2 ≤ f (ϵ). Similarly, if k ≤ 8t ϵ -1, then we conclude by Theorem 5.8 that sinv k (T ) ≤ 16t ϵ -2 ≤ f (ϵ). Moreover, if n ≥ Ck, we have sinv k (T ) ≤ 1 ≤ f (ϵ). Henceforth, we may assume k ≥ max{k 0 (ϵ), 8t ϵ -1} and n ≤ Ck. For every vertex u ∈ V (T ), we choose uniformly and independently at random a vector ⃗ u ∈ F t 2 \ { ⃗ 0}. For i ∈ [t], let X i = {u ∈ V (T ) | ⃗ u i = 1}. We will prove that with positive probability, the tournament T ′ = Inv(T ; X 1 , . . . , X t ) is k-strong. Note that for every arc uv ∈ A(T ), we have uv ∈ A(T ′ ) if and only if ⃗ u • ⃗ v = 0 mod 2. 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 z ∈ F t 2 \ { ⃗ 0} such that |{v ∈ V (T ) | ⃗ v ̸ = z}| ≤ k, E 2 : there are u, v ∈ V (T ) with ⃗ u ̸ = ⃗ v such that min{|N + T ′ (u)∩N - T ′ (v)|, |N + T ′ (u)∩N + T ′ (v)|, |N - T ′ (u)∩N - T ′ (v)|} ≤ (1 + ϵ/4) k 2 ,
E 3 : there are disjoint sets A, B ⊆ V (T ′ ) with |A|, |B| ≥ (1 + ϵ/4) k 2 with no directed (A, B)-matching of size 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 ⇒ V 1 in T ′ -X. Since E 1 does not hold, there exist x, y ∈ V 1 ∪ V 2 with ⃗ x ̸ = ⃗ y. If both x and y are in V 1 (resp. V 2 ), consider v ∈ V 2 (resp. u ∈ V 1 ) and either ⃗ x ̸ = ⃗ v or ⃗ y ̸ = ⃗ v (resp. ⃗ x ̸ = ⃗ u or ⃗ y ̸ = ⃗ u). If x ∈ V 1 and y ∈ V 2 we set u = x and v = y, and if y ∈ V 2 and x ∈ V 1 we set u = y and v = x. In all cases, there are u ∈ V 1 and v ∈ V 2 with ⃗ u ̸ = ⃗ v. Now, as E 2 does not hold, we have

|N + T ′ (u) ∩ N - T ′ (v)|, |N + T ′ (u) ∩ N + T ′ (v)|, |N - T ′ (u) ∩ N - T ′ (v)| ≥ (1 + ϵ/4) k 2 .
Finally, as E 3 does not hold, there is a directed (N + T ′ (u) ∩ N + T ′ (v), N - T ′ (u) ∩ N - T ′ (v))-matching M of size k/2 in T ′ . For every arc e = xy ∈ M , observe that P e = uxyv is a directed (u, v)-path in T ′ . Furthermore, for every x ∈ N + T ′ (u) ∩ 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. ♢

We will show that with high probability none of the events E 1 , E 2 and E 3 occurs. Claim 6.9.2. Pr(E 1 ) ≤ (2 t -1) exp(-ϵ 2 n/24)

Proof of claim. If ⃗ c ∈ F t 2 \ { ⃗ 0} is fixed, then Y ⃗ c = |{u ∈ V (T ) | ⃗ u ̸ = ⃗ c}|
is a random variable having a binomial law with parameters n and 1 -1 2 t -1 . As ϵ ≤ 1 3 and t ≥ 2, we have k ≤ 1 2 n ≤ 2 3 • 5 6 n ≤ (1 -1 2 t -1 )(1 -ϵ/2)n. By Chernoff's Bound (Proposition 2.6), and because t ≥ 2, we have

Pr[∃⃗ c ∈ F t 2 \ { ⃗ 0}, Y ⃗ c < k] ≤ ⃗ c∈F t 2 \{0} Pr[Y ⃗ c < k] ≤ ⃗ c∈F t 2 \{0} Pr Y ⃗ c < 1 - ϵ 2 1 - 1 2 t -1 n ≤ (2 t -1) exp -(ϵ/2) 2 1 - 1 2 t -1 n/3
≤ (2 t -1) exp(-ϵ 2 n/24),

We can now conclude using Claims 6.9.1, 6.9.2, 6.9.3 and 6.9.4 and the Union Bound:

Pr[T ′ not k-strong] ≤ Pr(E 1 ) + Pr(E 2 ) + Pr(E 3 ) ≤ (2 t -1) exp -ϵ 2 n 24 + 3n 2 exp -ϵ 2 n -2 4096 + 2 -k ≤ (2 t -1) exp -ϵ 2 (2 + ϵ)k 24 + 3(Ck) 2 exp -ϵ 2 (2 + ϵ)k 4096 + 2 -k < 1, by (1). This proves that there exist X 1 , . . . , X t ⊆ V (T ) such that T ′ = Inv(T ; X 1 , . . . , X t ) is k-strong.

Conclusion

In this paper, we investigated problems of the form: given a digraph, what is the minimum number of inversions needed such that the resulting digraph has a prescribed connectivity property? For the first part, it is tempting to understand better the asymptotic behaviour of sinv k (n). In particular, it would be interesting to see if an analogue of Theorem 1.1 exists for sinv k . For the algorithmic part, one may wonder whether polynomial-time constant-factor-approximation algorithms for computing sinv k or sinv ′ k exist. Actually, we believe that this is not the case and that Theorems 1.3 and 1.5 can be strengthened in the following way: k . There is still a significant gap between the logarithmic lower bounds and the linear upper bounds, so it would be good to improve these. A first question is the following. Further, we 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 an integers i. In particular, a tight bound for N k (1) would be satisfying.

Finally, Theorem 1.16 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 ϵ > 0, there is an integer k 0 with the property that for every k ≥ k 0 , if T is a tournament on at least (2 + ϵ)k vertices, then we have sinv k (T ) ≤ t? Proposition 1.14 shows that such an integer would have to satisfy t ≥ 2, so t = 2 is the first open case. The analogous statement for sinv ′

k is also open.

  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-)strenghtening family of T -v is also a k-(arc-)strenghtening family of T . Thus sinv k

  for all vertex v. Let A and B be two sets in D. If ab is an arc for all pair (a, b) in A × B, then we write A ⇒ B.

  Theorem 4.2. Deciding whether sinv ′ k (D) ≤ 1 for a given oriented graph D is NP-complete. Theorem 4.3. Deciding whether sinv k (D) ≤ 1 for a given k-strengthenable oriented graph D is NP-complete.

  Claim 4.3.1. The following are equivalent: (i) (X, C) is a positive instance of MEkSAT; (ii) D(X, C) can be made k-strong by inverting a single set Z; (iii) D(X, C) can be made k-arc-strong by inverting a single set Z. Proof of claim. Set D = D(X, C).

  Lemma 4.5. Given a graph G and a positive integer k, one can construct in polynomial time some oriented graph D such that sinv ′ k (D) = cc(G) and |V (D)| = |V (G)| + (2k + 1)|E(G)| + 2k + 1.

  exactly one of u and v. Proof of claim. Suppose otherwise. As D ′ is k-arc-strong and d D (Z e ) = 2k, we have d - D ′ (Z e ) = d + D ′ (Z e ) = k. For every i ∈ [t] either both u and v or none of u and v are contained in X i . Thus we deduce that for every j ∈ [k], either both the arcs corresponding to edges in ∂ D (Z e ) ∩ ∂ D (z j e ) are inverted or none of them are. Hence, in D ′ , there is exactly one arc entering Z e incident to z j e for j = 2, . . . , k, and there are either zero or two arcs entering Z e incident to z 1 e . Thus d - D ′ (Z e ) ∈ {k -1, k + 1}, a contradiction. ♢ By Claim 4.5.1, we obtain that (X ′ 1 , . . . , X ′ t ) is a cut cover for G. Hence cc(G) ≤ t = sinv ′ k (D).

Lemma 4. 7 .

 7 Given a graph G and a positive integer k, one can construct in polynomial time a k-strengthenable oriented graph D such that sinv k (D) = cc(G) and |V (D)| = |V (G)| + (2k + 1)|E(G)| + 2k + 1. Proof. We let V (D) contain V (G), a set of vertices Z e = {z 1 e , . . . , z 2k+1 e } for every e ∈ E(G) and a set of vertices W = {w 1 , . . . , w 2k+1 }. We add arcs to D such that D⟨W ⟩ is a k-strong tournament. We let A(D) contain an arc from v to w i for every v ∈ V (G) and every i ∈ [k] and an arc from w i to v for every v ∈ V (G) and every i ∈ {k + 1, . . . , 2k}. Next for every e ∈ E(G), we add arcs to D such that D⟨Z e ⟩ is a k-strong tournament. Further, for every e ∈ E(G), i ∈ [k] and j ∈ [k -1], we add an arc from z i e to w j and for every e ∈ E(G), i ∈ {k + 1, . . . , 2k} and j ∈ [k -1], we add an arc from w j to z i e . Finally, for every e = uv ∈ E(G), we add the arcs uz 1 e and vz 1 e . This finishes the description of D. Observe that |V (D)| = |V (G)| + (2k + 1)|E(G)| + 2k + 1.

  then there is at least one arc from Z e \ Y to W \ Y and there is at least one arc from W \ Y to Z e \ Y , so Z e \ Y ⊆ S. Finally, if Y = {w 1 , . . . , w k-1 }, observe that, by construction, either D ′ contains the arcs uz 1 e and z 1 e v or the arcs vz 1 e and z 1 e u. Again, we obtain Z e \ Y ⊆ S. This yields that D ′ is k-strong. We hence have sinv k (D) ≤ t = cc(G).

  , b, c, d, e, f } with {a, b, c} ⇒ {d, e, f }. Then inverting {a, b, c, d} and {a, d, e, f } transforms T into a 2-strong tournament.

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 )| ≤ |N + T (v 1 )| ≤ |F |.

Lemma 6. 4 .

 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 ⊆ V (T ) with |X ∩ A| = |X ∩ B| = 2k such that for T ′ = Inv(T ; X) and for any Y ⊆ V (T ) with |Y | ≤ k -1, we have that T ′ -Y contains a directed path from a to B \ Y for every a ∈ A \ Y , and T ′ -Y contains a directed path from A \ Y to b for every b ∈ B \ Y .

( i )

 i |X ∩ B| = |X ∩ A| = 2k ; (ii) for any Y ⊆ V (T ) with |Y | ≤ k -1, T ′ -Y contains a directed path from a to B \ Y for every a ∈ A \ Y ; (iii) for any Y ⊆ V (T ) with |Y | ≤ k -1, T ′ -Y contains a directed path from A \ Y to b for every b ∈ B \ Y .

  Claim 6.4.1. Let b ∈ B \ F and a ∈ A \ F . Then T 1 -F contains a directed path from b to a.

  so a i has an out-neighbour in B \ Y in T ′ -Y , a contradiction.Case 2. i ∈ {2k + 1, . . . , 4k} and a i ∈ A 0 .In this case, by the choice of A 0 , we have|(N + T ′ (a i ) ∩ B) \ Y | ≥ |N + T ′ (a i ) ∩ B| -|Y | ≥ |N + T ′ (a i ) ∩ (B 0 ∪ B 1 )| -|Y | = |B 0 ∪ B 1 | -|N - T ′ (a i ) ∩ (B 0 ∪ B 1 )| -|Y | = |B 0 ∪ B 1 | -|N + T (a i ) ∩ (B 0 ∪ B 1 )| -|Y | ≥ |B 0 ∪ B 1 | -|N - T ′ (a i ) ∩ B| -|Y | ≥ 2k -(k -1) -(k -1) = 2, so a i has an out-neighbour in B \ Y in T ′ -Y , a contradiction. Case 3. i ∈ [2k].As (a 1 , . . . , a 4k ) is a median order of T ⟨A⟩ = T ′ ⟨A⟩, by (M2) we have|(N + T ′ (a i ) ∩ {a i+1 , . . . , a 4k }) \ Y | ≥ |N + T ′ (a i ) ∩ {a i+1 , . . . , a 4k }| -|Y | = |N + T (a i ) ∩ {a i+1 , . . . , a 4k }| -|Y | ≥ 1 2 |{a i+1 , . . . , a 4k }| -|Y | ≥ 1 2 (4k -i) -(k -1)

  Problem 7.1. Let sinv k (n) = max{sinv k (D) | D k-strengtenable digraph of order n}. Find a good lower and upper bounds on sinv k (n).

Conjecture 7. 2 .

 2 Unless P=NP, for any positive integer k and any constant α, there is no α-approximation algorithm for computing sinv k (D) or sinv ′ k (D) given an oriented graph D. It would further be interesting to understand the complexity when restricting to tournaments. While the complexity for fixed k is resolved by Corollary 1.17, the following question remains open: Problem 7.3. What is the complexity of computing sinv k (T ) (resp. sinv ′ k (T )) for a given tournament T if k is part of the input ? Next, we established several bounds on M k and M ′

  Problem 7.4. Are M ′ k and M k sublinear functions of k ?

  al. [AHH + 22] and Alon et al. [APS + 22] proved n -2

√ n log n ≤ inv(n) ≤ n -⌈log(n + 1)⌉.

Hence there is some j > i such that a j ∈ A \ 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 \ Y in T ′ -Y . Hence T ′ -Y also contains a directed path from a i to B \ Y , a contradiction.

Theorem 1.15. For any positive integer k, we have

Proof. Assume n ≥ 11k -2. Let (v 1 , . . . , v n ) be a median order of T . Let B = {v 1 , . . . , v 4k }, A = {v n-4k+1 , . . . , v n } and C = V (T ) \ (A ∪ B). We have |C| ≥ 3k -2. By Lemma 6.5 applied to T ⟨A ∪ B⟩, there is a family X of three subsets of A ∪ B such that for T ′ = Inv(T ; X ) we have (i) T ′ ⟨A⟩ = T ⟨A⟩ and T ′ ⟨B⟩ = T ⟨B⟩ ;

(ii) for any

Let T 1 = Inv(T ; X ). Let us now prove that T 1 is k-strong, which implies sinv k (T ) ≤ 3. Note that T ⟨A ∪ C⟩, as well as T ⟨B ∪ C⟩ 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 ∈ B \ F that is reachable from x in T 1 -F . It is trivial if x ∈ B, so we may suppose that x ∈ A ∪ C. Lemma 6.2 asserts that from any vertex of (A ∪ C) \ F one can reach a vertex of A \ F in T 1 -F . Thus there exists a vertex x ′ ∈ A \ F reachable from x in T 1 -F . By (iii), there is a directed path from x ′ to a vertex of u in B \ F in T ′ -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 ∈ A \ F to y.

By Lemma 6.2,

T ⟨A∪C⟩-F (w), and so there exists a directed path Q from u to w in T 1 -F . Then P x QP y is a directed path from x to y in T 1 -F .

All the results of the previous subsections imply the following.

6.4 Upper bounds for k large.

In this section, we show that if a tournament has at least 2k + 1 + ϵk vertices for some positive integer k and some ϵ > 0, then it can be made k-strong by inversing a family of sets whose cardinality only depends on ϵ. 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.

is surjective and linear. As a consequence, there are

Thus by possibly removing the solution ⃗ w = 0, we obtain

Lemma 6.8. Let ϵ > 0, let t ≥ 16 be an integer, and let k ≥ 8t ϵ be an integer. Let U, V ∈ (F t 2 \ { ⃗ 0}) ⌈ϵk/8⌉ be drawn uniformly at random and

Proof. Note that since k ≥ 8t ϵ , we have ⌈ϵk/8⌉ ≥ t ≥ t/2 + 1. First we bound the probability that rk(U ) < t/2 + 1. If U has rank at most t/2, then there is a choice of ⌊t/2⌋ columns of U such that all the other ones are in the linear span of these selected columns. Since the linear span of ⌊t/2⌋ vectors has dimension at most t/2, and so size at most 2 t/2 , we deduce the following.

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 -⌊t/2⌋ -1 ≤ t/2. It follows that

Therefore

We know that tϵk ≥ 8t 2 ≥ 2 • 64, thus 2 -tϵk/64 ≤ 1/4. As 2x ≤ √ x for any x ∈ [0, 1/4], we end with

For technical reasons, we prove the following seemingly weaker restatement of Theorem 1.16. Theorem 6.9. There exists a function f : R >0 → N such that for every ϵ > 0 and every positive integer k, if T is an n-vertex tournament with n ≥ 2k + 2ϵk + 2, then sinv k (T ) ≤ f (ϵ).

It is not difficult to see that Theorem 6.9 actually implies Theorem 1.16. Indeed, given a function f like in Theorem 6.9 at hand, define

Once ⃗ u and ⃗ v revealed, for every vertex w ̸ = u, v, let Y w be a random variable with Y w = 1 if w ∈ X, Y w = 0 otherwise. By Lemma 6.7, Y w is a random variable following a Bernoulli distribution whose parameter is at least 1 4 (1 -3 2 t -1 ). Further, the Y w are mutually independent. We now define a random variable X w for every w ∈ V (T ) \ {u, v} as follows. If Y w = 0, set X w = 0, and otherwise set X w = 1 with probability

Pr[Yw=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,

and by Chernoff's Bound (Proposition 2.6)

For two disjoint sets of vertices X, Y in T ′ , we denote by µ T ′ (X, Y ) the size of a largest directed (X, Y )-matching in T ′ . Claim 6.9.4. Pr(E 3 ) ≤ 2 -k . Proof of claim. Let A, B ⊆ V (T ′ ) be disjoint sets of ⌈(1 + ϵ/4) k 2 ⌉ vertices. We shall prove that with high probability there is a directed (A, B)-matching in T ′ of size at least k 2 . Let M be a maximal directed (A, B)-matching and let Y A (resp. Y B ) the the set of vertices in

by Lemma 6.8 and the Union Bound ≤ 2 (1+ϵ/4)k+2 2 -tϵk/128 ≤ 2 -(2C+1)k as t ≥ 128 ϵ (2C + 2 + ϵ/4) + 16 and ϵk/64 ≥ 1 8 . It follows from the Union Bound (Proposition 2.5) that Pr(E 3 ) ≤ 2 2n 2 -(2C+1)k ≤ 2 -k using the fact that n ≤ Ck. ♢