Frédéric Havet
email: frederic.havet@inria.fr.

A Karolinna Maia

On disjoint directed cycles with prescribed minimum lengths

Keywords: k-linkage, circumference, disjoint directed cycles, subdivision k-linkage, circonférence, cycles dirigés disjoints, subdivision

In this paper, we show that the k-Linkage problem is polynomial-time solvable for digraphs with circumference at most 2. We also show that the directed cycles of length at least 3 have the Erdős-Pósa Property : for every n, there exists an integer t n such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of t n vertices that meets every directed cycle of length at least 3. From these two results, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F.

Introduction

All digraphs considered is this paper are strict, that is they have no loops nor multiple arcs. We rely on [START_REF] Bondy | Graph Theory[END_REF] for classical notation and concepts.

Let D 1 and D 2 be two digraphs, the disjoint union of D 1 and D 2 is denoted by D 1 + D 2 . For any digraph D, we set 2D = D + D and for any integer n greater than 2, nD = (n -1)D + D. In other words, nD is the disjoint union of n copies of D.

A digraph is connected if its underlying graph is connected. The components of a digraph are the (connected) components of its underlying graph. Hence, a digraph is the disjoint union of its components.

A linkage L in a digraph D is a subdigraph which is the disjoint union of directed paths. If L = P 1 + • • • + P k and P i is a directed (x i , y i )-path, 1 ≤ i ≤ k, then we say that L is a k-linkage from (x 1 , . . . , x k ) to (y 1 , . . . , y k ). If X,Y ⊆ V (D) and {x 1 , . . . , x k } ⊆ X and {y 1 , . . . , y k } ⊆ Y , then we say that L is a k-linkage from X to Y .

If P is a directed path, then its initial vertex is denoted by s(P) and its terminal vertex by t(P).

Finding a subdivision of a digraph

A subdivision of a digraph F, also called an F-subdivision, is a digraph obtained from F by replacing each arc ab of F by a directed (a, b)-path.

It is natural to consider the following decision problem. F -SUBDIVISION Input: A digraph D. Question: Does D contain a subdivision of F?

The analogue problem for undirected graphs can be solved in polynomial time for any undirected graph F. It follows from the Robertson and Seymour algorithm [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF] that solves in polynomial time the undirected linkage problem, which is the following.

UNDIRECTED k-LINKAGE

Input: A graph G and 2k distinct vertices x 1 , . . . , x k , y 1 , . . . , y k . Question: Is there a k-linkage from (x 1 , . . . , x k ) to (y 1 , . . . , y k ) in G?

However, for digraphs, Fortune, Hopcropt and Wyllie [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF] showed that the following k-LINKAGE problem is NP-complete for all k ≥ 2.

k-LINKAGE

Input: A digraph D and 2k distinct vertices x 1 , . . . , x k , y 1 , . . . , y k . Question: Is there a k-linkage from (x 1 , . . . , x k ) to (y 1 , . . . , y k ) in D?

Using reductions to this problem, Bang-Jensen et al. [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF] found many digraphs F for which F -SUBDIVISION is NP-complete. It is in particular the case of every digraph in which every vertex v is big (that is such that either d + (v) ≥ 3, or d -(v) ≥ 3, or d + (v) = d -(v) = 2). On the other hand, they gave polynomial-time algorithms to solve the problem for many others digraphs. This leads them to conjecturing that there is a sharp dichotomy between NP-complete and polynomial-time solvable instances. According to this conjecture, there are only two kinds of digraphs F: the hard ones, for which F-Subdivision is NP-complete, and the tractable ones, for which it is polynomial-time solvable. However there is no very clear picture of which graphs should be tractable and which ones should be hard, although some conjectures give some outline. Motivated by directed treewidth and a conjecture of Johnson et al. [START_REF] Johnson | Directed tree-width[END_REF], Seymour (see [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF]) posed the following conjecture.

Conjecture 1 (Seymour). If F is a planar digraph with no big vertices, then F-SUBDIVISION is polynomialtime solvable.

Bang-Jensen et al. [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF] proposed the following sort of counterpart conjecture.

Conjecture 2 (Bang-Jensen et al. [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF]). F-Subdivision is NP-complete for every non-planar digraph F.

As an evidence to Conjecture 1, Havet et al. [START_REF] Havet | Finding a subdivision of a prescribed digraph of order 4[END_REF] proved it when F has order at most 4. Bang-Jensen et al. [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF] also proved that every directed cycle is tractable. In this paper, we are interested in the case when F is the disjoint union of directed cycles. Conjecture 1 restricted to this particular case is the following.

Conjecture 3. If F is a disjoint union of directed cycles, then F-SUBDIVISION is polynomial-time solv- able.
Observe that if F is the disjoint union of n directed cycles of lengths 1 , . . . , n , then a subdivision of F is the disjoint union of n directed cycles C 1 , . . . ,C n , each C i being of length at least i . We denote the directed cycle of length , or directed -cycle, by C . A directed cycle of length at least is called directed + -cycle.

A particular case of Conjecture 3 is when all the directed cycles of F have the same length.

Conjecture 4. For any two positive integers n and with ≥ 2, n C -SUBDIVISION is polynomial-time solvable.

In fact, we show in Subsection 2.1 that Conjectures 3 and 4 are equivalent.

An n C 2 -subdivision is the disjoint union of n directed cycles. Therefore Conjecture 4 for = 2 can be deduced (See Theorem 13) from the following two theorems.

Theorem 5 (Fortune, Hopcroft and Wyllie [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF]). For each fixed k, the k-LINKAGE problem is polynomialtime solvable for acyclic digraphs.

Theorem 6 (Reed et al. [START_REF] Reed | Packing directed circuits[END_REF]). For every integer n ≥ 0, there exists an integer t n such that for every digraph D, either D has a n pairwise-disjoint directed cycles, or there exists a set T of at most t n vertices such that D -T is acyclic.

Theorem 6 is a directed analogue of the following theorem due to Erdös and Pósa.

Theorem 7 (Erdős and Pósa [START_REF] Erdős | On the independent circuits contained in a graph[END_REF]). Let n be a positive integer. There exists t * n such that for every graph G, either G has n pairwise-disjoint cycles, or there exists a set T of at most t * n vertices such that G -T is acyclic.

More precisely Erdős and Pósa [START_REF] Erdős | On the independent circuits contained in a graph[END_REF] proved that there exist two absolute constants c 1 and c 2 such that

c 1 • n log n ≤ t * n ≤ c 2 • n log n.
We believe that a similar approach may be used to prove Conjecture 4 for all . We show in Section 2.2 that Conjecture 4 for some is implied by the two following conjectures for the same .

The circumference of a non-acyclic digraph D, denoted circ(D), is the length of a longest directed cycle in D. If D is acyclic, then its circumference is defined by circ(D) = 1.

Conjecture 8. Let ≥ 2 be an integer. For any positive integer k, k-LINKAGE is polynomial-time solvable for digraphs with circumference at most -1?

This conjecture already appears as a problem in [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF]. Conjecture 9. Let ≥ 2 be an integer. For every integer n ≥ 0, there exists an integer t n = t n ( ) such that for every digraph D, either D has a n pairwise-disjoint directed + -cycles, or there exists a set T of at most t n vertices such that D -T is no directed + -cycles.

The main results of this paper (Theorems 14 and 16) prove both Conjecture 8 and Conjecture 9 for = 3. By virtue of Theorem 13 they imply the following. Inria Theorem 10. For any positive integer n, n C 3 -SUBDIVISION is polynomial-time solvable.

Combined with Lemma 12, this result in turn implies the following.

Corollary 11. If F is the disjoint union of cycles of length at most 3, then F-SUBDIVISION is polynomialtime solvable.

Reducing to Conjectures 8 and 9

For a digraph D and an integer ≥ 2, we denote by ν (D) the maximum n such that D has n disjoint directed cycles of length at least , and by τ (D) the minimum t such that there exists T ⊆ V (D) with |T | = t meeting all directed cycles of length at least . Evidently ν (D) ≤ τ (D) and Conjecture 9 states that for every fixed there exists a function f such that τ (D) ≤ f (ν (D)).

Equivalence of Conjectures 3 and 4

Conjecture 4 is a particular case of Conjecture 3. We now show how Conjecture 3 can be deduced from Conjecture 4.

Lemma 12. Let F be a disjoint union of n directed cycles, all of length at most . If m C -SUBDIVISION is polynomial-time solvable for all 1 ≤ m ≤ n, then F-SUBDIVISION is also polynomial-time solvable.

Proof. Let n be a positive integer. Assume that m C -SUBDIVISION is polynomial-time solvable for any m ≤ n.

Let

F = C 1 + • • • + C n with 1 ≤ • • • ≤ n ≤ . Any F-subdivision is a disjoint union of n directed cycles C p 1 + • • • + C p n with p 1 ≤ • • • ≤ p n such that i ≤ p i for all 1 ≤ i ≤ n.
The threshold of such a subdivision is the largest integer t such that p t < .

For t = 0 to n, we check whether there is an F-subdivision with threshold t with the following 'brute force' procedure. We enumerate all possible disjoint unions of directed cycles

U = C p 1 + • • • + C p t with p 1 ≤ • • • ≤ p t ≤ -1 and i ≤ p i for all 1 ≤ i ≤ t.
There are at most O |V (D)| (t-1)( -1) such U. For each such U, we check if D -U contains an (nt) C -subdivision (whose union with U would be an F-subdivision with threshold t). This can be done in polynomial time by the hypothesis.

The algorithm is a succession of (at most) n + 1 polynomial-time procedures, so it runs in polynomial time.

Conjectures 8 and 9 imply Conjecture 4

Theorem 13. Let ≥ 1 be an integer. If Conjectures 8 and 9 hold for , then for every positive integer n, n C -SUBDIVISION is polynomial-time solvable.

Proof. Let D be a digraph. Let t = t n ( ) with t n ( ) as in Conjecture 9. We first check if τ (D) ≤ t. This can be done by brute force, testing for each subset T of V (D) of size t whether it meets all directed + -cycles. Such a test can be done by checking whether D -T has circumference -1, that is, has no Csubdivision. Since there are O(|V (D)| t ) sets of size t, and C -SUBDIVISION is polynomial-time solvable, this can be done in polynomial time.

If no t-subset T meets all directed + -cycles, then τ (D) > t. Therefore, because Conjecture 9 holds for , D contains an n C -subdivision. So we return 'yes'.

If we find a set T of size t that meets all directed + -cycles, then circ(D -T ) ≤ -1. We use another brute force algorithm which is based on traces.

A trace is either a directed + -cycle or a linkage. Observe that for any directed + -cycle C and any subset

Z of V (D), the intersection C ∩ D[Z] is a trace. A trace contained in D[Z] is called a Z-trace.
Now every + -cycle intersects T in a non-empty trace because circ(D -T ) ≤ -1. We describe a polynomial-time procedure that, given a set of n pairwise disjoint traces T 1 . . . , T n , checks whether there is an n C -subdivision

C 1 + • • • + C n such that T i = C i ∩ D[T ] for all 1 ≤ i ≤ n. Now since T has size t,
there is a bounded number of possible sets of n pairwise disjoint traces T -traces (at most t n+1 (B t + 1), where B t is the is the number of partitions of a set of size t). Hence running the above procedure for all possible such set of T -traces, we obtain a polynomial-time algorithm that decides whether D contains an n C -subdivision.

Let T = {T 1 , . . . , T n } be a set of n pairwise disjoint T -traces. Set T = V (D) \ T . A trace is suitable if
it has at least vertices, at most t components, and the initial and terminal vertices of all components are in T .

For each T i , we shall describe a set T i of suitable traces such that a directed + -cycle C such that C ∩ T = T i contains at least one trace in T i . The set T i is constructed as follows. Let U i be the set of traces that can be obtained from T i by extending each components P of T i at both ends by an inneighbour of s(P) and an outneighbour of t(P) in T . Clearly, U i has size at most |V (D)| 2 k, where k is the number of components of T i . By construction, each trace of U i has its initial and terminal vertices in T and has no more components than T i . Moreover, a directed + -cycle C such that C ∩ T = T i contains one trace in U i . However, the set U i might not be our set T i because certain traces in it might be to small. For any trace U, let g(U) be set set of all possibles traces obtained from U by adding one vertex of T has outneighbour of a terminal vertex of one component of U. Clearly, g(U) has size at most k|V (D)|, where k is the number of components of U, and a directed + -cycle C containing U must contains a trace in g(U). Moreover, every trace of g(U) has size |V (U)| + 1, and no more components than U. Set g i (U) = {U} if i is a non-positive integer and for all positive integer i, define

g i (U) = U ∈g i-1 (U) g(U ). Now the set U∈U i g -|V (U)| (U) is our desired T i . Moreover, T i is of size at most t t • |V (D)| t .
To have a polynomial-time procedure to decide whether there is an n C -subdivision

C 1 + • • • + C n such that T i = C i ∩ T for all 1 ≤ i ≤ n, it
suffices to have a procedure that, given an n-tuple (T 1 , . . . , T n ) of disjoint traces such that T i ∈ T i , decides whether there is an n C -subdivision C 1 + • • • +C n such that T i is a subdigraph of C i for all 1 ≤ i ≤ n, and to run it on each possible such n-tuple. Such a procedure can be done as follows. Let P i 1 , . . . , P i k i be the components of T i . For each n-tuple of circular permutations

(σ 1 , . . . , σ n ) of S k 1 × • • • × S k n ,
one checks whether in the digraph D induced by the vertices of T which are not internal vertices of any of the components of the union of the T i , if there is a linkage from s(P 1 1 ), . . . , s(P 1 k 1 ), s(P 2 1 ), . . . , s(P 2 k 2 ), . . . , s(P n 1 ), . . . , s(P n k n ) to t(P 1 σ 1 (1) ), . . . ,t(P 1 σ 1 (k 1 ) ),t(P 2 σ 2 (1) ), . . . ,t(P 2 σ 2 (k 2 ) ), . . . ,t(P n σ n (1) ), . . . ,t(P n σ n (k n ) ) .

Now the digraph D is a subdigraph of D -T and so has circumference at most -1, and the linkage we are looking for has at most t components. Thus each of these instances of (k

1 + • • • + k n )-LINKAGE can be solved in time O(|V (D)| m )
for some absolute constant m because Conjecture 8 holds for .

3 Linkage in digraphs with circumference at most 2

The aim of this section is to prove the following theorem.

Theorem 14. For each fixed k, the k-LINKAGE problem is polynomial-time solvable for digraphs with circumference at most 2.

Inria

We first prove the following lemma. It is well-known that D/ ∼ is an acyclic digraph, therefore there is an ordering S 1 , . . . , S p of the strong components such that there is no arc S j S j in D/ ∼ with j > j . This implies that for every j > j , there is no directed (x, y)-path in D with x ∈ S j and y in S j .

Let D be the digraph D \ p j=1 A(S j ), the digraph whose arcs are those between non-equivalent vertices with respect to ∼.

Form a new digraph D whose vertices are the k-tuples v = (v 1 , . . . , v k ) of distinct vertices of D. For any such k-tuple v, there is a minimum index m such that S m intersects {v 1 , . . . ,

v k }. Let I = {i | v i ∈ S m }. Set I = {i 1 , . . . , i k } with i 1 < i 2 < • • • < i k .
For each k -tuple (w 1 , w 2 , . . . , w k ) of distinct vertices of V (D) \ {v 1 , v 2 , . . . , v k } such that there exists a k -tuple (u 1 , u 2 , . . . , u k ) of vertices in V (S m ) such that there is a linkage from (v i 1 , v i 2 , . . . , v i k ) to (u 1 , u 2 , . . . , u k ) in S m and u j w j is an arc in D for all 1 ≤ j ≤ k , we put an arc from v to the k-tuple obtained from it by replacing v i by w i for all i ∈ I. We say that such an arc in D is labelled by S m .

Observe that there are O(n k ) k -tuples (u 1 , u 2 , . . . , u k ) of V (S m ), and for each of them one can decide in polynomial time whether there is a linkage from We now prove that for any two sets of k distinct vertices {x 1 , . . . , x k } and {y 1 , . . . , y k }, there is a klinkage from (x 1 , . . . , x k ) to (y 1 , . . . , y k ) if and only if there is a directed path from (x 1 , . . . , x k ) to (y 1 , . . . , y k ) in D.

(v i 1 , v i 2 , . . . , v i k ) to (u 1 , u 2 , . . . , u k ) because k - LINKAGE is
Suppose first that there is a k-linkage (P 1 , . . . , P k ) from (x 1 , . . . , x k ) to (y 1 , . . . , y k ). Since, when j > j , there are no directed (x, y)-paths in D with x ∈ S j and y in S j , each P i goes through the strong components S 1 , . . . , S p in that order, possibly avoiding some. For each 1 ≤ m ≤ p and each 1 ≤ i ≤ k, let v i (m) the first vertex in p j=m S j along P i if p j=m S j and P i intersect, and v i (m) = y i otherwise.

Let M = {m 1 , . . . , m r } with m 1 ≤ m 2 ≤ • • • ≤ m r , be the set of indices m such that S m ∩ k i=1 P i = / 0. By definition of D, v(m q )v(m q+1 ) is an arc in D. Thus v(m 1 )v(m 2 ) . . . v(m r ) is a directed path from (x 1 , x 2 , . . . , x k ) to (y 1 , y 2 , . . . , y k ) in D.
Suppose now that D has a directed path Q from (x 1 , . . . , x k ) to (y 1 , . . . , y k ) in D. We construct directed walks P i , 1 ≤ i ≤ k, by the following procedure. At the beginning P i = (x i ) for all 1 ≤ i ≤ k. For each arc a = vw of Q one after another from the initial vertex to the terminal vertex of Q, we do the following.

Let I = {i 1 , . . . , i k } be set of indices i such that v i = w i . By definition of D, there is a strong component S of D, a k -tuple (u 1 , . . . , u k ) of disjoint vertices of S, and such that there is a linkage (R 1 , . . . , R k ) from (v i 1 , v i 2 , . . . , v i k ) to (u 1 , u 2 , . . . , u k ) in S and u j w i j ∈ A( D) for all 1 ≤ j ≤ k . In that case, we extend each P i j , 1 ≤ j ≤ r, by appending R j u j w i j at the end of it. Observe that R j might be a path reduced to the single vertex v i j = u j .

Observe that in D an arc labelled by a strong component S m enters a k-tuple of vertices that all belong to components S j with j > m. In particular, Q contains at most one arc labelled with any strong component S m . This implies that each P i is a directed (x i , y i )-path. Combined with the fact that each (R 1 , . . . , R k ) as defined above is a linkage, it implies that the P i are disjoint.

(iii) every directed 3 + -cycle of L 1 ∪ L 2 meets {a 1 , . . . , a k , b 1 , . . . , b k }.
However, for our purpose we need an extra condition on the two linkages L 1 and L 2 . This is in fact why we needed a stronger statement thanLemma 18.. Lemma 19. Let n ≥ 1 be an integer such that t n-1 exists, and let k be an even integer. Then there exists an integer t(k) such that the following holds. Let D be a digraph with ν 3 (D) < n, and τ 3 (D) ≥ t(k), and let T be a set of size τ 3 (D) such that D -T has no directed 3 + -cycles. Then there are distinct vertices a 1 , . . . , a k , b 1 , . . . , b k in T , and two k-linkages L 1 , L 2 of D so that

(i) L 1 links (a 1 , . . . , a k ) to (b 1 , . . . , b k ), (ii) L 2 links (b 1 , . . . , b k ) to one of (a 1 , . . . , a k ), (a k , . . . , a 1 ), (iii) every directed 3 + -cycle of L 1 ∪ L 2 meets {a 1 , . . . , a k , b 1 , . . . , b k }, (iv) no component of L 1 is the converse of a component of L 2 .
To prove this lemma, we will need Erdő-Pósa Theorem (Theorem 7) and the following lemma.

Lemma 20. Let r be a positive integer. Let T be a tree and S a set of at least 3r -2 vertices of T . Then there exists a vertex x of T and two subsets A and B of S, both of size r such that every (A, B)-path in T goes through x.

Proof. Let E r be the set of edges e such that both components of T \ e have at least r vertices of S. We divide the proof in two cases depending on whether or not E r is empty.

Assume first that E r = / 0. Let e = xy be an edge of E r , and let T x be the component of T \ e containing x and T y containing y. Both T x and T y contain at least r vertices of S. Let A (resp. B) be a set of r vertices of S ∩V (T x ) (resp. S ∩V (T y )). Then every (A, B)-path in T goes through e and so through x.

Assume now that E r = / 0.

Claim 20.1. There exists a vertex x such that all components of Tx have less than r vertices of S.

Subproof. Let us orient the edges of T as follows. Let e = uv be an edge of T . Since e / ∈ E r is empty, exactly one component of T \ e contains less than r vertices of S. Without loss of generality, this component is the one containing v. Orient the edge e from u to v. Now every orientation of a tree contains a vertex x with outdegree 0. Consider a component C of Tx. It contains exactly one neighbour y of x, and it is precisely the component of T \ xy containing y. Thus |C ∩ S| < r because the edge is oriented from x to y. Hence all components of Tx have less than r vertices. ♦ Take a vertex x as in the above claim. Let C 1 , . . . ,C m be the components of Tx. Then |C j | ≤ r -1 for all 1 ≤ j ≤ m. Let i be the smallest integer such that T i = i j=1 C j contains at least r vertices of S. Clearly, T i contains at most 2r -2 vertices in S, and thus there are least r vertices in T -T i . Let A (resp. B) be a set of r vertices in T i (resp. T -T i ). Then x is in every (A, B)-path.

Remark 21. The bound 3r -2 in the above lemma is tight. Indeed consider a tree T with a set S of 3r -3 leaves and four other vertices x, y 1 , y 2 and y 3 such that for every i ∈ {1, 2, 3}, y i is adjacent to x and r -1 leaves. One can check that for every vertex x and two sets A and B of r leaves there is an (A, B)-path avoiding x.

Proof of Lemma 19. Let t * n be as in Erdő-Pósa Theorem (Theorem 7); let r = k + 2t * n + 2; let t(k) = max{3r -2 + t * n , 2t (r)}, let where t is as in Lemma 18. We claim that t(k) satisfies the lemma. Let G 2 be the undirected graph with vertex set V (D) in which two vertices x and y are adjacent if and only if D[{x, y}] is a directed 2-cycle. To each cycle in G 2 correspond two directed cycles in D, one in each direction. Thus G 2 has less than n disjoint cycles. Hence by Erdő-Pósa Theorem, there is a set

U ⊂ V (D) of size t * n such that G 2 -U is acyclic. Choose T ⊆ V (D) with |T | = τ 3 (D), meeting all directed 3 + -cycles of D. Since t(k) ≥ 3r -2 + t *
n , there is a set S of size 3r -2 in T \U. Since G 2 -U is acyclic, we can extend it into a tree T 2 . Hence, by Lemma 20, there exists a vertex x in V (T 2 ) and two sets A and B in S of size r such that every (A, B)-path in T 2 goes through x. Since G 2 -U is a subgraph of T 2 , every (A, B)-path in G 2 -U goes through x.

Since For 1 ≤ i ≤ k , let P i be the component of L 1 with initial vertex a i and Q i the component of L 2 with initial vertex b i .

Clearly, if L 2 links (b 1 , . . . , b k ) to (a k , . . . , a 1 ), then condition (iv) is also verified by L 1 and L 2 , because k is even as k is even. For 1

≤ i ≤ k, set a i = a i+(k -k)/2 and b i = b i+(k -k)/2 , and let L 1 = {P j | 1+ k /2 -k/2 ≤ j ≤ k /2 + k/2} and L 2 = {Q j | 1 + k /2 -k/2 ≤ j ≤ k /2 + k/2}. Then a 1 , . . . , a k , b 1 , . . . , b k , L 1
and L 2 satisfy the lemma.

Assume now that L 2 links (b 1 , . . . , b k ) to one of (a 1 , . . . , a k ). At most t * n of the P i intersect U and at most t * n of the Q i intersect U. Thus, since k ≥ k + 2t * n + 1, there are at least k + 1 indices i such that both P i and Q i do not intersect U. Without loss of generality, we may assume that these indices are {1, . . . , k + 1}. Now for 1 ≤ i ≤ k + 1, if P i is the converse of Q i , then P i is also a path in G 2 -U and thus it must go through x. Hence there is at most one index i, say k + 1, such that P i is the converse of Q i . Hence a 1 , . . . , a k , b 1 , . . . , b k , L 1 and L 2 satisfy the lemma.

We say a digraph is divalent if every vertex has indegree 2 and outdegree 2, or indegree 1 and outdegree 1. In Subsection 4.2 we shall prove the following lemma which is the analogue of Lemma (2.3) of [START_REF] Reed | Packing directed circuits[END_REF].

A pair {L 1 , L 2 } of linkages is fully intersecting if each component of L 1 meets each component of L 2 , and it is acyclic if L 1 ∪ L 2 has no directed cycles, Lemma 22. For every positive integer n, there exists a positive integer k 1 such that for every divalent digraph D, if there is a fully intersecting and acyclic pair of k 1 -linkages in D then ν 3 (D) ≥ n.

Lemma 22 is proved in Subsection 4.2. We assume it for the moment. We will show how to combine it with Lemma 19 to prove Theorem 16. First we prove the following lemma, which is the analogue of Lemma (2.4) of [START_REF] Reed | Packing directed circuits[END_REF].

Lemma 23. For every non-negative integer n, there exists a positive integer k so that the following holds. Let D be a digraph, and let a 1 . . . , a k , b 1 , . . . , b k be distinct vertices of D. Let L 1 , L 2 be linkages in D linking (a 1 , . . . , a k ) to (b 1 , . . . , b k ), and (b 1 , . . . , b k ) to one of (a 1 , . . . , a k ), (a k , . . . , a 1 ), respectively, such that no component of L 2 is the converse of L 1 . Let every directed 3

+ -cycle of L 1 ∪ L 2 meet {a 1 , . . . , a k , b 1 , . . . , b k }. Then ν 3 (D) ≥ n.

Inria

The proof of this lemma is similar to the one of Lemma (2.4) of [START_REF] Reed | Packing directed circuits[END_REF]. However, some extra technical details are required. When reducing to a divalent digraph, we also have to get rid of directed 2-cycles, and Claim 24.1 is now required.

As in [START_REF] Reed | Packing directed circuits[END_REF], we shall also need Ramsey's theorem [START_REF] Ramsey | On a problem of formal logic[END_REF], which can be stated as follows.

Theorem 24 (Ramsey [START_REF] Ramsey | On a problem of formal logic[END_REF]). For all positive integers q, l, r, there exists a (minimum) integer R l (r; q) so that the following holds. Let Z be a set with |Z| ≥ R l (r; q), let Q be a set with |Q| = q, and for each X ⊂ Z with |X| = l let f (X) ∈ Q. Then there exists S ⊆ Z with |S| = r and there exists x ∈ Q so that f (X) = x for all X ⊆ S with |X| = l.

= P i ∪ P k+1-i ∪ Q i ∪ Q k+1-i . We show by induction on |E(D)| + |V (D)| that ν 3 (D) ≥ n. If L 1 ∪ L 2 = D,
then the result follows immediately by induction, so we may assume that L 1 ∪ L 2 = D.

Assume that either the arc e = uv belongs to P i ∩ Q j , or the arc uv is in P i and the arc vu is in Q j , then consider the graph D and the two linkages L 1 and L 2 obtained by contracting uv. These two linkages clearly satisfy the hypothesis of Lemma 23 since directed cycles can only be shorten while contracting.

We therefore may assume that every arc of D belongs to exactly one of L 1 , L 2 , and that D has no directed 2-cycles. In particular, D is divalent and every directed cycle of D meets {a 1 , . . . , a k , b 1 , . . . , b k }.

For 1 ≤ i ≤ k, let P i be the component of L 1 with initial vertex a i , and let Q i be the component of L 2 with initial vertex b i .

For 1 ≤ h < i ≤ k/2, define f ({h, i}) as follows. If G i and G h are disjoint, let f ({h, i}) = 0. Otherwise, at least one of the eight digraphs P i ∩ Q h , P k+1-i ∩ Q h , P i ∩ Q k+1-h , P k+1-i ∩ Q k+1-h , Q i ∩ P h , Q k+1-i ∩ P h , Q i ∩ P k+1-h , Q k+1-i ∩ P k+1-h is non-null. Number them 1, . . . , 8 in order; we define f ({h, i}) ∈ {0, 1, . . . , 8}.

Since k = 2R 2 (4k ; 9), by Theorem 24, there exists S ⊆ {1, . . . , 1 2 k} with |S| = 4k and x with 0 ≤ x ≤ 8 such that f ({h, i}) = x for all h, i ∈ S with h < i.

If x = 0, then the subdigraphs G i are pairwise disjoint for all i ∈ S. But as we shall prove in Claim 24.1, each G i contains a directed 3 + -cycle, and so ν 3 (D) ≥ |S| = 4k ≥ n.

Claim 24.1. Each G i contains a directed 3 + -cycle.

Subproof. If Q i is a directed (b i , a i )-path, then by assumption Q i is not the converse of P i . Thus by Lemma 17 P i ∪ Q i contains a directed 3 + -cycle, and so G i also does.

Assume now that Q i is a directed (b i , a k+1-i )-path, and so Q k+1-i is a directed (b k+1-i , a i )-path. Q i contains a directed path R 1 with initial vertex u 1 in P i and terminal vertex v 1 in P k+1-i whose internal vertices are not in P i ∪ P k+1-i . Now Q k+1-i contains a directed path R 2 with initial vertex u 2 in P k+1-i [v 1 , b k+1-i ] and terminal vertex v 2 in P i [a 1 , u 1 ] whose internal vertices are not in P i ∪ P k+1-i . Observe that u 1 , u 2 , v 1 and v 2 are all distinct because P i and P k+1-i are disjoint and Q i and Q k+1-i are disjoint. Hence the

R 1 ∪ P k+1-i [v 1 , u 2 ] ∪ R 2 ∪ P i [v 2 , u 1 ] is a directed 4 + -cycle in G i .
♦

Assume now that x = 1. Let S = I ∪ J, where |I| = k , |J| = 3k and i < j for all i ∈ I and j ∈ J. Then for all i ∈ I and all j ∈ J, P i meets Q j . There are 2k vertices that are endvertices of paths P i , i ∈ I, an each of them is an endvertex of at most one Q j , j ∈ J. Since |J| ≥ 3k , there exists J ⊂ J with |J | = k so that P i and Q j have no common endvertex for i ∈ I and j ∈ J . Let L 1 be the union of the components P i , i ∈ I and L 2 be the union of the components Q j , j ∈ J . Now every directed cycle in L 1 ∪ L 2 meets {a 1 . . . , a k , b 1 , . . . , b k }, and each of a 1 . . . , a k , b 1 , . . . , b k is incident with at most one arc of L 1 ∪ L 2 since P i and Q j have no common endvertex for i ∈ I and j ∈ J . Hence L 1 ∪ L 2 has no directed cycles. We thus have the result by Lemma 22.

Lemma 15 .

 15 Let D be a class of digraphs and S be the class of strong digraphs. If k -LINKAGE is polynomial-time solvable on D ∩ S for any k ≤ k, then k-LINKAGE is polynomial-time solvable on D. Proof. Let D be a digraph in D. Let ∼ be the relation defined on V (D) by u ∼ v if and only if u and v are in the same strong component. It is clearly an equivalence relation on V (D) with equivalence classes the strong components of D. Let D/ ∼ be the quotient of D by ∼, that is the digraph whose vertices are the strong components of D, and in which there is an arc from a strong component S to another S if and only if there is an arc of D with tail in S and head in S . One can also see D/ ∼ as the digraph obtained by contracting each strong component into a vertex.

  polynomial-time solvable on D by hypothesis. Hence in polynomial time, we can construct the digraph D which has polynomial size.

  |T | ≥ 2t (r), by Lemma 18, there are distinct vertices a 1 , . . . , a k in A and distinct vertices b 1 , . . . , b k in B, and two k -linkages L 1 , L 2 of D so that (i) L 1 links (a 1 , . . . , a k ) to (b 1 , . . . , b k ), (ii) L 2 links (b 1 , . . . , b k ) to one of (a 1 , . . . , a k ), (a k , . . . , a 1 ), (iii) every directed 3 + -cycle of L 1 ∪ L 2 meets {a 1 , . . . , a k , b 1 , . . . , b k }.

  Proof of Lemma 23, assuming Lemma 22. Let n ≥ 1. Let k = max{k 1 , n/4 } with k 1 as in Lemma 22. Let k = 2R 2 (4k ; 9) defined as in Theorem 24. We claim that n and k satisfy Lemma 23. For let a 1 . . . , a k , b 1 , . . . , b k , L 1 , L 2 be as in the statement of Lemma 23. Let G i

RR n°8286

InriaRESEARCH CENTRE SOPHIA ANTIPOLIS -MÉDITERRANÉE 2004 route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

We can easily derive Theorem 14 from Lemma 15.

Proof of Theorem 14. Let C 2 be the class of digraphs with circumference at most 2. A strong digraph D in C 2 is obtained from a tree T by replacing every edge by a directed 2-cycle. Hence there is a k-linkage from (x 1 , . . . , x k ) to (y 1 , . . . , y k ) in D if and only if there is a k-linkage from (x 1 , . . . , x k ) to (y 1 , . . . , y k ) in T . Since UNDIRECTED k-LINKAGE is polynomial-time solvable, it follows that k-LINKAGE is polynomialtime solvable on C 2 ∩ S. Thus, by Lemma 15, it is polynomial-time solvable on C 2 .

Packing directed 3 + -cycles

The aim of this section is to prove by induction on n the following theorem.

Theorem 16. For every integer n ≥ 0, there exists an integer t n such that for every digraph D, either

Our proof follows the same approach as the one used by Reed et al. [START_REF] Reed | Packing directed circuits[END_REF] to prove Theorem 6. A key ingredient in their proof is that if P is a directed (a, b)-path and Q is a directed (b, a)-path, then P ∪ Q contains a directed cycle. However, in such a case, P ∪ Q does not necessarily contain a 3 + -cycle. However, P ∪ Q does not contain a 3 + -cycle if and only if Q is the converse of P. The converse of a directed path P = (x 1 , . . . , x m ) is the directed path (x m , . . . , x 1 ).

Lemma 17. Let a and b two distinct vertices, and let P be a directed (a, b)-path and Q be a directed (b, a)-path. Then P ∪ Q contains a directed 3 + -cycle if and only if Q is not the converse of P.

Proof. Clearly, if Q is the converse of P, then P ∪ Q contains no directed 3 + -cycle.

Conversely, we prove by induction on the length m of P that if Q is not the converse of P, then P ∪ Q contains a directed 3 + -cycle. It holds trivially if m = 1. So we may assume that m ≥ 1. Let P = (x 0 , x 1 , . . . , x m ). Let y be the penultimate vertex of Q. If y = x 1 , then Qx 0 is not the converse of Px 0 . Hence, by the induction hypothesis, there is a directed 3 + -cycle in (Px 0 ) ∪ (Qx 0 ), and so in P ∪ Q. Assume now that y = x 1 , then let z be the penultimate vertex in

x 0 ] has length at least 2, and so

In the proof we will have to make sure that some directed paths are not converse of some others. We follow the lines of the proof of Reed et al. [START_REF] Reed | Packing directed circuits[END_REF] in order to emphasize the extra work required to deal with directed 3 + -cycle.

Main proof

First replacing 'directed cycle' by 'directed 3 + -cycle' in the proof of Theorem (2.2) of [START_REF] Reed | Packing directed circuits[END_REF], we obtain the following analogue of (2.2) of [START_REF] Reed | Packing directed circuits[END_REF].

Lemma 18. Let n ≥ 1 be an integer such that t n-1 exists, and let k be an integer. Then there exists an integer t (k) such that the following holds. Let D be a digraph with ν 3 (D) < n, and τ 3 (D) ≥ 2t (k), and let T be a set of size τ 3 (D) such that D -T has no directed 3 + -cycles. For any disjoint subsets A, B ⊆ T with |A| = |B| = k, there are distinct vertices a 1 , . . . , a k in A and distinct vertices b 1 , . . . , b k in B, and two k-linkages L 1 , L 2 of D, so that

(ii) L 2 links (b 1 , . . . , b k ) to one of (a 1 , . . . , a k ), (a k , . . . , a 1 ),

Inria

The cases 2 ≤ x ≤ 8 are similar to the case x = 1.

Proof of Theorem 16, assuming Lemma 22. We prove Theorem 16 by induction on n; we therefore assume that n ≥ 1 and t n-1 exists, and we show that t n exists. Let k be as in Lemma 23, and let t be as in Lemma 19. We claim that there is no digraph D with ν 3 (D) < n and τ 3 (D) ≥ t. For suppose that D is such a digraph. By Lemma 19, there exists a 1 . . . , a k , b 1 , . . . , b k and L 1 , L 2 as in Lemma 18, and so ν 3 (D) ≥ n by Lemma 23, a contradiction. Thus there is no such D, and consequently t n exists and t n < t.

Proving Lemma 22

In this section, following Section 3 of [START_REF] Reed | Packing directed circuits[END_REF], we show that if a digraph D contains a kind of grid, with some additional paths, then ν 3 (D) is large. We then use this lemma to prove Lemma 22.

Let p, q be positive integers. A (p, q)-web in a digraph D is a fully intersecting and acyclic pair (L 1 , L 2 ) of linkages such that L 1 has p components and L 2 has q components. Let p, q be positive integers. A (p, q)-fence in a digraph D is a sequence (P 1 , . . . , P 2p , Q 1 , . . . , Q q ) with the following properties:

(i) P 1 , . . . , P 2p are pairwise disjoint directed paths of D, and so are Q 1 , . . . , Q q ;

(ii) for 1 ≤ i ≤ 2p and 1 ≤ j ≤ q, P i ∩ Q j is a directed path (and therefore non-null);

(iii) for 1 ≤ j ≤ q, the directed paths P 1 ∩ Q j , . . . , P 2p ∩ Q j are in order in Q j , and the initial vertex of Q j is in V (P 1 ) and its terminal vertex is in V (P 2p );

(iv) for 1 ≤ i ≤ 2p, if i is odd then P i ∩ Q 1 , . . . , P i ∩ Q q are in order in P i , and if i is even then P i ∩ Q q , . . . , P i ∩ Q 1 are in order in P i .

Let Q j be a directed (a j , b j )-path (1 ≤ l ≤ q); we call {a 1 , . . . , a q } the top of the fence, and {b 1 , . . . , b q } its bottom.

The following lemma is the analogue to Lemma (3.1) of [START_REF] Reed | Packing directed circuits[END_REF]. It only differs in the conclusion ν 3 (D) ≥ n, instead of ν(D) ≥ n.

Lemma 25. For every positive integer n, there are positive integers p, r with the following property. For any q ≥ 2, let (P 1 , . . . , P 2p , Q 1 , . . . , Q q ) be a (p, q)-fence in a digraph D, and let there be r disjoint paths in D from the bottom of the fence to the top. Then ν 3 (D) ≥ n.

Combining Lemmas (4.4), (4.5) and (4.7) of [START_REF] Reed | Packing directed circuits[END_REF] we directly obtain the following lemma.

Lemma 26. For all positive integers p, q, there are positive integers p and q so that for every digraph G, if D contains a (p , q )-web then it contains a (p, q)-fence.

In exactly the same way that Reed et al. deduced Lemma (2.3) from Lemmas (3.1), (4.4), (4.5) and (4.7) in [START_REF] Reed | Packing directed circuits[END_REF], one can deduce Lemma 22 from Lemmas 25 and 26.

Hence it only remains to prove Lemma 25.

Proof Lemma 25

Consider the following lemma (Lemma (3.2)) from [START_REF] Reed | Packing directed circuits[END_REF].

Lemma 27 (Reed et al. [START_REF] Reed | Packing directed circuits[END_REF]). Let (P 1 , . . . , P 2p , Q 1 , . . . , Q q ) be a (p, q)-fence in a digraph D, with top A and bottom B. Let A ⊆ A and B ⊆ B with |A | = |B | = r, for r ≤ p. Then there are directed paths Q 1 , . . . , Q r in P 1 , . . . , P 2p , Q 1 , . . . , Q q so that (P 1 , . . . , P 2p , Q 1 , . . . , Q q ) is a (p, r)-fence with top A and bottom B .

Inria

Remark 28. In the proof of this lemma, the proven (p, r)-fence is a subgraph of the (p, q)-fence, with A ⊆ A and B ⊆ B. Moreover, if p ≥ 2, then Q j has order at least 4 for 1 ≤ j ≤ q, because Q j intersects every P i 1 ≤ i ≤ 2p. So, if p ≥ 2, Q l has size at least 4, for 1 ≤ l ≤ r.

We need also an analogue of Lemma (3.3) of [START_REF] Reed | Packing directed circuits[END_REF]:

Lemma 29. Let n ≥ 1 be an integer, and let p ≥ 2n and N ≥ 2n 2 -3n + 2 be integers. For some integer q ≥ 1 let (P 1 , . . . , P 2p , Q 1 , . . . , Q q ) be a (p, q)-fence in a digraph D. Let R 1 , . . . , R N be disjoint directed paths of D from the bottom of the fence to the top, so that each R k has no vertex or arc in P

The proof of this lemma is exactly the same as the one of Lemma (3.3) of [START_REF] Reed | Packing directed circuits[END_REF]. The disjoint directed cycles showed in the proof are of the form Q j R m , for Q j in a (p, r)-fence (P 1 , . . . , P 2p , Q 1 , . . . , Q q ), subgraph of the (p, q)-fence (P 1 , . . . , P 2p , Q 1 , . . . , Q q ). Since p ≥ 2n ≥ 2, by Remark 28 each Q j has length at least 2, and so Q j R m has length at least 3. Hence ν 3 (D) ≥ n.

We prove Lemma 25 by induction on n. The proof is almost identical to the one of Lemma (3.1) in [START_REF] Reed | Packing directed circuits[END_REF]. The only differences are the easy case n = 1, for which we need here to take p = 2 (instead of p = 1) to be sure that the directed cycle is of length at least 3, and the use in place of Lemma (3.3) of its analogue, namely Lemma 29.