Let D be an oriented graph. The inversion of a set X of vertices in D consists in reversing the direction of all arcs with both ends in X. The inversion number of D, denoted by inv(D), is the minimum number of inversions needed to make D acyclic. Denoting by ⌧ (D), ⌧ 0(D), and ⌫ (D) the cycle transversal number, the cycle arc-transversal number and the cycle packing number of D respectively, one shows that inv(D) ⌧ 0(D), inv(D) 2⌧ (D) and there exists a function g such that inv(D) g(⌫ (D)). We conjecture that for any two oriented graphs L and R, inv(L ! R) = inv(L) + inv(R) where L ! R is the dijoin of L and R. This would imply that the first two inequalities are tight. We prove this conjecture when inv(L) 1 and inv(R) 2 and when inv(L) = inv(R) = 2 and L and R are strongly connected. We also show that the function g of the third inequality satisfies g(1) 4. We then consider the complexity of deciding whether inv(D) k for a given oriented graph D. We show that it is NP-complete for k = 1, which together with the above conjecture would imply that it is NP-complete for every k. This contrasts with a result of Belkhechine et al. [6] which states that deciding whether inv(T ) k for a given tournament T is polynomial-time solvable.
Notation not given below is consistent with [
Since an inversion preserves the directed cycles of length 2, a digraph can be made acyclic only if it has no directed cycle of length 2, that is if it is an oriented graph. Reciprocally, observe that in an oriented graph, reversing an arc a = uv is the same as inverting Xa = {u, v}. Hence if F is a cycle arc-transversal of D, then Inv(D; (Xa)a2 F ) is acyclic.
A decycling family of an oriented graph D is a family of subsets (Xi)i2 I of subsets of V (D) such that Inv(D; (Xi)i2 I ) is acyclic. 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 digraph, that is, the minimum cardinality of a decycling family. By convention, the empty digraph (no vertices) is acyclic and so has inversion number 0. 1.1 Inversion versus cycle (arc-) transversal and cycle packing One can easily obtain the following upper bounds on the inversion number in terms of the cycle transversal number and the cycle arc-transversal number. See Section 2.
Theorem 1.1. inv(D) ⌧ 0(D) and inv(D) 2⌧ (D) for all oriented graph D.
A natural question is to ask whether these bounds are tight or not.
We denote by C~3 the directed cycle of length 3 and by T Tn the transitive tournament of order n. The vertices of T Tn
are v1, . . . , vn and its arcs {vivj | i < j}. The lexicographic product of a digraph D by a digraph H is the digraph
D[H] with vertex set V (D) ⇥ V (H) and arc set A(D[H]) = {(a, x)(b, y) | ab 2A(D), or a = b and xy 2A(H)}.
It can be seen as blowing up each vertex of D by a copy of H. Using boolean dimension, Belkhechine et al. [
Theorem 1.2 (Belkhechine et al. [
Since ⌧ 0(T Tn[C~3]) = n, this shows that the inequality inv(D) ⌧ 0(D) of Theorem 1.1 is tight. Pouzet asked for an elementary proof of Theorem 1.2. Let L and R be two digraphs. The dijoin from L to R is the digraph, denoted by L ! R, obtained from the disjoint union of L and R by adding all arcs from L to R. Observe that T Tn[C~3] = C~3 ! T Tn 1[C~3]. So a way to elementary prove Theorem 1.2 would be to prove that inv(C~3 ! T ) = inv(T ) + 1 for all tournament T . In fact, we believe that the following more general statement holds. Conjecture 1.3. For any two oriented graphs L and R, inv(L ! R) = inv(L) + inv(R).
As observed in Proposition 2.5, this conjecture is equivalent to its restriction to tournaments. If inv(L) = 0 (resp. inv(R) = 0), then Conjecture 1.3 holds has any decycling family of R (resp. L) is also a decycling family of L ! R. In Section 3, we prove Conjecture 1.3 when inv(L) = 1 and inv(R) 2 {1, 2}. We also prove it when inv(L) = inv(R) = 2 and both L and R are strongly connected.
Let us now consider the inequality inv(D) 2⌧ (D) of Theorem 1.1. One can see that is tight for ⌧ (D) = 1, that is h(1) = 2. Indeed, let Vn be the tournament obtained from a T Tn 1 by adding a vertex x such that N +(vi) = {vi | i is odd} (and so N (vi) = {vi | i is even}. Clearly, ⌧ (Vn) = 1 because Vn x is acyclic, and one can easily check that inv(Vn) 2 for n 5. Observe that V5 is strong, so by the above results, we have inv(V5 ! V5) = 4 while ⌧ (V5 ! V5) = 2, so h(2) = 4. More generally, Conjecture 1.3 would imply that inv(T Tn[V5]) = 2n, while ⌧ (T Tn[V5]) and thus that the inequality (ii) of Theorem 1.1 is tight. Hence we conjecture the following. Conjecture 1.4. h(n) = 2n for all positive integer n. In other words, for every positive integer n, there exists a digraph D such that ⌧ (D) = n and inv(D) = 2n.
A cycle packing in a digraph is a set of vertex disjoint cycles. The cycle packing number of a digraph D, denoted by
⌫ (D), is the maximum size of a cycle packing in D. We have ⌫ (D) ⌧ (D) for every digraph D. On the other hand,
Reed et al. [
Theorem 1.5. There is a (minimum) function g such that inv(D) g(⌫ (D)) for all oriented graph D and g 2f .
A natural question is then to determine this function g or at least obtain good upper bounds on it. Note that the upper
bound on f given by Reed et al. [
Conjecture 1.6. For all k, g(k) = O(k log k): there is an absolute constant C such that inv(D) C · ⌫ (D) log(⌫ (D)) for all oriented graph D.
Note that for planar digraphs, combining results of Reed and Sheperd [
Another natural question is whether or not the inequality g 2f is tight. In Section 4, we show that it is not the case.
We show that g(1) 4, while f (1) = 3 as shown by McCuaig [
Complexity of computing the inversion number We also consider the complexity of computing the inversion number of an oriented graph and the following associated problem. k-INVERSION.
Input: An oriented graph D.
Question: inv(D) k ? k-TOURNAMENT-INVERSION.
Input: A tournament.
Question: inv(T ) k ? We also study the complexity of the restriction of this problem to tournaments.
Note that 0-INVERSION is equivalent to deciding whether an oriented graph D is acyclic. This can be done in O(|V (D)|2) time.
Let k be a positive integer. A tournament T is k-inversion-critical if inv(T ) = k and inv(T x) = k 1 for all x 2V (T ). We denote by ICk the set of k-inversion-critical tournaments. Observe that a tournament T has inversion number at least k if and only if T has a subtournament in ICk.
Theorem 1.8 (Belkhechine et al. [
Checking whether the given tournament T contains I for every element I in ICk+1, one can decide whether inv(T ) in O(|V (T )|mk+1 ) time, where mk+1 be maximum order of an element of ICk+1.
Corollary 1.9. For any non-negative integer k, k-TOURNAMENT-INVERSION is polynomial-time solvable. k The proof of Theorem 1.8 neither explicitly describes ICk nor gives upper bound on mk. So the degree of the polynomial in Corollary 1.9 is unknown. This leaves open the following questions.
Problem 1.10. Explicitely describe ICk or at least find an upper bound on mk.
What is the minimum real number rk such that k-TOURNAMENT-INVERSION can be solved in O(|V (T )|rk ) time ?
As observed in [
v4
B6 v6 v2
A6 v1 v3
R5 v5
v1 v2 v4 Hence m2 = 6, so 1-TOURNAMENT-INVERSION can be solved in O(n6)-time. This is not optimal: we show in Subsection 5.2 that it can be solved in O(n3)-time, and that 2-TOURNAMENT-INVERSION can be solved in O(n6)-time. There is no upper bound on mk so far. Hence since the inversion number of a tournament can be linear in its order (See e.g. tournament Tk described at the end of the introduction), Theorem 1.8 does not imply that one can compute the inversion number of a tournament in polynomial time. In fact, we believe that it is not.
Conjecture 1.11. Given a tournament and an integer k, deciding whether inv(T ) = k is NP-complete. In contrast to Corollary 1.9, we show in Subsection 5.1 that 1-INVERSION is NP-complete. Note that together with Conjecture 1.3, this would imply that k-INVERSION is NP-complete for every positive integer k. Conjecture 1.12. k-INVERSION is NP-complete for all positive integer k.
As we proved Conjecture 1.3. when inv(L) = inv(R) = 1, we get that 2-INVERSION is NP-complete. Because of its relations with ⌧ 0, ⌧ , and ⌫ , (see Subsection 1.1), it is natural to ask about the complexity of computing the inversion number when restricted to oriented graphs (tournaments) for which one of these parameters is bounded. Recall that inv(D) = 0 if and only if D is acyclic, so if and only if ⌧ 0(D) = ⌧ (D) = ⌫ (D) = 0. Problem 1.13. Let k be a positive integer and be a parameter in {⌧ 0, ⌧, ⌫ }. What is the complexity of computing the inversion number of an oriented graph (tournament) D with (D) k ? Conversely, it is also natural to ask about the complexity of computing any of ⌧ 0, ⌧ , and ⌫ , when restricted to oriented graphs with bounded inversion number. In Subsection 5.3, we show that computing any of these parameters is NP-hard even for oriented graphs with inversion number 1. However, the question remains open when we restrict to tournaments.
be a parameter in {⌧ 0, ⌧, ⌫ }. What is the complexity of computing Problem 1.14. Let k be a positive integer and
(T ) for a tournament D with inv(T ) k ? 2
Properties of the inversion number In this section, we establish easy properties of the inversion number and deduce from themTheorem 1.1 and the fact that Conjecture 1.3 is equivalent to its restriction to tournaments.
The inversion number is monotone : Proposition 2.1. If D0 is a subdigraph of an oriented graph D, then inv(D0) inv(D).
Proof. Let D0 be a subdigraph of D. If (Xi)i2 I is a decycling family of D, then (Xi \ V (D0))i2 I is a decycling family of D0.
Lemma 2.2. Let D be a digraph. If D a source (a sink) x, then inv(D) = inv(D x).
Proof. Every decycling family of D digraph results in an acyclic digraph.
x is also a decycling family of D since adding a source (sink) to an acyclic Lemma 2.3. Let D be an oriented graph and let x be a vertex of D. Then inv(D) inv(D x) + 2.
Proof. Let N +[x] be the closed out-neighbourhood of x, that is {x} [ N +(x). Observe that D0 = Inv(D; (N +[x], N +(x))) is the oriented graph obtained from D by reversing the arc between x and its out-neighbours. Hence x is a sink in D0 and D0 x = D x. Thus, by Lemma 2.2, inv(D) inv(D0) + 2 inv(D x) + 2. Proof of Theorem 1.1. As observed in the introduction, if F is a feedback arc-set, then the family of sets of end-vertices of arcs of F is a decycling family. So inv(D) ⌧ 0(D).
Let S = {x1, . . . , xk} be a cycle transversal with k = ⌧ (D). Lemma 2.3 and a direct induction imply inv(D) inv(D { x1, . . . , xi}) + 2i for all i 2[k]. Hence inv(D) inv(D S) + 2k. But, since S is a cycle transversal, D S is acyclic, so inv(D S) = 0. Hence inv(D) 2k = 2⌧ (D).
Let D be an oriented graph. An extension of D is a tournament T such that V (D) = V (T ) and A(D) ✓ A(T ).
Lemma 2.4. Let D be an oriented graph. There is an extension T of D such that inv(T ) = inv(D). Proof. Set p = inv(D) and let (Xi)i2 [p] be a decycling family of D. Then D⇤ = Inv(D; (Xi)i2 [p]) is acyclic and so admits an acyclic ordering (v1, . . . , vn).
Let T be the extension of D constructed as follows: For every 1 i < j p such that vivj 2/A(D⇤ ), let n(i, j) be the number of Xi, i 2[p], such that {vi, vj } ✓ Xi. If n(i, j) is even then the arc vivj is added to A(T ), and if n(i, j) is odd then the arc vj vi is added to A(T ). Note that in the first case, vivj is reversed an even number of times by (Xi)i2 [p], and in the second vj vi is reversed an odd number of times by (Xi)i2 [p]. Thus, in both cases, vivj 2Inv(T ; (Xi)i2 [p]). Consequently, (v1, . . . , vn) is also an acyclic ordering of Inv(T ; (Xi)i2 [p]). Hence inv(T ) inv(D), and so, by Proposition 2.1, inv(T ) = inv(D).
Proposition 2.5. Conjecture 1.3 is equivalent to its restriction to tournaments.
Proof. Suppose there are oriented graphs L, R that form a counterexample to Conjecture 1.3, that is such that inv(L ! R) < inv(L) + inv(R). By Lemma 2.4, there is an extension T of L ! R such that inv(T ) = inv(L ! R) and let TL = T hV (L))i and TR = T hV (R))i. We have T = TL ! TR and by Proposition 2.1, inv(L) inv(TL) and inv(R) inv(TR). Hence inv(T ) < inv(TL) + inv(TR), so TL and TR are two tournaments that form a counterexample to Conjecture 1.3.
Proposition 3.1. inv(L ! R) inv(L) + inv(R).
Proof. First invert inv(L) subsets of V (L) to make L acyclic, and then invert inv(R) subbsets of V (R) to make R acyclic. This makes L ! R acyclic.
Proposition 3.2. If inv(L), inv(R) 1, then inv(L ! R) 2.
Proof. Assume inv(L), inv(R) 1. Then L and R are not acyclic, so let CL and CR be directed cycles in L and R respectively. Assume for a contradiction that there is a set X such that inverting X in L ! R results in a acyclic digraph D0. There must be an arc xy in A(CL) such that x 2X and y 2/X, and there must be z 2X \ V (CR). But then (x, y, z, x) is a directed cycle in D0, a contradiction.
Further than Proposition 3.2, the following result give some property of a minimum decycling family of L ! R when inv(L) = inv(R) = 1.
Theorem 3.3. Let D = (L ! R), where L and R are two oriented graphs with inv(L) = inv(R) = 1. Then, for any decycling family (X1, X2) of D, either X1 ⇢ V (L), X2 ⇢ V (R) or X1 ⇢ V (L), X2 ⇢ V (R). Proof. Let (X1, X2) be a decycling family of D and let D⇤ be the acyclic digraph obtained after inverting X1 and X2 (in symbols D⇤ = Inv(D; (X1, X2))).
Let us define some sets. See Figure 2.
• For i 2[
i j = (XiR \ XjR).
X1L X2L
X1L 2 X1L2 X2L 1 ZL
X1R 2 X1R2 X2R 1 ZR
X1R
X2R Observe that at least one of the sets X1L 2, X2R 1, X2L 1 and X1R 2 must be empty, otherwise D⇤ is not acyclic. By symmetry, we may assume that it is X1R 2 or X2R 1. Observe moreover that X1R 2 [ X2R 1 6= ; for otherwise X1F = X2F = X1R2 and D⇤ hV (F )i = F is not acyclic.
Assume first that X1R 2 = ; and so X2R 1 6= ; .
Suppose for a contradiction that X1R2 6= ; and let a 2X2R 1, b 2X1R2. Let C be a directed cycle in L. Note that V (C) cannot be contained in one of the sets X1L 2, X1L2 or X2L 1. If V (C) \ ZL 6= ; , there is an arc cd 2A(L) such that c 2X1L 2 [ X1L2 [ X2L 1 and d 2ZL. Then, either (c, d, a, c) or (c, d, b, c) is a directed cycle in D⇤ , a contradiction. Thus, V (C) ✓ X1L 2 [ X1L2 [ X2L 1. If V (C) \ X1L2 6= ; , then there is an arc cd 2A(L) such that c 2X1L2 and d 2X1L 2 [ X2L 1 which means that dc 2A(D⇤ ) and (d, c, b, d) is a directed cycle in D⇤ , a contradiction. Hence V (C) ✓ X1L 2 [ X2L 1 and there exists an arc cd 2A(L) such that c 2X2L 1, d 2X1L 2 and (c, d, a, c) is a directed cycle in D⇤ , a contradiction.
Therefore X1R2 = ; and every directed cycle of R has its vertices in X2R 1 [ ZR. Then, there is an arc ea 2A(R) with a 2X2R 1 and e 2ZR. Note that, in this case, ea 2A(D⇤ ) and (e, a, c, e) is a directed cycle in D⇤ for any c 2X1L2 [ X2L 1. Thus, X1L2 = X2L 1 = ; and X1 ⇢ V (L), X2 ⇢ V (R).
If X2R 1 = ; , we can symmetrically apply the same arguments to conclude that X1 ⇢ V (R) and X2 ⇢ V (L). Theorem 3.4. Let L and R be two oriented graphs. If inv(L) = 1 and inv(R) = 2, then inv(L ! R) = 3. Proof. Let D = (L ! R). By Proposition 3.1, we know that inv(D) 3.
Assume for a contradiction that inv(D) 2. Let (X1, X2) be a decycling family of D and let D⇤ = Inv(D; (X1, X2)).
Let L⇤ = D⇤ hV (L)i and R⇤ = D⇤ hV (F )i. We define the sets X1L, X2L, X1R, X2R, ZL, ZR, X1L2, X1R2, X1L 2, X2L 1,
X1R 2, and X2R 1 as in Theorem 3.3. See Figure 2. Note that each of these sets induces an acyclic digraph in D⇤ and
thus also in D. For i 2[
Claim 1: XiL, XiR 6= ; for all i 2[
Proof. Since inv(R) = 2, necessarily, X1R, X2R 6= ; .
Suppose now that XiL = ; . Then Di = L ! Ri. As inv(L) contradiction.
Claim 2: X1L 6= X2L and X1R 6= X2R. 1 and inv(Ri) 1, by Proposition 3.2 inv(Di) 2, a ⌃ Proof. If X1L = X2L, then L⇤ = L, so L⇤ is not acyclic, a contradiction. Similarly, If X1R = X2R, then R⇤ = R, so R⇤ is not acyclic, a contradiction. ⌃ In particular, Claim 2 implies that X1L 2 [ X2L 1 6= ; .
In the following, we denote by A
B the fact that there is no arc from B to A.
Assume first that X1R 2 = ; . By Claim 1, X1R 6= ; , so X1R2 6= ; and by Claim 2 , X1R 6= X2R, so X2R 1 6= ; . If X2L 1 6= ; , then, in D⇤ , X2R 1 [ X1R2 would be acyclic, a contradiction. Thus, X2L 1 = ; .
ZR because X2R 1 [ X1R2 ! X2L 1 ! ZR. But then R1 = Inv(R⇤ ; X2R) Then by Claims 1 and 2, we get X1L2, X1L 2 6= ; . Hence, as X1R2 ! X1L 2 ! X2R 1 ! X1L2 ! X1R2 in D⇤ , there is a directed cycle in D⇤ , a contradiction. Therefore X1R 2 6= ; .
In the same way, one shows that X2R 1 6= ; . As X1R 2 ! X1L 2 ! X2R 1 ! X2L 1 ! X1R 2 in D⇤ , and D⇤ is acyclic, one of X1L 2 and X2L 1 must be empty. Without loss of generality, we may assume X1L 2 = ; .
Then by Claims 1 and 2, we have X1L2, X1L 2 6= ; . Furthermore X1R2 = ; because X1R2 ! X1L2 ! X1R2 in D⇤ . Now in D⇤ , X2R 1 because X1R 2 ! X1L2 ! ZR. Thus, in D, we also have X2R 1 contradiction to Inv(R) = 2.
X1R 2 [ ZR because X2R 1 !
X2L 1 ! X1R 2 [ ZR and X1R 2
X2L 1 ! X1R 2 ! X1R 2 [ ZR, and X1R 2 ZR
ZR. So R is acyclic, a Therefore inv(D)
3. So inv(D) = 3.
Corollary 3.5. inv(D) = 1 if and only if inv(D ! D) = 2.
Theorem 3.6. Let L and R be strong digraphs such that inv (L), inv (R) Due to lack of space, the proof of this theorem is left in appendix.
Corollary 3.7. Let L and R be strong digraphs such that inv (L), inv (R) = 2. Then inv (L ! R) = 4.
A digraph D is intercyclic if ⌫ (D) = 1. The aim of this subsection is to prove the following theorem. Theorem 4.1. If D is an intercyclic oriented graph, then inv(D) 4.
In order to prove this theorem, we need some preliminaries.
Let D be an oriented graph. An arc uv is weak in D if min{d+(u), d (v)} = 1. An arc is contractable in D if it is weak and in no directed 3-cycle. If a is a contractable arc, then let D/a is the digraph obtained by contracting the arc a and D˜ /a be the oriented graph obtained from D by removing one arc from every pair of parallel arcs created in D/a. Lemma 4.2. Let D be a strong oriented graph and let a be a contractable arc in D. Then D/a is a strong intercyclic oriented graph and inv(D˜ /a) inv(D).
inv(D˜ /a) = inv(D/a).
Set a = uv, and let w be the vertex corresponding to both u and v in D/a. Let (X10, . . . , Xp0) be a decycling family of D0 = D˜ /a that result in an acyclic oriented graph R0. For i 2[p], let Xi = Xi0 if w 2/Xi0 and Xi = (Xi0 \{w})[{ u, v} if w 2X0. Let a⇤ = uv if w is in an even number of Xi0 and a⇤ = vu otherwise, and let R = Inv(D; (X1, . . . , Xp)).
i One easily shows that R = R0/a⇤ . Therefore R is acyclic since the contraction of an arc transforms a directed cycle into a directed cycle.
Lemma 4.3. Let D be an intercyclic oriented graph. If there is a non-contractable weak arc, then inv(D) 4. Proof. Let uv be a non-contractable weak arc. By directional duality, we may assume that d (v) = 1. Since uv is non-contractable, uv is in a directed 3-cycle (u, v, w, u). Since D is intercyclic, we have D \ {u, v, w} is acyclic. Consequently, {w, u} is a cycle transversal of D, because every directed cycle containing v also contains u. Hence, by Theorem 1.1, inv(D) ⌧ (D) 4.
The description below follows [
Intercyclic digraphs in reduced form were characterized by Mc Cuaig [
y1 y4 y1 y4 y1 y4 y2 y6 y (a) y3 y5 y2 y6 y (b) y3 y5 y2 y6 y (c) y3 y5
Let K be the class of digraphs D with ⌧ (D) 3 and 0(D) 2 which can be obtained from a digraph KH from
P(w0, z0; z1, w1) by adding at most one arc connecting w0, z0, adding at most one arc connecting w1, z1, adding a
directed 4-cycle (x0, x1, x2, x3, x0) disjoint from KH and adding eight single arcs w1x0, w1x2, z1x1, z1x3, x0w0,
x2w0, x1z0 ,x3z0 (see Figure 4). Let H be the class of digraphs D with ⌧ (D) 3 and 0(D) 2 such that D is the
union of three arc-disjoint digraphs H↵ 2 P(y4, y3, y1; y5, y2), H 2 P(y4, y5; y3, y1, y2), and H 2 P(y1, y2; y3, y4),
where y1, y2, y3, y4, y5 are the only vertices in D occuring in more than one of H↵ , H , H (see Figure 5).
Theorem 4.4 (McCuaig [
Using this characterization we can now prove the following.
Corollary 4.5. If D is an intercyclic oriented graph in reduced form, then inv(D) 4.
Proof. Let D be an intercyclic oriented graph in reduced form. By Theorem 4.4, it is in T [ { D7} [ K [ H
If D 2 T, then it is obtained from a digraph D0 in P(x+, y+; x , y ) by identifying x+ = x and y+ = y . Thus D { x+, y+} = D0 { x+, y+, x , y } is acyclic. Hence ⌧ (D) 2, and so by Theorem 1.1, inv(D) 4. If D = D7, then inverting X1 = {y, y2, y4, y6} so that y becomes a source and then inverting {y2, y3, y5, y6}, we obtain an acylic digraph with acyclic ordering (y, y6, y3, y4, y5, y, y2). Hence inv(D7) 2.
If D 2 K, then inverting {x0, x3} and {x0, x1, x2, x3, w1, z1}, we convert D to an acyclic digraph with acyclic ordering (x3, x2, x1, x0, v1, . . . , vp) where (v1, . . . , vp) is an acyclic ordering of KH .
If D 2 H, then consider D0 = Inv(D, V (H ). The oriented graph D is the union of H↵ 2 P(y4, y3, y1; y5, y2), H 2 P(y4, y5; y3, y1, y2), and H , the converse of H . As H Set Y = {y1, y2, y3, y4, y5}. 2 P(y1, y2; y3, y4), we have H 2 P(y4, y3; y2, y1).
We claim that every directed cycle C0 of D0 contains y5. Since D0 Y is acyclic, C0 is the concatenation of directed paths P1, P2, . . . , Pq with both end-vertices in Y and no internal vertex in Y . Now let C be the directed cycle obtained from C by replacing each Pi by an arc from its initial vertex to its terminal vertex. Clearly, C contains y5 if and only if C0 does. But C is a directed cycle in J the digraph with vertex set Y in which {y4, y3, y1} ! { y5, y2}, {y4, y5} ! { y3, y1, y2}, and {y4, y3} ! { y1, y2}. One easily checks that J v5 is acyclic with acyclic ordering (y4, y3, y1, y2), so C contains y5 and so does C0.
Consequently, {y5} is a cycle transversal of D0. Hence, by Theorem 1.1 (ii), we have inv(D0) 2⌧ (D0) 2. As D0 is obtained from D by inverting one set, we get inv(D) 3.
We can now prove Theorem 4.1.
Proof. By induction on the number of vertices of D.
If D is not strong, then it has a unique non-trivial strong component C and any decycling family of C is a decycling family of D, so inv(C) = inv(D). By the induction hypothesis, inv(C) 4, so inv(D) 4. Henceforth, we may assume that D is strong.
Assume now that D has a weak arc a. If a is non-contractable, then inv(D) 9 by Lemma 4.3. If a is contractable,
then consider D˜ /a. As observed by McCuaig [
Thus D is in a reduced form and by Corollary 4.5, inv(D) 4. Theorem 5.1. 1-INVERSION is NP-complete even when restricted to strong digraphs.
In order to prove this theorem, we need some preliminaries.
Let J be the digraph depicted in Figure 6.
d
e a b
c Lemma 5.2. The only sets whose inversion can make J acyclic are {a, b, e} and {b, c, d}.
Proof. Assume that an inversion on X makes D acyclic. Then X must contain exactly two vertices of each of the directed 3-cycles (a, b, c, a), (a, b, d, a), and (e, b, c, e), and cannot be {a, c, d, e} for otherwise (e, b, d, e) is a directed cycle in the resulting digraph. Hence X must be either {a, b, e} or {b, c, d}. One can easily check that an inversion on any of these two sets makes D acyclic.
Proof of Theorem 5.1. Reduction from MONOTONE 1-IN-3 SAT which is well-known to be NP-complete. Let be a monotone 3-SAT formula with variables x1, . . . , xn and clauses C1, . . . , Cm. Let D be the digraph constructed as follows. For every i 2[n], let us construct a variable digraph Ki as follows: for every j 2[m], create a copy Jij of J , and then identify all the vertices cij into one vertex ci. Then, for every clause Cj = xi1 _ xi2 _ xi3 , we add the arcs of the directed 3-cycle Dj = (aij1 , ai2 , aij3 ).
j Observe that D is strong. We shall prove that inv(D) = 1 if and only if admits a 1-in-3-SAT assignment. '(xi) = true if X \ V (Ki) = Sm j=1{aij , bij , eij }.
j=1{bij , ci, dij }, and '(xi) = f alse if X \ V (Ki) = Sm Assume first that inv(D) = 1. Let X be a set whose inversion makes D acyclic. By Lemma 5.2, for every i 2[n], either X \ V (Ki) = Sm j j=1{bij , ci, dij }. Let ' be the truth assignment defined by j=1{ai , bij , eij } or X \ V (Ki) = Sm Consider a clause Cj = xi1 _ xi2 _ xi3 . Because Dj is a directed 3-cycle, X contains exactly two vertices in V (Dj ).
of ', we have '(x`1 ) = '(x`2 ) = f alse and '(x`3 ) = true. Therefore, ' is a 1-in-3 SAT assignment. and Xi = Sm i=1 Xi.
j=1{aij , bij , eij } if '(xi) = f alse, and set X = Sn Assume now that admits a 1-in-3 SAT assignment '. For every i 2[n], let Xi = Sm j=1{bij , ci, dij } if '(xi) = true Let D0 be the graph obtained from D by the inversion on X. We shall prove that D is acyclic, which implies inv(D) = 1.
Assume for a contradiction that D0 contains a cycle C. By Lemma 5.2, there is no cycle in any variable gadget Ki, so C must contain an arc with both ends in V (Dj ) for some j. Let Cj = xi1 _ xi2 _ xi3 . Now since ' is a 1-in-3-SAT namely bij3 , which is a sink. This is a contradiction.
Corollary 5.3. 2-INVERSION is NP-complete. assignment, w.l.o.g., we may assume that '(xi1 ) = '(xi2 ) = f alse and '(xi3 ) = true. Hence in D0, aij2 ! aij1 , aij2 ! aij3 and aij3 ! aij1 . Moreover, in D0hV (Jij1 )i, aij1 is a sink, so aij1 is a sink in D0. Therefore C does not goes through aij1 , and thus C contains the arc aij2 aij3 , and then enter Ji3 . But in D0hV (Jij3 )i, aij3 has a unique out-neighbour, j Proof. By Corollary 3.5, we have inv(D ! D) = 2 if and only inv(D) = 1, so the statement follows from Theorem 5.1. 5.2 Solving k-TOURNAMENT-INVERSION for k 2 {1, 2} Theorem 5.4. 1-TOURNAMENT-INVERSION can be solved in O(n3) time.
Proof. Let T be a tournament. For every vertex v one can check whether there is an inversion that transforms T into a transitive tournament with source v. Indeed the unique possibility inversion is the one on the closed in-neighbourhood of v, N [v] = N (v) [ { v}. So one can make inversion on N [v] and check whether the resulting tournament is transitive. This can obviously be done in O(n2) time Doing this for every vertex v yields an algorithm which solves 1-TOURNAMENT-INVERSION in O(n3) time. Theorem 5.5. 2-TOURNAMENT-INVERSION can be solved in in O(n6) time.
The main idea to prove this theorem is to consider every pair (s, t) of vertices and to check whether there are two sets X1, X2 such that the inversion of X1 and X2 results in a transitive tournament with source s and sink t. We need some definitions and lemmas.
The symmetric difference of two sets A ad B is A4B = (A \ B) [ (B \ A).
Let T be a tournament and let s and t be two vertices of T . We define the following four sets
A(s, t) = B(s, t) = C(s, t) = D(s, t) =
N +(s) \ N (t) N (s) \ N +(t) N +(s) \ N +(t)
N (s) \ N (t) Lemma 5.6. Let T be a tournament and let s and t be two vertices of T . Assume there are two sets X1, X2 such that the inversion of X1 and X2 results in a transitive tournament with source s and sink t.
(1) If {s, t} ✓
X1 \ X2, then ts 2A(T ), C(s, t) = D(s, t) = ; and X1 = {s, t} [ B(s, t). (2) If s 2X1 \ X2, t 2X2 \ X1, and the inversion of X1 and X2 makes T acyclic, then st 2A(T ), A(s, t) \ (X1 [ X2) = ; , X1 = {s} [ B(s, t) [ D(s, t), and X2 = {t} [ B(s, t) [ C(s, t). (3) If s 2X1 \ X2 and t 2X1 \ X2, then ts 2A(T ), X1 = {s, t} [ B(s, t) [ C(s, t), and X2 = {s} [ C(s, t) [
D(s, t). (4) If {s, t} ✓ X1 \ X2, then st 2 A(T ), C(s, t) = ; , D(s, t) = ; , X1 \ X2 ✓
B(s, t) = X14X2.
A(s, t) [ { s, t}, and Proof. (1) The arc between s and t is reversed once, so ts 2A(T ).
Assume for a contradiction, that there is a vertex c 2C(S, t). The arc tc must be reversed, so c 2X1, but then the arc sc is reversed contradicting the fact that s becomes a source. Hence C(s, t) = ; . Similarly D(s, t) = ; . The arcs from t to B(s, t) and from B(s, t) to s are reversed so B(s, t) ✓ X1. The arcs from s to A(s, t) and from A(s, t) to t are not reversed so A(s, t) \ X1 = ; . Therefore X1 = {s, t} [ B(s, t). (2) The arc between s and t is not reversed, so st 2A(T ). The arcs from s to A(s, t) and from A(s, t) to t are not reversed so A(s, t) \ X1 = ; and A(s, t) \ X2 = ; . The arcs from t to B(s, t) and from B(s, t) to s are reversed so B(s, t) ✓ X1 and B(s, t) ✓ X2. The arcs from s to C(s, t) are not reversed so C(s, t) \ X1 = ; and the arcs from t to C(s, t) are reversed so C(s, t) ✓ X2. The arcs from D(s, t) to s are reversed so D(s, t) ✓ X1 and the arcs from D(s, t) to d are not reversed so D(s, t) \ X2 = ; . Consequently, X1 = {s} [ B(s, t) [ D(s, t), and X2 = {t} [ B(s, t) [ C(s, t). (3) The arc between s and t is reversed, so ts 2A(T ). The arcs from A(s, t) to t are not reversed so A(s, t) \ X1 = ; . The arcs from s to A(s, t) are not reversed so A(s, t) \ X2 = ; . The arcs from t to B(s, t) are reversed so B(s, t) ✓ X1. The arcs from B(s, t) to s are reversed (only once) so B(s, t) \ X2 = ; . The arcs from t to C(s, t) are reversed so C(s, t) ✓ X1. The arcs from s to C(s, t) must the be reversed twice so C(s, t) ✓ X2. The arcs from D(s, t) to t are not reversed so D(s, t) \ X1 = ; . The arcs from D(s, t) to s are reversed so D(s, t) ✓ X2. Consequently, X1 = {s, t} [ B(s, t) [ C(s, t), and X2 = {s, t} [ C(s) [ D(s, t). (4) The arc between s and t is reversed twice, so st 2A(T ).
Assume for a contradiction, that there is a vertex c 2C(s, t). The arc tc must be reversed, so c is in exactly one of X1 ad X2. But then the arc sc is reversed contradicting the fact that s becomes a source. Hence C(s, t) = ; . Similarly D(s, t) = ; . The arcs from s to A(s, t) and from A(s, t) to t are not reversed so every vertex of A(s, t) is either in X1 \ X2 or in V (T ) \ (X1 [ X2). The arcs from t to B(s, t) and from B(s, t) to s are reversed so every vertex of B(s, t) is either in X1 \ X2 or in X2 \ X1. Consequently, X1 \ X2 ✓ A(s, t) [ { s, t}, and B(s, t) = X14X2. Lemma 5.7. Let T be a tournament of order n and let s and t be two vertices of T .
(1) One can decide in O(n3) time whether there are two sets X1, X2 such that the inversion of X1 and X2 results in a transitive tournament with source s and sink t and {s, t} ✓ X1 \ X2. (2) One can decide in O(n2) time whether there are two sets X1, X2 such that the inversion of X1 and X2 results in a transitive tournament with source s and sink t and s 2X1 \ X2 and t 2X2 \ X1. (3) One can decide in O(n2) time whether there are two sets X1, X2 such that the inversion of X1 and X2 results in a transitive tournament with source s and sink t and s 2X1 \ X2 and t 2X1 \ X2. (4) One can decide in O(n4) time whether there are two sets X1, X2 such that the inversion of X1 and X2 results in a transitive tournament with source s and sink t and {s, t} ✓ X1 \ X2.
Proof. For all cases, we first compute A(s, t), B(s, t), C(s, t), and D(s, t), which can obviously be done in O(n2). (1) By Lemma 5.6, we must have ts 2A(T ) and C(s, t) = D(s, t) = ; . So we first check if this holds. Furthermore, by Lemma 5.6, we must have X1 = {s, t} [ B(s, t). Therefore we invert {s, t} [ B(s, t) which results in a tournament T 0. Observe that s is a source of T 0 and t is a sink of T 0. Hence, we return ‘Yes’ if and only if inv(T 0 { s, t}) = 1 which can be tested in O(n3) by Theorem 5.4. (2) By Lemma 5.6, we must have st 2A(T ). So we first check if this holds. Furthermore, by Lemma 5.6, the only possibility is that X1 = {s} [ B(s, t) [ D(s, t), and X2 = {t} [ B(s, t) [ C(s, t). So we invert those two sets and check whether the resulting tournament is a transitive tournament with source s and sink t. This can done in O(n2). (3) By Lemma 5.6, we must have ts 2A(T ). So we first check if this holds. Furthermore, by Lemma 5.6, the only possibility is that X1 = {s, t} [ B(s, t) [ C(s, t), and X2 = {s} [ C(s, t) [ D(s, t). So we invert those two sets and check whether the resulting tournament is a transitive tournament with source s and sink t. This can done in O(n2). (4) By Lemma 5.6, we must have st 2A(T ), C(s, t) = ; , D(s, t) = ; . So we first check if this holds. Furthermore, by Lemma 5.6, the desired sets X1 and X2 must satisfy X1 \ X2 ✓ A(s, t) [ { s, t}, and B(s, t) = X14X2. In particular, every arc of TA = T hA(s, t)i is either not reversed or reversed twice (which is the same). Hence TA must be a transitive tournament. So we check whether TA is a transitive tournament and if yes, we find a directed hamiltonian path PA = (a1, . . . , ap) of it. This can be done in O(n2).
Now we check that B(s, t) admits a partition (X10, X20) with Xi0 = Xi \ B and the inversion of both X10 and X20 transforms T hB(s, t)i into a transitive tournament TB with source s0 and sink t0. The idea is to investigate all possibilities for s0, t0 and the sets X10 and X20. Since (X10, X20) is a partition of B(s, t) and (X10, X20) is a decycling family if and only if (X20, X10) is a decycling family, we may assume that (a) {s0, t0} ✓
X10 \ X20, or
For the possibilties corresponding to Case (a), we proceed as in (1) above. For every arc t0s0 2A(T hB(s, t)i), we check that C(s0, t0) = D(s0, t0) = ; (where those sets are computed in T hB(s, t)i). Furthermore, by Lemma 5.6, we must have X10 = {s, t} [ B(s0, t0) and X20 = B(s, t) \ X10. So we invert those two sets and check whether the resulting tournament TB is transitive. This can be done in O(n2) (or each arc t0s0.
For a possibilities corresponding to Case (b), we proceed as in (2) above. For every arc t0s0 2A(T hB(s, t)i), by
Lemma 5.6, the only possibility is that X10 = {s0} [ B(s0, t0) [ D(s0, t0), and X2 = {t0} [ B(s0, t0) [ C(s0, t0). As
those two sets form a partition of B(s, t), we also must have B(s0, t0) = ; and A(s0, t0) = ; . So we invert those two
sets and check whether the resulting tournament TB is transitive. This can be done in O(n2) for each arc t0s0.
In both cases, we are left with a transitive tournament TB. We compute its directed hamiltonian path PB = (b1, . . . , bq)
which can be done in O(n2). We need to check whether this partial solution on B(s, t) is compatible with the rest of
the tournament, that is {s, t} [ A(s, t). It is obvious that it will always be compatible with s and t as they become
source and sink. So we have to check that we can merge TA and TB into a transitive tournament on A(s, t) and
B(s, t) after the reversals of X1 and X2. In other words, we must interlace the vertices of PA and PB. Recall that
Z = X1 \ X2 \ {s, t} ✓ A(s, t) and Xi = Xi0 [ Z [ { s, t}, i 2[
ai for j > ji (in which case ai 2/Z and the arcs between ai and B(s, t) • or bj ai for j ji and bj ! ai for j > ji (in which case ai 2Z and the arcs between ai and B(s, t) are reversed).
See Figure 7 for an illustration of a case when we can merge the two orderings after reversing X1 and X2. a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 Deciding whether there are such indices can be done in O(n2) for each possibility.
As we have O(n2) possibilities, and for each possibility the procedure runs in O(n2) time. Hence the overall procedure runs in O(n4) time.
Proof of Theorem 5.5. By Lemma 2.2, by removing iterately the sources and sinks of the tournament, it suffices to solve the problem for a tournament with no sink and no source.
Now for each pair (s, t) of distinct vertices, one shall check whether there are two sets X1, X2 such that the inversion of X1 and X2 results in a transitive tournament with source s and sink t. Observe that since s and t are neither sources nor sinks in T , each of them must belong to at least one of X1, X2. Therefore, without loss of generality, we are in one of the following possibilities: • {s, t} ✓
X1 \ X2. Such a possibility can be check in O(n3) by Lemma 5.7 (1). • s 2X1 \ X2 and t 2X2 \ X1. Such a possibility can be check in O(n2) by Lemma 5.7 (2). • s 2X1 \ X2 and t 2X1 \ X2. Such a possibility can be check in O(n2) by Lemma 5.7 (3). • t 2X1 \ X2 and s 2X1 \ X2. Such a possibility is the directional dual of the preceding one. It can be tested in O(n2) by reversing all arcs and applying Lemma 5.7 (3). • {s, t} ✓
X1 \ X2. Such a possibility can be check in O(n4) by Lemma 5.7 (4).
Since there are O(n2) pairs (s, t) and for each pair the procedure runs in O(n4), the algorithm runs in O(n6) time.
Computing related parameters when the inversion number is bounded The aim of this subsection is to prove the following theorem.
Theorem 5.8. Let be a parameter in ⌧, ⌧ 0, ⌫ . Given an oriented graph D with inversion number 1 and an integer k, it is NP-complete to decide whether (D) k.
Let D be a digraph. The second subdivision of D is the oriented graph S2(D) obtained from D by replacing every arc a = uv by a directed path Pa = (u, xa, ya, u) where xa, ya are two new vertices.
Proposition 5.9. Let D be a digraph.
(i) inv(S2(D) 1.
(ii) ⌧ 0(S2(D)) = ⌧ 0(D), ⌧ (S2(D)) = ⌧ (D), and ⌫ (S2(D)) = ⌫ (D).
and the other vertices form a stable set. Thus inv(S2(D)) = 1. (ii) There is a one-to-one correspondence between directed cycles in D and directed cycles in S2(D) (their second subdivision). Hence ⌫ (S2(D)) = ⌫ (D).
Moreover every cycle transversal S of D is also a cycle transversal of S2(D). So ⌧ (S2(D)) ⌧ (D). Now consider a cycle transversal T . If xa or ya is in S for some a 2A(D), then we can replace it by any end-vertex of a. Therefore, we may assume that T ✓ V (D), and so T is a cycle transversal of D. Hence ⌧ (S2(D)) = ⌧ (D). Similarly, consider a cycle arc-transversal F of D. Then F 0 = {a | xaya 2F } is a cycle arc-transversal of S2(D). Conversely, consider a cycle arc-transversal F 0 of S2(D). Replacing each arc incident to xa, ya by xaya for each a 2 A(D), we obtain another cycle arc-transversal. So we may assume that F 0 ✓ { xaya | a 2 A(D)}. Then F = {a | xaya 2F 0} is a cycle arc-transversal of D. Thus ⌧ 0(S2(D)) = ⌧ 0(D).
Proof of Theorem 5.8. Since computing each of ⌧ , ⌧ 0, ⌫ is NP-hard, Proposition 5.9 (ii) implies that computing each of ⌧ , ⌧ 0, ⌫ is also NP-hard for second subdivisions of digraphs. As those oriented graphs have inversion number 1 (Proposition 5.9 (i)), computing each of ⌧ , ⌧ 0, ⌫ is NP-hard for oriented graphs with inversion number 1.
The authors would like to thank Maurice Pouzet for suggesting the problem. There are very pleased to honour him on his 75th birthday.
This research was supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B, and by the french Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01. This work was done while the Joergen Bang-Jensen was visiting team Coati, I3S and INRIA Sophia Antipolis. Hospitality and financial support is gratefully acknowledged. Ce travail a bénéficié d’une aide du gouvernement français, gérée par l’Agence Nationale de la Recherche au titre du projet Investissements d’Avenir UCAJEDI portant la référence no ANR-15-IDEX-01. This work was done while the Jonas Costa Ferreira da Silva was spending his second year of PhD as “sandwich” in team Coati, I3S and INRIA Sophia Antipolis.
Appendix: Dijoin of oriented graphs with inversion number 2 In this appendix, we give the proof of the following Theorem 3.6 Theorem 3.6. Let L and R be strong digraphs such that inv (L), inv (R)
Proof. Assume for a contradiction that there are two digraphs L and R such that inv (L), inv (R) R) = 3. By Lemma 2.4 and Proposition 2.1, we can assume that L and R are tournaments. By Theoren b3.4, inv (L ! R) 3. Assume for a contradiction that inv (L ! R) = 3. Let (X1, X2, X3) be a decycling sequence of D = L ! R and denote the resulting acylic (transitive) tournament by T . We will use the following notation. Below and in the whole proof, whenever we use subscripts i, j, k together we have {i, j, k} = {1, 2, 3}.
• XiL = Xi \ V (L), XiR = Xi \ V (R) for all i 2[
• XiL jk = XiL \ (XjL [ XkL) and XiR jk = XiR \ (XjR [ XkR).
For any two (possibly empty) sets Q, W , we write Q ! W to indicate that every q 2Q has an arc to every w 2W . Unless otherwise specified, we are always referring to the arcs of T below. When we refer to arcs of the original digraph we will use the notation u ) v, whereas we use u ! v for arcs in T .
Claim A: XiL, XiR 6= ; for all i 2[
Proof. Suppose w.l.o.g. that X1R = ; and let D0 = Inv(D; X1). Then D0 contains C3 ! R as an induced subdigraph since reversing X1L does not make L acyclic so there is still a directed 3-cycle (by Moon’s theorem). ⌃ Claim B: In T the following holds, implying that at least one of the involved sets is empty (as T is acyclic). (a) X1R23 ! X1L23 ! XiRj k ! XiLk j ! X1R23.
(b) XiLj k ! XiRj k ! XiLk j ! XiRk j ! XiLj k.
Proof. This follows from the fact that and arc of D is inverted if and only if it belongs to an odd number of the sets X1, X2, X3. ⌃ Claim C: For all i 6= j, we have XiL 6= XjL and XiR 6= XjR.
Proof. Suppose this is not true, then without loss of generality X3L = X2L but this contradicts that (X1L, X2L, X3L) is a decycling sequence of L as inverting X2L and X3L leaves every arc unchanged and we have inv(L) = 2. ⌃ Now we are ready to obtain a contradiction to the assumption that (X1, X2, X3) is a decycling sequence for D = L ! R. We divide the proof into five cases. In order to increase readability, we will emphasize partial conclusions in blue, assumptions in orange, and indicate consequences of assumptions in red.
Case 1: XL i jk for all i, j, k.
i jk = ; = XR By Claim C, at least two of the sets X1L2 3, X1L3 2, X2L3 1 are non-empty and at least two of the sets X1R2 3, X1R3 2, X2R3 1 are non-empty. Without loss of generality, X1L2 3, X1L3 2 6= ; . Now, by Claim B (b), implies that one of X1R2 3, X1R3 2 must be empty. By interchanging the names of X2, X3 if necessary, we may assume that X1R3 2 = ; and hence, by Claim C, X1R2 3, X2R3 1 6= ; . By Claim B (a), this implies X2L3 1 = ; . Now X2R3 1 ! X1L2 3 ! X1R2 3, so X2R3 1 ! X1R3 2. As X1L2 3 ! X1R2 3 ! X1L3 2, we must have X1L2 3 ! X1L3 2. By Claim B (a), X1L23 ! X1R2 3 ! X1L3 2 ! X1R23 ! X1L23, so one of X1L23 and X1R23 is empty. W.l.o.g. we may assume X1R23 = ; . As R is strong and X2R3 1 dominates X1R2 3 in R (these arcs are reversed by X2), we must have ZR 6= ; . Moreover the arcs incident to ZR are not reversed, so the set ZR has an out-neighbour in X1R2 3 [ X2R3 1. But X1R2 3 [ X2R3 1 ! X1L3 2 ! ZR so T has a directed 3-cycle, contradiction. This completes the proof of Case 1. Case 2: Exactly one of X1L 23, X2L 13, X3L 12, X1R 23, X2R 13, X3R 12 is non-empty.
By reversing all arcs and switching the names of L and R if necessary, we may assume w.l.o.g that X1L 23 6= ; . As X2R 6= X3R we have X1R2 3 [ X1R3 2 6= ; . By symmetry, we can assume that X1R2 3 6= ; .
Suppose for a contradiction that X2R3 1 = ; . Then Claims A and C imply X1R3 2 6= ; . Now, by Claim B (b), one of X1L2 3, X1L3 2 is empty. By symmetry, we can assume X1L3 2 = ; . Now, by Claim C, X2L 6= X3L, so X1L2 3 6= ; . Note that X1L2 3 ! X1R2 3 ! X1L 23, thus X1L2 3 ! X1L 23 because T is acyclic. We also have X1L23 ! X1L2 3 as X1L23 ! X1R3 2 ! X1L2 3, and X1L2 3 ! X2L3 1 as X1L2 3 ! X1R2 3 ! X2L3 1. This implies that in L all arcs between X1L2 3 and X2L3 1 [ X1L23 [ X1L 23 are entering X1L2 3 (the arcs between X1L23 and X1L2 3 were reversed twice and those between X1L 23 [ X2L3 1 and X1L2 3 were reversed once). Hence, as L is strong, we must have an arc uz from X1L2 3 to ZL. But ZL ! X1R3 2 ! X1L2 3 so together with uz we have a directed 3-cycle in T , contradiction. Hence X2R3 1 6= ; .
Observe that X1R2 3 [
If X1L2 3 6= ; , then X2R3 1 ! X1L2 3 ! X1R2 3 ! X2R3 1, a contradiction. So X1L2 3 = ; . But X2L 6= X3L by Claim C. Thus X1L3 2 6= ; . As X2R3 1 ! X1L3 2 ! X1R23, we have X2R3 1 ! X1R23. This implies that in R all the arcs between X2R3 1 and X1R3 2 [ X1R23 [ X1R2 3 are leaving X2R3 1. So as R is strong there must be an arc in R from ZR to X2R3 1. This arc is not reversed (in fact reversed twice), so it is also an arc in T . But since X2R3 1 ! X1L3 2 ! ZR, this arc is in a directed 3-cycle, a contradiction. This completes Case 2.
Case 3: Exactly one of X1L 23, X2L 13, X3L 12 is non-empty and exactly one of X1R 23, X2R 13, X3R 12 is non-empty. By symmetry we can assume X1L 23 6= ; .
Subcase 3.1: X1R 23 6= ; .
By Claim C, X2L 6= X3L, so one of X1L2 3 and X1L3 2 is non-empty. By symmetry we may assume X1L2 3 6= ; . Suppose X1R2 3 6= ; . Then X2R3 1 = ; as X1L 23 ! X1R 23 ! X1L2 3 ! X1R2 3 ! X2L3 1 ! X1R 23.
X2R3 1 !
X1L2 3 !
X1R2 3 !
X1L 23, and X2L3 1 = ; as By Claim B (b), one of X1L3 2, X1R3 2 is empty. By symmetry, we may assume X1R3 2 = ; .
Observe that V (R) \ ZR = X1R23 [ X1R2 3 [ X1R 23, so V (R) \ ZR ! X1L 23 ! ZR, so V (R) \ ZR ! ZR. But all the arcs incident to ZR are not inversed, so in R, there is no arc from ZR to V (R) \ ZR. Since R is strong, ZR = ; . NowX1R 23 ! X1R2 3 [ X1R23 because X1R 23 ! X1L2 3 ! X1R2 3 [ X1R23. But all the arcs between X1R 23 and X1R2 3 [ X1R23 = V (R) \ X1R 23 are inversed from R to T . Hence in R, no arcs leaves X1R 23 in R, a contradiction to R being strong.
Hence X1R2 3 = ; . As X2R 6= X3R this implies X1R3 2 6= ; .
Suppose that X2R3 1 = ; , then X1R23 6= ; because X2R 6= ; by Claim A. Furthermore X1R3 2 ! X1R23 as X1R3 2 !
X1L 23 as X1L2 3 ! X1R23 ! X1L 23. This implies that X1L23 = ; as X1L23 ! X1L2 3 ! X1R23, and X1L2 3 ! X1R3 2 ! X1R23 ! X1L23.
Since L is strong, there must be an arc uv leaving X1L2 3 in L. But v cannot be in X1L 23 since all vertices of this set dominate X1L2 3 in L. Moreover v cannot be in ZL for otherwise (u, v, w, u) would be a directed 3-cycle in T for any w 2X1R 23 since ZL ! X1R 23 ! X1L2 3. Hence v 2X1L3 2 [ X2L3 1, so X1L3 2 [ X2L3 1 6= ; . As X1L3 2 !
X1L3 2, precisely one of X1L3 2, X2L3 1 is non-empty.
IadfL+cXo(Xn1Lt31rLa32di26=c)ti>;ona.0nHdtheXenrc2eL3eeXx1is1L=t3s ;z2, 2=th eZ;nLaXnsdu1L3cXh22Lt3h!at1 tX6=he1Rr;3e. i2Tsh!aennXaXrc1L2Lu32z31f[r!oXmX1LX21L1L33aism2Xpto2lLi3eZs1Lt h,!abtuXXtt11hLR3en223z!!! XXX11LL1R. 2233[ !Xu1L2!3.zAiss Note that ZL = ; as every vertex in V (L) \ ZL has an in-neighbour in V (R) in T , implying that there can be no arc fsruobmdigVra(Lph) o\fZLLatnodZwLe hinavLe. XT1Lhu2s3V)(LX) 1L=2 X3)1L 2X32[L3 X11L)2 3X[ 1 X22L33in1Lw. hBeuret neoawchinovfetrhteinsge tsheetssientdXuc1Les23a n[ aXcy2L3clic1 makes L acyclic, a contradiction to inv(L) = 2. Thus X2R3 1 6= ; .
Suppose X2L3 1 = ; . As above ZL = ; , so V (L) = X1L. As X1L 23 ! X2R3 1 ! X1L2 3 [ X1L3 2 we have TXXXh111LLRu2s22333ZR!!!=XXX; 11RR1L322a3n,2d3waV[se(XXhRa11RL)v3e=232X.X!1R2T1R3hX2u=3s1L,2[; 3u.Xs!iMn1R3goXrd2e1RL+o3[v(XeX2r.12LRXN321oR31w)w!V>he(XRr0e,2R)3ew\aec1ZhgbRoeeftc=atXhuXe1sLs2e1e3RXs6=2e1R3ts[ ; !i.nXdAX1uR3sc1LeXs221aR[32n3!Xa!c2Ry3XclX21Ri3c1!Ld213i.gXr!Wa1Lp2ehXa3il2nRs3!oR1hZaan!vRde. X1R 23 ) X2R3 1 ) X1R3 2 ) X1R 23 in D. But then inverting X1R 23 [ X2R3 1 we make R acyclic, a contradiction to inv(R) = 2. Thus X2L3 1 6= ; . wTXhe1Rehr2ea3fvoe!reXXX1L11LL323232!!= XX;1L2Ra23s 31X;w1LA3esh2Xav!2Le3 XX11R1R!3232X!!1RX2X23R32L!31;1aXs!1LX21RX33[2R23 X!11L2X!23L3Xw11eL3!ha2v.XeA1RXs22L3X3[ 1L1X2!32R3!X11LwXe22R33h a[v1eX!X1L21R3X31;L22A!3s X1R 23 [ X2R3 1.
As every vertex in V (R) \ ZR has an out-neighbour in V (L), we derive as above ZR = ; . Similarly, as every vertex in V (L) \ ZL has in-neighbour in V (R), we get ZL = ; . Next observe that at least one of the sets X1R23, X1L23 must be eeamcphtyofatsheXse1R2s3et!sinXdu1Lc2e3s!an Xac2Ry3cli1c !subXto1Lu2rna3m!enXto1Rf2R3. aIfndXX1R21R3 =23 ; )thXen2R3V (1R)) =X1RX3 1R2 2a3n[d XX1R1R3232 )[ XX2R1R33 12.wThheures R is acyclic, contradicting inv(R) = 2. So X1R23 6= ; and X1L23 = ; . As above we obtain a contradiction by observing that L is acyclic, contradicting inv(L) = 2. This completes the proof of Subcase 3.1.
Subcase 3.2 X1R 23 = ; .
! X1L3 2 ! X1R3 2 ! X1L 23 ! X2L 6= X3L, so X1L2 3 6= ; .
By symmetry, we can assume X2R 13 = ; and X3R 12 6= ; . Hence X1L 23 ! X3L because X1L 23 ! X3R 12 ! X3L, and X1R X3R 12 because XX1R3R !12 !X1LX21L33 2!. BXy3Rsym12m.etNryotweethcaant oasnseumofe Xtha1L3t X2,1L3X1R23 =2 ; is. BemypCtylaismincCe, X2R3 1 ! X1L2 3 ! Thus X1R23 = ; .
SCulapipmosAe,fiXrs3Lt t h6=at ; Xs1Ro23X16=L23 ; 6 =. ;T.heNn oXw2L3X1L123 =! ; Xsi1Rn3ce2 X!2L3 X1 1L!23 X!1R23X1L!23, sXo1LX21R33 !2 =X;2L3. 1F.urtNheorwm,obrey,
X1R23 ! X1L 23 ! X2R3 1 so X2R3 1 = ; . Therefore X1R = X2R, a contradiction to Claim C. Next suppose X1L23 6= ; . Then X1R2 3 = ; because X1R2 3 ! so X1R3 2 6= ; and X2R3 1 6= ; . As X1R3 2 ! X1L 23 !
By Claim A, X3L 6= ; , so X2L3 1 6= ; . Thus X2R3 1 = ; because X2R3 1 ! X1L2 3 ! X3R 12 ! X2L3 1 ! X2R3 1. By X1R2 3 ! X1L 23 [ X2L3 1, Claim A, X2R 6= ; so X1R2 3 6= ; . By Claim C, X1R 6= X2R, so X1R3 2 6= ; . As X1L2 3 ! we have X1L2 3 ! X1L 23 [ X2L3 1. Thus the fact that dL+(X1L2 3) > 0 implies that there is an arc vz from X1L2 3 to ZL. But then for any u 2X1R3 2, (u, v, z, u) is directed 3-cycle, a contradiction.
This completes Subcase 3.2.
Case 4: All three of X1L 23, X2L 13, X3L 12 or all three of X1R 23, X2R 13, X3R 12 are non-empty.
By symmetry, we can assume that X1L 23, X2L 13, X3L 12 6= ; . There do not exist i, j 2 [
X1R 23, so since dR(X1R 23) > 0 we must have an arc from By symmetry we can assume that X1L 23, X2L 13 6= ; and X3L 12 = ; .
Case 5: Exactly two of X1L 23, X2L 13, X3L 12 or two of X1R 23, X2R 13, X3R 12 are non-empty. Subcase 5.1: X1R 23, X2R 13, X3R 12 = ; .
X1L3 2 [ subtournament of R and X1R3 2 ) contradicting inv(R) = 2.
This completes Subcase 5.1 Subcase 5.2: X1R 23 6= ; and X2R 13 [ X3R 12 = ; .
X1L 23 ! ZR, thus there is no arc leaving ZR. As R is strong, we get ZR = ; .
As X1L 23 ! X2R3 1 ! X2L 13 ! X1R3 2 ! X1L 23, one of X1R3 2, X2R3 1 is empty. By symmetry we may assume that X2R3 1 = ; . By Claim C, X1R 6= X2R and X1R 6= X3R, so X1R3 2 6= ; and X1R2 3 6= ; . Now V (R) \ ZR = X1R ! dR+(X1R23) = 0. Hence X1L23 = ; . By Claim A, X3L 6= ; , so X1L3 2 [ X2L3 1 6= ; .
As X1R2 3 ! X2L 13 ! X1R3 2, we have X1R2 3 ! X1R3 2. Hence as R is strong, necessarily X1R23 6= ; . If X1L23 6= ; , then X1R23 ! X1R2 3 [ X1R3 2 as X1R23 ! X1L23 ! X1R2 3 [ X1R3 2. This contradicts the fact that R is strong since
X1R3 2, we have X1R23 ! X1R23. Hence V (R) = X1R2 3 [ X1R3 2 [
X1R2 3 ) X1R23 ) X1R3 2. Thus inverting X1R2 3 [ X1R3 2 makes R acyclic,
X1R3 2. We also have X1R2 3 ! X1R23 because X1R2 3 !
X1R23 where each of these sets induces an acyclic X1R 23 ! X1L, X1R3 2 [ X1R2 3 ! X2L3 1 and X2R ! X2L 13) so we must have ZL = ; .
We first observe that since X2L 13 [ X2L3 1 ! X1R 23 ! X1L we can conclude that X2L 13 ! X1L and X2L3 1 ! X1L. As X2R3 1 ! X2L 13 ! X1L 23 ! X2R3 1, we have X2R3 1 = ; . Now V (R) \ ZR = X1R and X1R ! X1L 23 ! ZR. So V (R) \ ZR ! ZR. Since R is strong, ZR = ; . Now Claims A and C imply that at least two of the sets X1R3 2, X1R23, X1R2 3 are non-empty. This implies that every vertex of V (L) has an in-neighbour in V (R) (as Suppose first that X1R2 3 = ; . By Claim A, X2R 6= ; , so X1R23 6= ; . Moreover, by Claim C, X2R 6= X3R, so X1R3 2 6= ; . Since X1L2 3 [ X1L3 2 !
X1R23 !
X1L2 3 [ X1L3 2 we have X1L2 3 [ X1L3 2 = ; . If X2L3 1 6= ; , then X1L23 = ; as X2L3 1 ! X1L23 ! X1R3 2 ! X2L3 1 and we have X2L 13 ! X2L3 1 as X2L 13 ! X1R3 2 ! X2L3 1. Now we see that dL (X2L3 1) = 0, a contradiction. Hence X2L3 1 = ; and X1L23 6= ; because X3L 6= ; by Claim A. X1L23 where each Moreover X1L23 ! X1L 23 because X1L23 ! of these sets induces an acyclic subdigraph in L and X1L 23 )
X1R3 2 ! X1L 23. Now V (L) = X1L 23 [ X2L 13 [
X1L23 ) X2L 13 ) X1L 23. Then inverting the set by the same reasoning X1R23 ! X1R 23 to X1R3 2. Hence X1R3 2 6= ; and X2L3 1 = ; as X1R3 2 ! X2L3 1 ! X1L2 3 ! X1R23 ! X2L 13 ! X1R 23 ! X1L2 3. Finally, as X2L 13 ! X1R 23 ! now dL+(X1L) = 0 (recall that ZL = ; ), a contradiction. This completes Subcase 5.2 tNXhoa1L2tte3tht!ehraet XiXs1R1Ra22t 3l3ea!s!t oXnXe1R1Ra2r32c3 !f[romXX1R1XL3231R22. aF3sutroXth1XRe2r1Rm233ori!en tThXe(2aLfanc1dt3 itnh!aRt)dX.R+1R(WX2e1R32s[aw3)Xb1>Re3fo02re.i mthTpahltiueXss 1RXt2h1aL23t3X!=1R23 X;16=Rbe2;3caaaunnsdde X1R 23, hence, as ZR = ; and dR(X1R 23) > 0, there is at least one arc from
X1R 23. We have X1L2 3 = ; since
X1L we have X2L 13 ! X1L. But Subcase 5.3: X3R 12 6= ; and X1R 23 [
X2R 13 = ; .
As X2R3 1 ! X2L 13 ! X1R3 2 ! may assume that X2R3 1 = ; .
X2R3 1 one of the sets X1R3 2, X2R3 1 must be empty. By symmetry we have X1R2 3 6= ; .
Suppose first that X1R2 3 = ; . Then, by Claim A, X2R 6= ; , so X1R23 6= ; , and by Claim C, X1R 6= X2R, so X1R3 2 6= ; . hNXao3Lvwe6=XX;1R1L22b33y!=Cl; Xaib1mR3ecCa2,u[ wseeXXh3Ra1Lv213e2.X!N2Le3Xxt1R13w6=e2o;!bbsueXtrvt1Lheat2th3caot!nXtr1LXa3d3Ri2c1t=s2 t!h;astiXnXc1L2eL233X.11AL3!s 2XX!1R21R32X3!!1R23XX!2L3R1X1323R!!12XX!1R2L33X211L[.3SXo2.3RwNe1o2mw,,wuasest wiFCXXnile21rLLaRsihtm12,a33oivmbAe!!sp,eXlwrXyvX1Riee3n2L3R3ght2ha1t1vah26=et[a!tXXX;th1L2.L12XLe33rN2eL213o=3cw.6=a1Wn;,X;ewba.1Lease3SlnsXhioo2na1Lcvha2=eear3vcXXe;!e1L1ZnL2atLse2Xr33Xi=1nR!!21gL;3 Z3sXX2iLn!1R2L.c!23eNe3X1ovX.w!e1L1rMRy3V2oX3v(2reL2eL!ro!t)ev1x=3eXriX!nX3XR1LX12LL1X12L23211R3323!!3[!2[XXX!XX2L1L3R322L1R33X31.121L12[2A[!!sX3XX2wLX2XL1eR11L2L313h336=aw2vh1h.eaX[esXAra2eRXns1Le21LbiXanyc3-32Lhn3C=eo6=iligfam;hitmp.;hbleoiAbseCuyessr, sets induces a transitive subtournament in L and X1L 23 ) X2L3 1 ) X2L 13 ) X1L 23. However this implies that inverting X1L 23 [ X2L 13 makes L acyclic, a contradiction to inv(L) = 2. This completes the proof of Subcase 5.3. Subcase 5.4: X1R 23, X2R 13 6= ; and X3R 12 = ; .
This case is trivial as X1L 23 !
X2R 13 !
By symmetry the only remaining case to consider is the following.
Subcase 5.5: X1R 23, X3R 12 6= ; and X2R 13 = ; .
AiVXXss(11RReRmX2)!3p2L3(tya!sX1aX1sL!XX1R21L31L23X3a2n31R2d!!2!X3 3XR!XX1L12R21R33aX!n121dLw!XX2e332LRhX)!a.!v1LeTX2hX3Xi3Rs2R2!L3i1m211p3X!)li=3eRasn1Xd;t2h.2Lae3!tvNeZ1royXLtwe1Lve=3tehrhat2a;etvxaeaenvnidneXdray2VLZt3(RvlRee1ar)=tse=thxoa; nsi.;neaAaVnontfd(oLlXeua)at1Ls-s2nhtXeao3is2gRn,3hXeabn11oRo2fiun!rX3-ni1Lnie3siXgVeh22Lm,(bLXop13ut)1Ryr3(!aain2ss X1L2 3 ! X1R2 3 ! X2L 13 ! X1R 23 ! X1L2 3.
Moreover X1R23 ! contradiction.
Suppose first that X1R2 3 = ; = X1R3 2. Then X2R 6= ; by Claim A, so X1R23 6= ; .
X1R 23 [ X3R 12 because X1R23 ! X2L 13 ! X1R 23 [ X3R 12. This implies that dR+(X1R23) = 0, a we get the contradiction X1L23 ! X1R3 2 ! X1L 23 ! X3R 12 ! X1L23.
Now assume that X1R2 3 = ; = X1L3 2 and X1R3 2 6= ; 6 = X1L2 3. Then X1L23 6= ; as X3L 6= ; by Claim A and now