I NVERSION NUMBER OF AN ORIENTED GRAPH AND RELATED PARAMETERS Jørgen Bang-Jensen Jonas Costa Ferreira da Silva Department of Mathematics and Computer Science, Department of Computer Science University of Southern Denmark Universidade Federal do Ceará Odense, Denmark Fortaleza, Brazil jbj@imada.sdu.dk jonascosta@lia.ufc.br Frédéric Havet Université Côte d’Azur, CNRS, Inria, I3S, Sophia Antipolis, France frederic.havet@inria.fr A BSTRACT 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. Keywords Feedback vertex set · Feedback arc set · Inversion · Tournament · Oriented graph · Intercyclic digraph. 1 Introduction Notation not given below is consistent with [2]. Making a digraph acyclic by either removing a mininum cardinality set of arcs or vertices are important and heavily studied problems, known under the names C YCLE A RC T RANSVERSAL or F EEDBACK A RC S ET and C YCLE T RANSVERSAL or F EEDBACK V ERTEX S ET. A cycle transversal or feedback vertex set (resp. cycle arc-transversal or feedback arc set) in a digraph is a set of vertices (resp. arcs) whose deletion results in an acyclic digraph. The cycle transversal number (resp. cycle arc-transversal number) is the minimum size of a cycle transversal (resp. cycle arc-transversal) of D and is denoted by ⌧ (D) (resp. ⌧ 0 (D)). Note that if F is a minimum cycle arc-transversal in a digraph D = (V, A), then we will obtain an acyclic digraph from D by either removing the arcs of F or reversing each of these, that is replacing each arc uv 2 F by the arc vu. It is well-known and easy to show that ⌧ (D)  ⌧ 0 (D) (just take one end-vertex of each arc in a minimum cycle arc-transversal). Computing ⌧ (D) and ⌧ 0 (D) are two of the first problems shown to be NP-hard listed by Karp in [9]. They also remains NP-complete in tournaments as shown by Bang-Jensen and Thomassen [4] and Speckenmeyer [14] for ⌧ , and by Alon [1] and Charbit, Thomassé, and Yeo [7]. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). In this paper, we consider another operation, called inversion, where we reverse all arcs of an induced subdigraph. Let D be a digraph. The inversion of a set X of vertices consists in reversing the direction of all arcs of DhXi. We say that we invert X in D. The resulting digraph is denoted by Inv(D; X). If (Xi )i2I is a family of subsets of V (D), then Inv(D; (Xi )i2I ) is the digraph obtained after inverting the Xi one after another. Observe that this is independent of the order in which we invert the Xi : Inv(D; (Xi )i2I ) is obtained from D by reversing the arcs such that an odd number of the Xi contain its two end-vertices. 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 )a2F ) is acyclic. A decycling family of an oriented graph D is a family of subsets (Xi )i2I of subsets of V (D) such that Inv(D; (Xi )i2I ) 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 {vi vj | 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 2 A(D), or a = b and xy 2 A(H)}. It can be seen as blowing up each vertex of D by a copy of H. Using boolean dimension, Belkhechine et al. [5] proved the following. Theorem 1.2 (Belkhechine et al. [5]). inv(T Tn [C~3 ]) = n. 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. ~3] = C Observe that T Tn [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. [12] proved that there is a (minimum) function f such that ⌧ (D)  f (⌫(D)) for every digraph D. With Theorem 1.1 (ii), this implies inv(D)  f (⌫(D)). 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. [12] proof is huge (a multiply iterated exponential, where the number of iterations is also a multiply iterated exponential). The only known value has been established by McCuaig [10] who proved f (1) = 3. As noted in [12], the best lower bound on f due to Alon (unpublished) is f (k) k log k. It might be that f (k) = O(k log k). This would imply the following conjecture. 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 [13] and Goemans and Williamson [8], we get ⌧ (D)  63 · ⌫(D) for every planar digraph D. This implies that ⌧ (D)  126 · ⌫(D) for every planar digraph D and so Conjecture 1.6 holds for planar oriented graphs. 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 [10]. However we do not know if this bound 4 on g(1) is attained. Furthermore can we characterize the intercyclic digraphs with small inversion number ? Problem 1.7. For any k 2 [4], can we characterize the intercyclic oriented graphs with inversion number k ? In contrast to Theorem 1.1 and 1.5, the difference between inv and ⌫, ⌧ , and ⌧ 0 can be arbitrarily large as for every k, there are tournaments Tk for which inv(Tk ) = 1 and ⌫(Tk ) = k. Consider for example the tournament Tk obtained from three transitive tournaments A, B, C of order k by adding all arc form A to B, B to C and C to A. One easily sees that ⌫(Tk ) = k and so ⌧ 0 (Tk ) ⌧ (Tk ) k; moreover Inv(Tk ; A [ B) is a transitive tournament, so inv(Tk ) = 1. 1.2 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-I NVERSION. Input: An oriented graph D. Question: inv(D)  k ? We also study the complexity of the restriction of this problem to tournaments. k-T OURNAMENT-I NVERSION. Input: A tournament. Question: inv(T )  k ? Note that 0-I NVERSION 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 2 V (T ). We denote by IC k 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 IC k . Theorem 1.8 (Belkhechine et al. [6]). For any positive integer k, the set IC k is finite. Checking whether the given tournament T contains I for every element I in IC k+1 , one can decide whether inv(T ) k in O(|V (T )|mk+1 ) time, where mk+1 be maximum order of an element of IC k+1 . Corollary 1.9. For any non-negative integer k, k-T OURNAMENT-I NVERSION is polynomial-time solvable. The proof of Theorem 1.8 neither explicitly describes IC k 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 IC k or at least find an upper bound on mk . What is the minimum real number rk such that k-T OURNAMENT-I NVERSION can be solved in O(|V (T )|rk ) time ? As observed in [6], IC 1 = {C ~ 3 }, so m1 = 3. This implies that 0-T OURNAMENT-I NVERSION can be done in O(n3 ). However, deciding whether a tournament is acyclic can be solved in O(n2 )- time. Belkhechine et al. [6] also proved that IC 2 = {A6 , B6 , D5 , T5 , V5 } where A6 = T T2 [C ~3] = Inv(T T6 ; ({v1 , v3 }, {v4 , v6 })), B6 = Inv(T T6 ; ({v1 , v4 , v5 }, {v2 , v5 , v6 })), D5 = Inv(T T5 ; ({v2 , v4 }, {v1 , v5 })), R5 = Inv(T T5 ; ({v1 , v3 , v5 }, {v2 , v4 })), and V5 = Inv(T T5 ; ({v1 , v5 }, {v3 , v5 })). See Figure 1. v1 v4 v3 v5 v3 v2 v6 v5 v2 v4 v1 A6 D5 v5 v6 v3 v5 v5 v1 v4 v1 v1 v2 v3 v4 v3 v2 v2 v4 B6 R5 V5 Figure 1: The 2-inversion-critical tournaments Hence m2 = 6, so 1-T OURNAMENT-I NVERSION 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-T OURNAMENT-I NVERSION 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-I NVERSION is NP-complete. Note that together with Conjecture 1.3, this would imply that k-I NVERSION is NP-complete for every positive integer k. Conjecture 1.12. k-I NVERSION is NP-complete for all positive integer k. As we proved Conjecture 1.3. when inv(L) = inv(R) = 1, we get that 2-I NVERSION 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. Problem 1.14. Let k be a positive integer and be a parameter in {⌧ 0 , ⌧, ⌫}. What is the complexity of computing (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 )i2I is a decycling family of D, then (Xi \ V (D0 ))i2I 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 x is also a decycling family of D since adding a source (sink) to an acyclic digraph results in an acyclic digraph. 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 vi vj 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 vi vj 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, vi vj 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, vi vj 2 Inv(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. 3 Inversion number of dijoins of oriented graphs 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 2 X and y 2 / X, and there must be z 2 X \ 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 [2], XiL = Xi \ V (L) and XiR = Xi \ V (R). • Z L = V (L) \ (X1L [ X2L ) and Z R = V (R) \ (X1R [ X2R ). L • X12 = X1L \ X2L and X12 R = X1R \ X2R . • for {i, j} = {1, 2}, XiL j = (XiL \ XjL ) and XiR j = (XiR \ XjR ). X1L 2 X1R 2 X1L X1R L R X12 X12 X2L X2R X2L 1 X2R 1 ZL ZR Figure 2: The oriented graph D⇤ 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 = X12 R and D⇤ hV (F )i = F is not acyclic. Assume first that X1R 2 = ; and so X2R 1 6= ;. Suppose for a contradiction that X12 R 6= ; and let a 2 X2R 1 , b 2 X12 R . Let C be a directed cycle in L. Note that V (C) cannot be contained in one of the sets X1 2 , X12 or X2 1 . If V (C) \ Z L 6= ;, there is an arc cd 2 A(L) such that L L L c 2 X1L 2 [ X12 L [ X2L 1 and d 2 Z L . Then, either (c, d, a, c) or (c, d, b, c) is a directed cycle in D⇤ , a contradiction. Thus, V (C) ✓ X1L 2 [ X12 L [ X2L 1 . If V (C) \ X12L 6= ;, then there is an arc cd 2 A(L) such that c 2 X12 L and d 2 X1 2 [ X2 1 which means that dc 2 A(D ) and (d, c, b, d) is a directed cycle in D , a contradiction. Hence L L ⇤ ⇤ V (C) ✓ X1L 2 [ X2L 1 and there exists an arc cd 2 A(L) such that c 2 X2L 1 , d 2 X1L 2 and (c, d, a, c) is a directed cycle in D⇤ , a contradiction. Therefore X12 R = ; and every directed cycle of R has its vertices in X2R 1 [ Z R . Then, there is an arc ea 2 A(R) with a 2 X2 1 and e 2 Z R . Note that, in this case, ea 2 A(D⇤ ) and (e, a, c, e) is a directed cycle in D⇤ for any R L c 2 X12 [ X2L 1 . Thus, X12 L = 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 , Z L , Z R , X12 L , X12 R , X1L 2 , X2L 1 , X1 2 , and X2 1 as in Theorem 3.3. See Figure 2. Note that each of these sets induces an acyclic digraph in D⇤ and R R thus also in D. For i 2 [2], let Di = Inv(D; Xi ), let Li = Inv(L, XiL ) = Inv(L⇤ ; X2L i ), and Ri = Inv(R, XiR ) = Inv(R⇤ ; X2R i ). Since inv(D) = 2, inv(D1 ) = inv(D2 ) = 1. Since inv(R) = 2, R1 and R2 are both non-acyclic, so inv(R1 ) = inv(R2 ) = 1. Claim 1: XiL , XiR 6= ; for all i 2 [2]. Proof. Since inv(R) = 2, necessarily, X1R , X2R 6= ;. Suppose now that XiL = ;. Then Di = L ! Ri . As inv(L) 1 and inv(Ri ) 1, by Proposition 3.2 inv(Di ) 2, a contradiction. ⌃ Claim 2: X1L 6= X2L and X1R 6= X2R . 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 X12 R 6= ; and by Claim 2 , X1R 6= X2R , so X2R 1 6= ;. If X2L 1 6= ;, then, in D⇤ , X2R 1 [ X12 R Z R because X2R 1 [ X12 R ! X2L 1 ! Z R . But then R1 = Inv(R⇤ ; X2R ) would be acyclic, a contradiction. Thus, X2 1 = ;. L Then by Claims 1 and 2, we get X12 L , X1L 2 6= ;. Hence, as X12 R ! X1L 2 ! X2R 1 ! X12 L R ! X12 in D⇤ , there is a directed cycle in D , a contradiction. Therefore X1 2 6= ;. ⇤ R 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 X12 L , X1L 2 6= ;. Furthermore X12R = ; because X12 R ! X2L 1 ! X1R 2 ! L X12 ! X12 R in D⇤ . Now in D⇤ , X2R 1 X1R 2 [ Z R because X2R 1 ! X2L 1 ! X1R 2 [ Z R , and X1R 2 ZR because X1R 2 ! X12 L ! Z R . Thus, in D, we also have X2R 1 X1R 2 [ Z R and X1R 2 Z R . So R is acyclic, a contradiction to Inv(R) = 2. 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) 2. Then inv (L ! R) 4. 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. 4 Inversion number of intercyclic digraphs 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). Proof. McCuaig proved that D/a is strong and intercyclic. Let us prove that inv(D)  inv(D̃/a). Observe that 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 2 Xi . Let a = uv if w is in an even number of Xi and a = vu otherwise, and let R = Inv(D; (X1 , . . . , Xp )). 0 ⇤ 0 ⇤ 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 [3]. A digraph D is in reduced form if it is strongly connected, and it has no weak arc, that is min{ (D), + (D)} 2. Intercyclic digraphs in reduced form were characterized by Mc Cuaig [10]. In order to restate his result, we need some definitions. Let P(x1 , . . . , xs ; y1 , . . . , yt ) be the class of acyclic digraphs D such that x1 , . . . , xs , s 2, are the sources of D, y1 , . . . , yt , t 2, are the sinks of D, every vertex which is neither a source nor a sink has in- and out-degree at least 2, and, for 1  i < j  s and 1  k < `  t, every (xi , y` )-path intersects every (xj , yk )-path. By a theorem of Metzlar [11], such a digraph can be embedded in a disk such that x1 , x2 , . . . , xs , yt , yt 1 , . . . , y1 occur, in this cyclic order, on its boundary. Let T be the class of digraphs with minimum in- and out-degree at least 2 which can be obtained from a digraph in P(x+ , y + ; x , y ) by identifying x+ = x and y + = y . Let D7 be the digraph from Figure 3(a). y2 y3 y2 y3 y2 y3 y1 y y4 y1 y y4 y1 y y4 y6 y5 y6 y5 y6 y5 (a) (b) (c) Figure 3: (a): the digraph D7 ; (b): the digraph D70 obtained from D7 inverting the set {y, y2 , y4 , y6 }; (c): the acyclic digraph D700 obtained from D70 by inverting the set {y2 , y3 , y5 , y6 }. 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 w1 x0 , w1 x2 , z1 x1 , z1 x3 , x0 w0 , x2 w0 , x1 z0 ,x3 z0 (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 [10]). The class of intercyclic digraphs in reduced form is T [ {D7 } [ K [ H. 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. x0 w1 z0 x1 x2 z1 w0 x3 KH Figure 4: The digraphs from K. The arrow in the grey area symbolizing the acyclic (plane) digraph KH indicates that z0 , w0 are its sources and z1 , w1 are its sinks. y4 y3 y1 y4 y5 y1 y2 y5 y2 y3 y1 y2 y3 y4 H↵ H H Figure 5: The digraphs from 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 2 P(y1 , y2 ; y3 , y4 ), we have H 2 P(y4 , y3 ; y2 , y1 ). Set Y = {y1 , y2 , y3 , y4 , y5 }. We claim that every directed cycle C 0 of D0 contains y5 . Since D0 Y is acyclic, C 0 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 C 0 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 C 0 . 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 [10], D/a is also intercyclic. So by Lemma 4.2 and the induction hypothesis, inv(D)  inv(D/a)  4. Henceforth, we may assume that D has no weak arc. Thus D is in a reduced form and by Corollary 4.5, inv(D)  4. 5 Complexity results 5.1 NP-hardness of 1-I NVERSION and 2-I NVERSION Theorem 5.1. 1-I NVERSION 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 Figure 6: The digraph J 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 M ONOTONE 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 cji into one vertex ci . Then, for every clause Cj = xi1 _ xi2 _ xi3 , we add the arcs of the directed 3-cycle Dj = (aji1 , aji2 , aji3 ). Observe that D is strong. We shall prove that inv(D) = 1 if and only if admits a 1-in-3-SAT assignment. 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], Sm Sm either X \ V (Ki ) = j=1 {aji , bji , eji } or X \ V (Ki ) = j=1 {bji , ci , dji }. Let ' be the truth assignment defined by Sm Sm '(xi ) = true if X \ V (Ki ) = j=1 {bji , ci , dji }, and '(xi ) = f alse if X \ V (Ki ) = j=1 {aji , bji , eji }. Consider a clause Cj = xi1 _ xi2 _ xi3 . Because Dj is a directed 3-cycle, X contains exactly two vertices in V (Dj ). Let `1 and `2 be the two indices of {i1 , i2 , i3 } such that aj`1 and aj`2 are in X and `3 be the third one. By our definition of ', we have '(x`1 ) = '(x`2 ) = f alse and '(x`3 ) = true. Therefore, ' is a 1-in-3 SAT assignment. Sm j j Assume now that admits a 1-in-3 SAT assignment '. For every i 2 [n], let Xi = j=1 {bi , ci , di } if '(xi ) = true Sm Sn and Xi = j=1 {aji , bji , eji } if '(xi ) = f alse, and set X = i=1 Xi . 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 assignment, w.l.o.g., we may assume that '(xi1 ) = '(xi2 ) = f alse and '(xi3 ) = true. Hence in D0 , aji2 ! aji1 , aji2 ! aji3 and aji3 ! aji1 . Moreover, in D0 hV (Jij1 )i, aji1 is a sink, so aji1 is a sink in D0 . Therefore C does not goes through aji1 , and thus C contains the arc aji2 aji3 , and then enter Jij3 . But in D0 hV (Jij3 )i, aji3 has a unique out-neighbour, namely bji3 , which is a sink. This is a contradiction. Corollary 5.3. 2-I NVERSION is NP-complete. 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-T OURNAMENT-I NVERSION for k 2 {1, 2} Theorem 5.4. 1-T OURNAMENT-I NVERSION 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-T OURNAMENT-I NVERSION in O(n3 ) time. Theorem 5.5. 2-T OURNAMENT-I NVERSION 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) = N + (s) \ N (t) B(s, t) = N (s) \ N + (t) C(s, t) = N + (s) \ N + (t) D(s, 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 2 A(T ), C(s, t) = D(s, t) = ; and X1 = {s, t} [ B(s, t). (2) If s 2 X1 \ X2 , t 2 X2 \ X1 , and the inversion of X1 and X2 makes T acyclic, then st 2 A(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 2 X1 \ X2 and t 2 X1 \ X2 , then ts 2 A(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 ✓ A(s, t) [ {s, t}, and B(s, t) = X1 4X2 . Proof. (1) The arc between s and t is reversed once, so ts 2 A(T ). Assume for a contradiction, that there is a vertex c 2 C(S, t). The arc tc must be reversed, so c 2 X1 , 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 2 A(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 2 A(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 2 A(T ). Assume for a contradiction, that there is a vertex c 2 C(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) = X1 4X2 . 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 2 X1 \ X2 and t 2 X2 \ 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 2 X1 \ X2 and t 2 X1 \ 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 2 A(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 2 A(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 2 A(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 2 A(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) = X1 4X2 . 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 (b) s0 2 X10 \ X20 and t0 2 X20 \ X10 . For the possibilties corresponding to Case (a), we proceed as in (1) above. For every arc t0 s0 2 A(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 t0 s0 . For a possibilities corresponding to Case (b), we proceed as in (2) above. For every arc t0 s0 2 A(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 t0 s0 . 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 [2] so the arcs between Z and B(s, t) will be reversed exactly once when we invert X1 and X2 . Using this fact, one easily checks that this is possible if and only there are integers j1  · · ·  jp such that • either bj ! ai for j  ji and bj ai for j > ji (in which case ai 2 / Z and the arcs between ai and B(s, t) are not reversed), • or bj ai for j  ji and bj ! ai for j > ji (in which case ai 2 Z 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 Figure 7: Indicating how to merge the two orderings of A and B. The fat blue edges indicate that the final ordering will be b1 b3 , a1 a4 , b4 b6 , a5 a8 , b7 b9 , a9 a11 , b10 b12 . The set Z = {a2 , a6 , a10 } consists of those vertices from A(s, t) which are in X1 \ X2 . These vertices are shown in red. The red arcs between a vertex of Z and one of the boxes indicate that all arcs between the vertex and those of the box have the direction shown. Hence the boxes indicate that values of j1 , . . . , j11 satisfy that : j1 = . . . = j4 = 3, j5 = . . . = j8 = 6, j9 = . . . = j11 = 9. 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 2 X1 \ X2 and t 2 X2 \ X1 . Such a possibility can be check in O(n2 ) by Lemma 5.7 (2). • s 2 X1 \ X2 and t 2 X1 \ X2 . Such a possibility can be check in O(n2 ) by Lemma 5.7 (3). • t 2 X1 \ X2 and s 2 X1 \ 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. 5.3 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). S Proof. (i) Inverting the set a2A(D) {xa , ya } makes S2 (D) acyclic. Indeed the xa become sinks, the ya become source 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 2 A(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 | xa ya 2 F } 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 xa ya for each a 2 A(D), we obtain another cycle arc-transversal. So we may assume that F 0 ✓ {xa ya | a 2 A(D)}. Then F = {a | xa ya 2 F 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. Acknowledgement 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. References [1] N. Alon. Ranking tournaments. SIAM J. Discrete Math., 20:137–142, 2006. [2] J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer-Verlag, London, 2nd edition, 2009. [3] J. Bang-Jensen and M. Kriesell. On the problem of finding disjoint cycles and dicycles in a digraph. Combinatorica, 31:639–668, 2011. [4] J. Bang-Jensen and C. Thomassen. A polynomial algorithm for the 2-path problem for semicomplete digraphs. SIAM J. Discrete Math., 5:366–376, 1992. [5] H. Belkhechine, M. Bouaziz, I. Boudabbous, and M. Pouzet. Inversions in tournaments. Unpublished. [6] H. Belkhechine, M. Bouaziz, I. Boudabbous, and M. Pouzet. Inversion dans les tournois. Comptes Rendus Mathematique, 348(13):703 – 707, 2010. [7] P. Charbit, S. Thomassé, and A. Yeo. The minimum feedback arc set problem is NP-hard for tournaments. Combin. Probab. Comput., 16:1–4, 2007. [8] M. X. Goemans and D. P. Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs. In W. H. Cunningham, S. T. McCormick, and M. Queyranne, editors, Integer Programming and Combinatorial Optimization, pages 147–161, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg. [9] R. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Symp., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85–103. Plenum, 1972. [10] W. McCuaig. Intercyclic digraphs. In N. Robertson and P. D. Seymour, editors, Graph Structure Theory, Proceedings of a AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors held June 22 to July 5, 1991, at the University of Washington, Seattle, USA, volume 147 of Contemporary Mathematics, pages 203–245. American Mathematical Society, 1991. [11] A. Metzlar. ‘Minimum transversal of cycles in intercyclic digraphs. PhD thesis, University of Waterloo, Ontario, Canada, 1989. [12] B. A. Reed, N. Robertson, P. D. Seymour, and R. Thomas. Packing directed circuits. Combinatorica, 16(4):535– 554, 1996. [13] B. A. Reed and F. B. Shepherd. The gallai-younger conjecture for planar graphs. Combinatorica, 16(4):555–566, 1996. [14] E. Speckenmeyer. On feedback problems in digraphs. In WG 1989, volume 411 of Lect. Notes Comput. Sci., pages 218–231. Springer, 1989. 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) 2. Then inv (L ! R) 4. Proof. Assume for a contradiction that there are two digraphs L and R such that inv (L), inv (R) 2 and inv (L ! 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 [3]. • Z L = V (L) \ (X1L [ X2L [ X3L ) and Z R = V (R) \ (X1R [ X2R [ X3R ) L • X123 = X1L \ X2L \ X3L , X123 R = X1R \ X2R \ X3R . k = (Xi \ Xj ) \ Xk and Xij k = (Xi \ Xj ) \ Xk . L L L L R R R R • Xij • 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 2 Q has an arc to every w 2 W . 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 [3]. 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) X123 R L ! X123 R ! Xij k ! Xik j ! X123 . L R (b) Xij L k ! Xij k ! Xik j ! Xik j ! Xij k . R L R L 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 X 1 , 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: XiL jk = ; = XiR jk for all i, j, k. By Claim C, at least two of the sets X12 L 3 , X13 2 , X23 1 are non-empty and at least two of the sets L L X12 3 , X13 2 , X23 1 are non-empty. Without loss of generality, X12 R R R L 3 , X13 2 6= ;. Now, by Claim B (b), L implies that one of X12 R 3 , X13 2 must be empty. By interchanging the names of X2 , X3 if necessary, we may R assume that X13 2 = ; and hence, by Claim C, X12 R R 3 , X23 1 6= ;. By Claim B (a), this implies X23 1 = ;. Now R L 1 ! X12 3 ! X12 3 , so X23 1 ! X13 2 . As X12 3 ! X12 3 ! X13 2 , we must have X12 3 ! X13 2 . R L R R R L R L L L X23 By Claim B (a), X123 ! X12 3 ! X13 2 ! X123 ! X123 , so one of X123 and X123 is empty. W.l.o.g. we may L R L R L L R assume X123 R = ;. As R is strong and X23R 1 dominates X12 3 in R (these arcs are reversed by X2 ), we must have R Z 6= ;. Moreover the arcs incident to Z are not reversed, so the set Z R has an out-neighbour in X12 R R R 3 [ X23 1 . R But X12 3 [ X23 1 ! X13 2 ! Z so T has a directed 3-cycle, contradiction. This completes the proof of Case 1. R R L R 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 X12 R 3 [ X13 2 6= ;. By symmetry, we can assume that X12 3 6= ;. R R Suppose for a contradiction that X23R 1 = ;. Then Claims A and C imply X13 2 6= ;. Now, by Claim B (b), one of R X12 3 , X13 2 is empty. By symmetry, we can assume X13 2 = ;. Now, by Claim C, X2L 6= X3L , so X12 L L L L 3 6= ;. Note that X12 3 ! X12 3 ! X1 23 , thus X12 3 ! X1 23 because T is acyclic. We also have X123 ! X12 L R L L L L L 3 as X123 ! X13 2 ! X12 3 , and X12 3 ! X23 1 as X12 3 ! X12 3 ! X23 1 . This implies that in L all arcs L R L L L L R L between X12L 3 and X23 1 [ X123 [ X1 23 are entering X12 3 (the arcs between X123 and X12 3 were reversed L L L L L L twice and those between X1 23 [ X23 1 and X12 3 were reversed once). Hence, as L is strong, we must have an arc L L L uz from X12L 3 to Z . But Z ! X13 2 ! X12 3 so together with uz we have a directed 3-cycle in T , contradiction. L L R L Hence X23 1 6= ;. R Observe that X12 R 3 [ X13 2 ! X23 1 as X12 3 [ X13 2 ! X1 23 ! X23 1 . R R R R L R If X12 L 3 6= ;, then X23 1 ! X12 3 ! X12 3 ! X23 1 , a contradiction. So X12 3 = ;. But X2 6= X3 by Claim R L R R L L L C. Thus X13 2 6= ;. As X23 1 ! X13 2 ! X123 , we have X23 1 ! X123 . This implies that in R all the arcs L R L R R R between X23 R 1 and X13 2 [ X123 [ X12 3 are leaving X23 1 . So as R is strong there must be an arc in R from Z R R R R R to X23 1 . This arc is not reversed (in fact reversed twice), so it is also an arc in T . But since X23 1 ! X13 2 ! Z , R R L R 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 X12 L 3 and X13 2 is non-empty. By symmetry we may assume X12 3 6= ;. L L Suppose X12 R 3 6= ;. Then X23 1 = ; as X1 23 ! X23 1 ! X12 3 ! X12 3 ! X1 23 , and X23 1 = ; as R L R L R L L X1 23 ! X12 3 ! X12 3 ! X23 1 ! X1 23 . R L R L R By Claim B (b), one of X13 L 2 , X13 2 is empty. By symmetry, we may assume X13 2 = ;. R R Observe that V (R) \ Z R = X123 R R [ X12 3 [ X1 23 , so V (R) \ Z ! X1 23 ! Z , so V (R) \ Z ! Z . But all R R L R R R the arcs incident to Z are not inversed, so in R, there is no arc from Z to V (R) \ Z . Since R is strong, Z R = ;. R R R NowX1R 23 ! X12 R 3 [ X123 because X1 23 ! X12 3 ! X12 3 [ X123 . But all the arcs between X1 23 and R R L R R R X12 3 [ X123 = V (R) \ X1 23 are inversed from R to T . Hence in R, no arcs leaves X1 23 in R, a contradiction to R R R R R being strong. Hence X12 R 3 = ;. As X2 6= X3 this implies X13 2 6= ;. R R R Suppose that X23 R 1 = ;, then X123 6= ; because X2 6= ; by Claim A. Furthermore X13 2 ! X123 as X13 2 ! R R R R R X12 3 ! X123 , and X12 3 ! X1 23 as X12 3 ! X123 ! X1 23 . This implies that X123 = ; as X123 L R L L L R L L L ! X13 2 ! X123 ! X123 . R R L Since L is strong, there must be an arc uv leaving X12L 3 in L. But v cannot be in X1 23 since all vertices of this set L dominate X12 3 in L. Moreover v cannot be in Z for otherwise (u, v, w, u) would be a directed 3-cycle in T for any L L w 2 X1R 23 since Z L ! X1R 23 ! X12 L 3 . Hence v 2 X13 2 [ X23 1 , so X13 2 [ X23 1 6= ;. L L L L As X13 L 2 ! X13 2 ! X23 1 ! X1 23 ! X13 2 , precisely one of X13 2 , X23 1 is non-empty. R L R L L L If X13 L 2 6= ; and X23 1 = ;, then X13 2 ! X13 2 ! X1 23 [ X12 3 implies that X13 2 ! X1 23 [ X12 3 . As L L R L L L L L + dL (X13 2 ) > 0 there exists z 2 Z such that there is an arc uz from X13 2 to Z , but then z ! X1 23 ! u ! z is L L L L R a contradiction. Hence X13 L 2 = ; and X23 1 6= ;. Then X23 1 ! X1 as X23 1 ! X1 23 ! X1 . L L L L R L Note that Z L = ; as every vertex in V (L) \ Z L has an in-neighbour in V (R) in T , implying that there can be no arc from V (L) \ Z L to Z L in L. Thus V (L) = X1L 23 [ X12 L 3 [ X23 1 where each of these sets induces an acyclic L subdigraph of L and we have X1 23 ) X12 3 ) X23 1 ) X L L L 1 23 in L. But now inverting the set X1L 23 [ X23 L 1 makes L acyclic, a contradiction to inv(L) = 2. Thus X23 R 1 6= ;. Suppose X23 L 1 = ;. As above Z L = ;, so V (L) = X1L . As X1L 23 ! X23 R 1 ! X12 3 [ X13 2 we have L L + X1 23 ! X12 3 [ X13 2 . Thus, using dL (X1 23 ) > 0, we get X123 6= ;. As X123 ! X123 ! X23 L L L L L R L R 1 ! X12 3 ! X123 , we have X123 = ;. Moreover X1 ! X23 1 because X1 ! X1 23 ! X23 1 . We also have L R R R R R L R X1R 23 ! X13 2 as X1 23 ! X123 ! X13 2 . Now V (R) \ Z 2 [ X23 1 ! X12 3 ! Z . R R L R R = X1R 23 [ X13 R R L R Thus Z R = ; and V (R) = X1R 23 [ X13 R 2 [ X23 1 where each of these sets induces an acyclic digraph in R and R X1 23 ) X23 1 ) X13 2 ) X1 23 in D. But then inverting X1R 23 [ X23 R R R R R 1 we make R acyclic, a contradiction to inv(R) = 2. Thus X23 1 6= ;. L Therefore X13 L 2 = ; as X13 2 ! X13 2 ! X23 1 ! X23 1 ! X13 2 . As X1 23 ! X23 1 ! X12 3 L R L R L L R L we have X1 23 ! X12 3 ; As X23 1 ! X1 23 ! X1 23 [ X12 3 we have X23 1 ! X1 23 [ X12 3 ; As L L L R L L L L L X1R 23 ! X1L 23 ! X23 1 we have X1 23 ! X23 1 ; as X13 2 ! X23 1 ! X1 23 [ X23 1 we have X13 2 ! R R R R L R R R X1R 23 [ X23 R 1 . As every vertex in V (R) \ Z R has an out-neighbour in V (L), we derive as above Z R = ;. Similarly, as every vertex in V (L) \ Z L has in-neighbour in V (R), we get Z L = ;. Next observe that at least one of the sets X123 R L , X123 must be empty as X123R ! X123L ! X23R 1 ! X L 12 3 ! X R 123 . If X R 123 = ; then V (R) = X R 1 23 [ X R 13 2 [ X 23 1 where R each of these sets induces an acyclic subtournament of R and X1R 23 ) X23 R 1 ) X13 2 and X1 23 ) X13 2 . Thus R R R R is acyclic, contradicting inv(R) = 2. So X123 6= ; and X123 = ;. As above we obtain a contradiction by observing R L that L is acyclic, contradicting inv(L) = 2. This completes the proof of Subcase 3.1. Subcase 3.2 X1R 23 = ;. 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 X1R ! X1L 23 ! X3R 12 . Note that one of X13 L 2 , X13 2 is empty since R 2 ! X13 2 ! X1 23 ! X3 12 ! X13 2 . By symmetry we can assume that X13 2 = ;. By Claim C, L R L R L L X13 X2 6= X3 , so X12 3 6= ;. L L L Suppose first that X123 R 6= ;. Then X23 L 1 = ; since X23 1 ! X123 ! X1 23 ! X23 1 . Now, by L R L L Claim A, X3 6= ; so X123 6= ;. Now X123 ! X13 2 ! X1 23 ! X123 , so X13 2 = ;. Furthermore, L L L R L L R 1 ! X12 3 ! X123 ! X1 23 ! X23 1 so X23 1 = ;. Therefore X1 = X2 , a contradiction to Claim C. R L R L R R R R X23 Thus X123 R = ;. Next suppose X123 L 6= ;. Then X12 R 3 = ; because X12 3 ! X3 12 ! X123 ! X12 3 . By Claim A, X1 , X2 6= ;, R R L R R R so X13 2 6= ; and X23 1 6= ;. As X13 2 ! X1 23 ! X3 12 [ X23 1 we have X13 2 ! X3 12 [ X23 R R R L R R R R R 1. Since d+ R (X13 2 ) > 0 we have Z R R 6= ;. However, there can be no arcs from Z R to X3R = V (R) \ Z R , because X3 ! X123 ! Z . This contradicts the fact that R is strong. Thus X123 R L R L = ;. By Claim A, X3L 6= ;, so X23L 1 6= ;. Thus X23 1 = ; because X23 1 ! X12 3 ! X3 12 ! X23 1 ! X23 1 . By R R L R L R Claim A, X2 6= ; so X12 3 6= ;. By Claim C, X1 6= X2 , so X13 2 6= ;. As X12 3 ! X12 3 ! X1 23 [ X23 R R R R R L R L L 1, + we have X12 3 ! X1 23 [ X23 1 . Thus the fact that dL (X12 3 ) > 0 implies that there is an arc vz from X12 3 to L L L L L Z L . But then for any u 2 X13 R 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 [3] such that XiR \ XjR , XjR \ XiR 6= ;, for otherwise XiL jk ! (XjR \ XiR ) ! XjL ik ! (XiR \ XjR ) ! XiL jk , a contradiction. Hence we may assume by symmetry that X2R \ X1R , X3R \ X1R , X2R \ X3R = ;. This implies that X2R = X123R , X3R = X123 R R [ X13 2 and X1 = X123 [ X13 2 [ X1 23 . Moreover, X1 23 , X123 , X13 2 6= ; by R R R R R R R Claim C. As X3 ! X3 12 ! X1 23 we have X3 ! X1 23 , so since dR (X1 23 ) > 0 we must have an arc from R L R R R R Z R to X1R 23 and now X1R 23 ! X1L 23 ! Z R gives a contradiction. This completes Case 4. Case 5: Exactly two of X1L 23 , X2L 13 , X3L 12 or two of X1R 23 , X2R 13 , X3R 12 are non-empty. By symmetry we can assume that X1L 23 , X2L 13 6= ; and X3L 12 = ;. Subcase 5.1: X1R 23 , X2R 13 , X3R 12 = ;. As X1L 23 ! X23R 1 ! X2 13 ! X13 2 ! X1 23 , one of X13 2 , X23 1 is empty. By symmetry we may assume L R L R R that X23 1 = ;. By Claim C, X1 6= X2 and X1 6= X3 , so X13 2 6= ; and X12 R R R R R R R 3 6= ;. Now V (R) \ Z = X1 ! R R X1 23 ! Z , thus there is no arc leaving Z . As R is strong, we get Z = ;. L R R R As X12 R 3 ! X2 13 ! X13 2 , we have X12 3 ! X13 2 . Hence as R is strong, necessarily X123 6= ;. If X123 6= ;, L R R R R L then X123 ! X12 3 [ X13 2 as X123 ! X123 ! X12 3 [ X13 2 . This contradicts the fact that R is strong since R R R R L R R d+ R (X123 ) = 0. Hence X123 = ;. By Claim A, X3 6= ;, so X13 2 [ X23 1 6= ;. R L L L L Since X123 R ! X2L 13 ! X13 R 2 , we have X123 ! X13 2 . We also have X12 3 ! X123 because X12 3 ! R R R R R X13 2 [ X23 1 ! X123 . Hence V (R) = X12 3 [ X13 2 [ X123 where each of these sets induces an acyclic L L R R R R subtournament of R and X13R 2 ) X12 3 ) X123 ) X13 2 . Thus inverting X12 3 [ X13 2 makes R acyclic, R R R R R contradicting inv(R) = 2. This completes Subcase 5.1 Subcase 5.2: X1R 23 6= ; and X2R 13 [ X3R 12 = ;. We first observe that since X2L 13 [ X23 L 1 ! X1 23 ! X1 we can conclude that X2 13 ! X1 and X23 1 ! X1 . R L L L L L As X23 1 ! X2 13 ! X1 23 ! X23 1 , we have X23 1 = ;. Now V (R) \ Z = X1 and X1 ! X1 23 ! R L L R R R R R L Z R . So V (R) \ Z R ! Z R . Since R is strong, Z R = ;. Now Claims A and C imply that at least two of the sets X13 R 2 , X123 , X12 3 are non-empty. This implies that every vertex of V (L) has an in-neighbour in V (R) (as R R X1 23 ! X1 , X13 2 [ X12 R L R R 3 ! X23 1 and X2 ! X2 13 ) so we must have Z = ;. L R L L Suppose first that X12 R 3 = ;. By Claim A, X2 6= ;, so X123 6= ;. Moreover, by Claim C, X2 6= X3 , so X13 2 6= ;. R R R R R Since X12 3 [ X13 2 ! X123 ! X2 13 ! X12 3 [ X13 2 we have X12 3 [ X13 2 = ;. If X23 1 6= ;, then L L R L L L L L L L X123 = ; as X23 L 1 ! X123 ! X13 2 ! X23 1 and we have X2 13 ! X23 1 as X2 13 ! X13 2 ! X23 1 . L R L L L L R L Now we see that dL (X23 1 ) = 0, a contradiction. Hence X23 1 = ; and X123 6= ; because X3 6= ; by Claim A. L L L L Moreover X123L ! X1L 23 because X123 L ! X13R 2 ! X1 23 . Now V (L) = X1 23 [ X2 13 [ X123 where each L L L L of these sets induces an acyclic subdigraph in L and X1 23 ) X123 ) X2 13 ) X1 23 . Then inverting the set L L L L X1L 23 [ X2L 13 makes L acyclic, a contradiction to inv(L) = 2. Thus X12 R 3 6= ;. Note that X12 R 3 ! X1 23 [ X13 2 as X12 3 ! X2 13 ! X1 23 [ X13 2 . Thus X123 = ; because R R R L R R L + X123 ! X12 3 ! X1 23 ! X123 . Furthermore the fact that dR (X12 3 ) > 0 implies that X123 L R R L R R 6= ; and that there is at least one arc from X12 3 to X123 in T (and in R). We saw before that X12 3 ! X1R 23 and R R R by the same reasoning X123 R ! X1R 23 , hence, as Z R = ; and dR (X1R 23 ) > 0, there is at least one arc from X1R 23 to X13R 2 . Hence X 13 2 6= ; and X23 1 = ; as X13 2 ! X23 1 ! X1 23 . We have X12 3 = ; since R L R L R L X12 3 ! X123 ! X2 13 ! X1 23 ! X12 3 . Finally, as X2 13 ! X1 23 ! X1 we have X2 13 ! X1L . But L R L R L L R L L now d+ L (X1 ) = 0 (recall that Z = ;), a contradiction. This completes Subcase 5.2 L L Subcase 5.3: X3R 12 6= ; and X1R 23 [ X2R 13 = ;. As X23 R 1 ! X2 13 ! X13 2 ! X1 23 ! X23 1 one of the sets X13 2 , X23 1 must be empty. By symmetry we L R L R R R may assume that X23 1 = ;. R Suppose first that X12 R 3 = ;. Then, by Claim A, X2 6= ;, so X123 6= ;, and by Claim C, X1 6= X2 , so X13 2 6= ;. R R R R R Now X123 = ; because X123 ! X13 2 ! X1 23 ! X3 12 ! X123 . As X123 ! X2 13 ! X13 2 [ X3R 12 , we L L R L R L R L R have X123 R ! X13 R 2 [ X3 12 . Next we observe that X13 2 = ; since X13 2 ! X123 ! X3 12 ! X13 2 . Now, as R L L R R L X3 6= ; by Claim C, we have X23 1 6= ; but that contradicts that X23 1 ! X123 ! X3 12 ! X23 1 . So we must L L L R R L have X12 R 3 6= ;. First observe that X123L = ; as X123 L ! X12R 3 ! X1 23 ! X3 12 ! X123 . As X1 6= X2 by Claim C, L R L R R we have X13 2 6= ;. Now X13 2 = ; as X13 2 ! X13 2 ! X1 23 ! X3 12 ! X13 2 . As X3L 6= ; by R L L R L R L Claim A, we have X23 L 1 6= ;. Since X12 3 ! X12 3 ! X2 13 ! X13 2 ! X12 3 we have X12 3 = ;. As L R L R L L X1 23 ! X3 12 ! X23 1 , we have X1 23 ! X23 1 . Moreover X2 13 ! X13 2 ! X23 1 [ X1L 23 implies L R L L L L R L X2L 13 ! X23 1 [ X1 23 . We also have Z = ; since every vertex in X1 23 [ X23 1 [ X2 13 has an in-neighbour L L L L L L in R, implying that there can be no arc entering Z . Now V (L) = X1 23 [ X23 1 [ X2 13 where each of these L L L L sets induces a transitive subtournament in L and X1L 23 ) X23L 1 ) X2 13 ) X1 23 . However this implies that L L inverting X1 23 [ X2 13 makes L acyclic, a contradiction to inv(L) = 2. This completes the proof of Subcase 5.3. L L Subcase 5.4: X1R 23 , X2R 13 6= ; and X3R 12 = ;. This case is trivial as X1L 23 ! X2R 13 ! X2L 13 ! X1R 23 ! X1L 23 contradicts that T is acyclic. By symmetry the only remaining case to consider is the following. Subcase 5.5: X1R 23 , X3R 12 6= ; and X2R 13 = ;. As X23L 1 ! X1 23 ! X1 23 ! X3 12 ! X23 1 we have X23 1 = ; and as X23 1 ! X2 13 ! R L R L L R L X1R 23 ! X1L 23 ! X23 R 1 we have X R 23 1 = ;. Note that every vertex in V (L) has an in-neighbour in V (R) (as X1 23 ! X1 and X2 ! X2 13 ) and every vertex in V (R) has an out-neighbour in V (L) (as R L R L X1R ! X1L 23 and X3R 12 ! X3L ). This implies that Z L = ; and Z R = ;. At least one of X13 L R 2 , X13 2 is empty as X13 2 ! X13 2 ! X1 23 ! X3 12 ! X13 2 and at least one of X12 3 , X12 3 is empty as L R L R L L R 3 ! X12 3 ! X2 13 ! X1 23 ! X12 3 . L R L R L X12 Suppose first that X12 R 3 = ; = X13 2 . Then X2 6= ; by Claim A, so X123 6= ;. R R R Moreover X123R ! X1R 23 [ X3R 12 because X123 R ! X2L 13 ! X1R 23 [ X3R 12 . This implies that d+ R (X123 ) = 0, a R contradiction. Suppose next that X12 L 3 = ; = X13 2 . Then X3 6= ; by Claim A, so X123 6= ;. Moreover X1 23 [ X2 13 ! X123 L L L L L L as X1 23 [ X2 13 ! X3 12 ! X123 . This implies that dL (X123 ) = 0, a contradiction. L L R L L Now assume that X12 R 3 = ; = X13 2 and X13 2 6= ; = L R L 6 X12 3 . Then X123 6= ; as X3 6= ; by Claim A and now L L we get the contradiction X123 ! X13 2 ! X1 23 ! X3 12 ! X123 . L R L R L The final case is X12 R 3 6= ; = L 6 X13 2 and X13 2 = ; = X12 3 . We first observe that X123 = ; as X123 ! X1 23 ! R L R R L X3 12 ! X13 2 ! X123 . As X12 3 ! X2 13 ! X1 23 we have X12 3 ! X1 23 and as X1 23 ! X1 23 ! R L R R L R R R R L X3R 12 we have X1R 23 ! X3R 12 . This implies that dR (X1R 23 ) = 0, a contradiction. This completes Subcase 5.5 and the proof of the theorem.