Jørgen Bang-Jensen

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

A Karolinna Maia

Finding a subdivision of a digraph

We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.

Introduction

Many interesting classes of graphs are defined by forbidding induced subgraphs, see [START_REF] Chudnovsky | Excluding induced subgraphs[END_REF] for a survey. This is why the detection of several kinds of induced subgraphs is interesting, see [START_REF] Lévêque | Detecting induced subgraphs[END_REF] where several such problems are surveyed. In particular, the problem of deciding whether a graph G contains, as an induced subgraph, some graph obtained after possibly subdividing prescribed edges of a prescribed graph H has been studied. This problem can be polynomial-time solvable or NP-complete according to H and to the set of edges that can be subdivided. The aim of the present work is to investigate various similar problems in digraphs, focusing only on the following problem: given a digraph H, is there a polynomialtime algorithm to decide whether an input digraph G contains a subdivision of H?

Of course the answer depends heavily on what we mean by "contain". Let us illustrate this by surveying what happens in the realm of undirected graphs. If the containment relation is the subgraph containment, then for any fixed H, detecting a subdivision of H in an input graph G can be performed in polynomial time by the Robertson and Seymour linkage algorithm [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF] (for a short explanation of this see e.g. [START_REF] Bang-Jensen | Disjoint directed and undirected paths and cycles in digraphs[END_REF]). But, if we want to detect an induced subdivision of H, then the answer depends on H (assuming P̸ =NP). It is proved in [START_REF] Lévêque | Detecting induced subgraphs[END_REF] that detecting an induced subdivision of K 5 is NP-complete, and the argument can be reproduced for any H whose minimum degree is at least 4. Polynomial-time solvable instances trivially exist, such as detecting an induced subdivision of H when H is a path, or a graph on at most 3 vertices. But non-trivial polynomial-time solvable instances also exist, such as detecting an induced subdivision of K 2,3 which can be performed in O(n 11 ) time by Chudnovsky and Seymour's three-in-a-tree algorithm, see [START_REF] Chudnovsky | The three-in-a-tree problem[END_REF]. Note that for many graphs H, nothing is known about the complexity of detecting an induced subdivision of H: when H is cubic (in particular when H = K 4 ) or when H is a disjoint union of two triangles, and in many other cases.

To prove such a conjecture, a first idea would be to try to establish for any digraph G and subdigraph F, that if F-SUBDIVISION is NP-complete, then G-SUBDIVISION is also NP-complete, and conversely, if G-SUBDIVISION is polynomial-time solvable, then F-SUBDIVISION is polynomial-time solvable. However, these two statements are false as shown by the two digraphs depicted Figure 1. The NP-completeness of A-SUBDIVISION follows Theorem 12. The fact that B-SUBDIVISION is polynomial-time solvable is proved in Theorem 27.

v 2 A B u 1 v 1 v 2 u 2 u 1 v 1 u 2
Figure 1: Digraphs A and B such that A is a subdigraph of B, A-SUBDIVISION is NP-complete, and B-SUBDIVISION is polynomial-time solvable.

The paper is organized as follows. We start by giving some general lemmas which allow to extend NP-completeness results of F-SUBDIVISION for some digraphs F to much larger classes of digraphs. Next we give a powerful tool, based on a reduction from the NP-complete 2-linkage problem in digraphs, which can be applied to conclude the NPcompleteness of F-SUBDIVISION for the majority of all digraphs F. We then describe different algorithmic tools for proving polynomial-time solvability of certain instances of F-SUBDIVISION. We first give some easy brute force algorithms, then algorithms based on maximum-flow calculations and finally algorithms based on handle decompositions of strongly connected digraphs. After this we give a number of classes of digraphs for which the F-SUBDIVISION is polynomial-time solvable for every F. Then we treat F-SUBDIVISION when F belongs to some special classes of digraphs such as disjoint unions of cycles, wheels, fans, transitive tournaments, oriented paths or cycles or F has at most 3 vertices. Finally, we

conclude with some open problems, including an interesting conjecture due to Seymour, which if true would imply some of the polynomial cases treated in this paper.

Some general lemmas

Lemma 2. Let F 1 and F 2 be two digraphs.

(i) If F 1 -SUBDIVISION is NP-complete, then (F 1 + F 2 )-SUBDIVISION is NP-complete.

(ii) If (F 1 + F 2 )-SUBDIVISION is polynomial-time solvable, then F 1 -SUBDIVISION is polynomial-time solvable.

F 1 -subdivision and S 2 an F 2 -subdivision. Let us consider such an (F 1 + F 2 )-subdivision that maximizes the number of connected components 4 of F 2 that are mapped (in S) into F 2 again (notice that since there are no arcs between D and F 2 in D + F 2 , in the subdivision S every component of S 2 will either be entirely inside F 2 or entirely inside D). We claim that S 2 = F 2 .

Indeed suppose that some component T of S 2 is in D. Let C be the component of F 2 of which T is the subdivision. Let U = S ∩C. Then T contains a subdivision U ′ of U (because it is a subdivision of all of C). Hence replacing U by U ′ and T by C in S, we obtain a subdivision with one more component mapped on itself, a contradiction.

Hence S 2 = F 2 , and so D contains S 1 which is an F 1 -subdivision.

Lemma 3. Let F 1 and F 2 be two digraphs such that F 1 is strongly connected and F 2 contains no F 1 -subdivision. Let F be obtained from F 1 and F 2 by adding some arcs with tail in V (F 1 )

and head in V (F 2 ).

(i) If F 1 -SUBDIVISION is NP-complete, then F-SUBDIVISION is NP-complete.

(ii) If F-SUBDIVISION is polynomial-time solvable, then F 1 -SUBDIVISION is polynomialtime solvable.

Proof. We shall prove that a digraph D contains an F 1 -subdivision if and only if D → F 2 contains an F-subdivision, where D → F 2 is obtained from D + F 2 by adding all possible arcs from V (D) to V (F 2 ).

It is easy to see that if D contains an F 1 -subdivision S, then S + F 2 together with some subset of the arcs from D to F 2 is an F-subdivision in D → F 2 . Conversely, if D → F 2 contains an F subdivision S * , then, since F 1 is strongly connected, the part of S * forming a subdivision of F 1 has to lie entirely inside D or F 2 . Since F 2 contains no F 1 -subdivision, the subdivision of F 1 has to be inside D and hence we get that D has an F 1 -subdivision.

It is useful to look at Figure 1

+ (v), d -(v)} ≥ 2.
We believe that the condition max{d

+ (v), d -(v)} ≥ 2 for all v ∈ V (F) is not necessary,
although it is in our proof.

Conjecture 6. Let F be a digraph, and let S be a subdivision of F.

(i) If F-SUBDIVISION is NP-complete, then S-SUBDIVISION is NP-complete.
(ii) If S-SUBDIVISION is polynomial-time solvable, then F-SUBDIVISION is polynomialtime solvable.

General NP-completeness results

The tool

The following observations allow us to conclude that F-subdivision is "almost always" NP-complete. We use an easy modification of the 2-linkage problem as the basis for these proofs.

A vertex v is said to be small if d -(v) ≤ 2, d + (v) ≤ 2 and d(v) ≤ 3. A non-small vertex is called big.
Theorem 7. The 2-LINKAGE problem is NP-complete even when restricted to digraphs with no big vertices in which x 1 and x 2 are sources and y 1 and y 2 are sinks.

Proof. Reduction from 2-LINKAGE in general digraphs.

An out-arborescence is the orientation of a tree in which all vertices have in-degree 1 expect one special vertex, called the root. A switching out-arborescence is an out-arborescence, in which the root has out-degree 1, the leaves have out-degree 0 and all other vertices have out-degree 2. A switching in-arborescence is the dual notion to out-arborescence.

Let D be a digraph and x 1 , x 2 , y 1 , y 2 four vertices. Let D * be the digraph obtained from D by deleting all the arcs entering x 1 and x 2 and all the arcs leaving y 1 and y 2 . Let S(D) be the digraph obtained from D * as follows. For every vertex v, replace all the arcs leaving v by a switching out-arborescence with root v and whose leaves corresponds to the out-neighbours of v in D * , and replace all the arcs entering v by a switching in-arborescence with root v and whose leaves corresponds to the in-neighbours of v in D * . It is clear that S(D) has no big vertices and that x 1 and x 2 are sources and y 1 and y 2 are sinks. Furthermore, one checks easily that there is a 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ) in D if and only if there is a 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ) in S(D).

A general NP-completeness theorem

For a digraph D, we denote by B(D) the set of its big vertices. A big path in a digraph is a directed path whose endvertices are big and whose internal vertices all have in-and outdegree one in D (in particular an arc between two big vertices is a big path). Note also that two big paths with the same endvertices are necessarily internally disjoint.

The big paths digraph of D, denoted BP(D), is the multidigraph with vertex set V (D) in which there are as many arcs between two vertices u and v as there are big (u, v)-paths in D.

By the remark above BP(D) is well-defined and easy to construct in polynomial time given Clearly, if there is a 2-linkage P 1 , P 2 in D, then the union of F \ {ab, cd} and the paths

ax 1 P 1 y 1 b and cx 2 P 2 y 2 d is a F-subdivision in H.
Conversely, suppose that H contains an F-subdivision S. Observe that in H, no vertex of D is big. Hence, since S has as many big vertices as F, F and S have the same set of big vertices.

Clearly, S contains as many big paths as F and thus there must be in D two disjoint directed paths between (x 1 , x 2 ) and (y 1 , y 2 ). These two paths cannot be an (x For many digraphs F, the condition of Theorem 8 is verified and so F-SUBDIVISION is NP-complete. However, there are graphs F that do not verify this condition but for which F-SUBDIVISION is NP-complete as we shall prove in the following subsection.

Dumbbells

An oriented path is an orientation of an undirected path. Let P = (x 1 , • • • , x n ) be an oriented path. If x 1 x 2 is an arc, then P is an out-path, otherwise P is an in-path. In particular, if P is a directed path then it is an out-path. The blocks of P are the maximal directed subpaths of P. We often enumerate them from the origin to the terminus of the path. The number of blocks of P is denoted by b(P).

A dumbbell is a digraph D with exactly two big vertices u and v which are connected by an induced oriented (u, v)-path P such that removing the internal vertices of P leaves a digraph with two connected components, one L containing u and one R containing the terminus v. The subdigraph L (resp. R) is the left (resp. right) plate of the dumbbell, vertex u is its left clip, vertex v its right clip and P its bar.

A dumbbell set is a disjoint union of dumbbells. In this subsection, we shall give some necessary conditions for F-SUBDIVISION to be NP-complete, F being a dumbbell set. In Subsection 5.3, we give particular cases when F-SUBDIVISION is polynomial-time solvable.

A pair of oriented paths (P, Q) is a bad pair if one of the following holds:

• P and Q are both directed paths;

• {b(P), b(Q)} = {1, 2};

• P and Q are both out-paths and {b(P), b(Q)} ∈ {{2, 2}; {2, 4}};

• P and Q are both in-paths and {b(P), b(Q)} ∈ {{2, 2}; {2, 4}}.

Lemma 11. Let P and Q be two oriented paths. If (P, Q) is not a bad pair, then there exists ab ∈ A(P) and cd ∈ A(Q) such that the two oriented paths P ′ and Q ′ obtained from P and Q by replacing ab and cd by ad and cb verify

{b(P), b(Q)} ̸ = {b(P ′ ), b(Q ′ )}.
Proof. Let (P, Q) be a non-bad pair of paths. Without loss of generality, we may assume that b(Q) ≥ b(P). In particular this implies b(Q) ≥ 3.

Assume that P is an out-path (resp. in-path) and Q is an in-path (resp. out-path). If

′ )} = {2, b(Q) -1} ̸ = {b(P), b(Q)}.
So we may assume that P and Q are both out-paths or both in-paths. Observe that this in particular implies that P and Q have an even number of blocks, because the opposite path (same digraph but starting form the terminus and ending at the origin) of an out-path with an odd number of blocks is an in-path with an odd number of blocks.

Take an arc ab of the first block of P and an arc cd of the second block of Q. Then one of

P ′ , Q ′ has
(b) L 1 ̸ ∼ = L 2 , L 1 ̸ ∼ = R 2 , R 1 ̸ ∼ = L 2 and R 1 ̸ ∼ = R
̸ ∼ = L 2 or L 1 ̸ ∼ = R 2 (resp. R 1 ̸ ∼ = L 2 or R 1 ̸ ∼ = R 2 ).
then F-SUBDIVISION is NP-complete.

Proof. By Lemma 2, it is sufficient to prove it when Clearly, if there is a 2-linkage R 1 , R 2 in D, then the union of F \ {ab, cd} and the paths

F = D 1 + D 2 .
ax 1 R 1 y 1 b and cx 2 R 2 y 2 d is an F-subdivision in H.
Conversely, suppose that H contains an F-subdivision S. For each vertex x of F, we denote by x * the vertex corresponding to x in S and for any subdigraph G of F, we denote by G * the subdigraph of S corresponding to the subdivision of G.

In H, no vertex of D is big, so the sole big vertices of D are the clips of D 1 and D 2 .

Hence {u * 1 , v * 1 , u * 2 , v * 2 } = {u 1 , v 1 , u 2 , v 2 }
. Now in S, the paths P * 1 and P * 2 connect big vertices.

For connectivity reasons these two paths must use P 1 \ ab and P 2 \ cd. In particular, (L 1 +

L 2 + R 1 + R 2 ) * is a subdigraph of L 1 + L 2 + R 1 + R 2 . So (L 1 + L 2 + R 1 + R 2 ) * = L 1 + L 2 + R 1 + R 2 . So for any G ∈ {L 1 , L 2 , R 1 , R 2 }, the digraph G * is isomorphic to G and is one of the subdigraphs L 1 , L 2 , R 1 and R 2 .

Moreover b(P

* i ) = b(P i ) for i = 1, 2.
* 2 ) = b(P 2 ), there is a 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ) in D. (b) If L 1 ̸ ∼ = L 2 and L 1 ̸ ∼ = R 2 , then L * 1 ∈ {L 1 , R 1 }. Similarly, if R 1 ̸ ∼ = L 2 and R 1 ̸ ∼ = R 2 , then R * 1 ∈ {L 1 , R 1 }. Hence P * 1 must go from u 1 to v 1 , and so P * 1 ∩ D is a directed (x 1 , y 1 )- path.
Hence there is a 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ) in D.

(c) If P 1 and P 2 are both directed paths, then {u * 1 , u * 2 } = {u 1 , u 2 } as there are the origin of

P * 1 and P * 2 . Now, since L 1 ̸ ∼ = L 2 , we have L * 1 = L 1 and L * 2 = L 2 . Similarly, R * 1 = R 1 and R * 2 = R 2 . Hence, P * 1 ∩ D and P * 2 ∩ D form a 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ) in D.
(d) Assume that P 1 is a directed path and that P 2 is an out-path with two blocks. (The proof is analoguous when P 2 is an in-path with two blocks.)

Assume that L 1 ̸ ∼ = L 2 .
Then we can choose cd to be an arc of the first block of P 2 .

Necessarily,

v * 1 = v 1 and R * 1 = R 1 since v * 1 is the only clip with out-degree 0 in P * 1 ∪ P * 2 .
It follows that

L * 1 ∈ {L 1 , L 2 }, and so L * 1 = L 1 because L 1 ̸ ∼ = L 2 . Thus P * 1 ∩D is a directed (x 1 , y 1 )-path and there is a 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ) in D. If L 1 ̸ ∼ = R 2 ,
we get the result similarly by choosing cd to be an arc of the second block of P 2 .

Easy polynomial-time solvable F-subdivision problems

There are digraphs F for which F-SUBDIVISION can be easily proved to be polynomialtime solvable.

A spider is a tree obtained from disjoint directed paths by identifying one end of each path into a single vertex. This vertex is called the body of the spider.

Proposition 13. If F is the disjoint union of spiders, then F-SUBDIVISION can be solved in

O(n |V (F)| ) time. Proof. A digraph D contains an F-subdivision if and only if it contains F as a subdigraph.
This can be checked in

O(n |V (F)| ) time.
A natural question is to ask whether the problem remains polynomial-time solvable when the spider F is no more fixed but specified in the input. Then, if yes, we check if D -A has an F-subdivision.

Subdivision of directed cycles

We denote by C k the directed cycle of length k.

Proposition 16. For every k ≥ 2, C k -SUBDIVISION can be solved in time O(n k • m). Proof. For any k ≥ 2, for k-tuple (x 1 , x 2 , . . . , x k ), we check if (x 1 , x 2 , . . . , x k ) is a directed path and if yes if there is a directed (x k , x 1 )-path in D -{x 2 , . . . , x k-1 }. There are O(n k ) k-tuples, so this can be done in O(n k • m) time.
The running time above is certainly not best possible. For example, when k = 2 or k = 3, we can find linear-time algorithms.

( n |V (F)| (n + m)
) .

The complexity given in Proposition 21 is certainly not optimal. For example, it can be improved for spindles with paths of small lengths.

Proposition 22. If F is a (k 1 , . . . , k p )-spindle and k i ≤ 2 for all 1 ≤ i ≤ p, then F-SUBDIVISION can be solved in O(n 2 (n + m)) time.
Proof. If some of the k i , say k 1 , equals 1, then finding an F-subdivision is equivalent to find p internally disjoint directed paths from some vertex a to some other vertex b, which by Menger's theorem is equivalent to check that the connectivity from a and b is at least p. For any pair (a, b), this can be done in linear time by a Menger algorithm.

If k i = 2 for all 1 ≤ i ≤ 2,

Question: Does D contain a subdivision of F?

There are many other digraphs that can be solved in the same way as spindles using a Menger algorithm. It is in particular the case of any oriented tree T such that there is a vertex r of in-degree 0 such that Tr is the disjoint union of spiders. For such a tree, T -SUBDIVISION can be solved in O

( n |V (T )|-1 (n + m)
) time. The polynomial-time solvability of F-SUBDIVISION of some other digraphs may also be established by using a Menger algorithm in a slightly different way as we show in the next two subsections.

Subdivision of windmills

A cycle windmill is a digraph obtained from disjoint directed cycles by taking one vertex per cycle and identifying all of these. This vertex will be called the axis of the windmill.

Theorem 25. If W is a cycle windmill, then W -SUBDIVISION can be solved in O(n |V (W )| (n + m)) time.
Proof. Suppose W is a windmill with axis o and cycle lengths a 1 , a 2 , . . . , a p . To check whether a given digraph D = (V, A) contains a subdivision of W with axis at the vertex x we do the following (until success or all subsets have been tried): for all choices of dis-

joint ordered subsets X 1 , X 2 , . . . , X p of V such that X i = {v i,1 , . . . , v i,a i -1 }, i = 1, 2, . . . , p check whether Q i = xv i,1 v i,2 . . . v i,a i -1 is a directed (x, v i,a i -1
)-path. If this holds for all i, then delete all the vertices of X i -v i,a i -1 , i = 1, 2, . . . , p and check whether the resulting digraph contains internally disjoint paths P 1 , P 2 , . . . , P p where P i is a path from v i,a i -1 to x using a Menger algorithm. If these paths exist, then return the desired subdivision of W formed by the union of Question: Does D contain a subdivision of W ?

Q 1 , Q 2 , . . . , Q p , P 1 , P 2 , . . . , P p . Otherwise continue to the next choice for X 1 , X 2 , . . . , X p . Since the size of X 1 ∪ X 2 ∪ . . . ∪ X p is |V (W )| -1,

Subdivision of palm trees

A palm tree is a dumbbell, whose left and right plates are spiders, and whose bar is a directed path of length one. Observe that in a palm tree, the two clips must be the bodies of the spiders. A palm grove is a disjoint union of palm trees. For example, the two graphs A and B depicted Figure 1 are palm groves.

By Theorem 12(c), if F is a palm grove having two palm trees whose left spiders are not isomorphic and whose right spiders are not isomorphic, then F-SUBDIVISION is NPcomplete. We shall now prove that it is indeed the only hard case. Observe that if a digraph contains a subdivision of a palm tree, then it contains a subdivision of this palm tree such that the only subdivided arc is the bar.

Theorem 27. Let F be a palm grove. Then F-SUBDIVISION is polynomial-time solvable if and only if all its left spiders are isomorphic or all its right spiders are isomorphic.

Proof. If there are two left spiders that are not isomorphic and there are two right spiders that are not isomorphic, then there exist two palm trees such that their left spiders are not isomorphic and their right spiders are not isomorphic. Then, by Theorem 12-(c), F-SUBDIVISION is NP-complete.

Assume now that all the right spiders are isomorphic to a spider R. Let L 1 , . . . , L p be the left spiders (possibly some of them are isomorphic). We shall decribe an algorithm to solve

F-SUBDIVISION.
Let D be a digraph. By the above remark, if D contains an F-subdivision, then it contains an F-subdivision such that only the bars of the palm trees are subdivided. Hence we look for such a subdivision. Observe that such a subdivision is the disjoint union of copies of each of the L i , 1 ≤ i ≤ p and p copies of R together with p disjoint directed paths from the bodies of the copies of the L i to the bodies of the p copies of R. Hence to decide if D contains an F-subdivision, we try all possibilities for the disjoint union of spiders L i , 1 ≤ i ≤ p, and p spiders R and for each possibility we check via a Menger algorithm if there are disjoints directed paths from the bodies of the L i to the bodies of the copies of R.

Formally, the algorithm is the following. For each set of distinct vertices {u 1 , . . . u p , v 1 , . . . ,

v p } of D and family of disjoints subsets {U 1 , . . . ,U p ,V 1 , . . . ,V p } of D such that for 1 ≤ i ≤ p, u i ∈ U i and v i ∈ V i ,
D \ ( ∪ p i=1 (U i ∪ V i ) \ {u i , v i })

The Fork Problem and bispindles

A fork with bottom vertex a, top vertices b and c and centre t is a digraph in which

• a, b and c are distinct, and t is distinct from b and c (but possibly equal to a),

• every vertex except a has in-degree 1 and a has in-degree 0, and • all vertices except b, c and t have out-degree 1 and b and c have out-degree 0 and t has out-degree 2.

The following problem is very useful, as it can be efficiently solved. We claim that this necessary condition is also sufficient. Indeed, assume that there is a directed (a, b)-path P in Dc and a directed (a, c)-path Q in Db. Let t be the last vertex on P which also belongs to Q. Such a vertex exists because a is in P and Q. Then the union of P and Q[t, c] is the desired fork.

Since one can decide in linear time if there is a directed (u, v)-path in a digraph, FORK can be solved in linear time.

The (k 1 , . . . , k p ; l 1 , . . . , l q )-bispindle, denoted B(k 1 , . . . , k p ; l 1 , . . . , l q ), is the digraph obtained from the disjoint union of a (k 1 , . . . , k p )-spindle with tail a 1 and head b 1 and a (l 1 , . . . , l q )spindle with tail a We say that (P 1 , . . . ,

P p ; Q 1 , . . . , Q q ) is a (k 1 , . . . , k p ; l 1 , . . . , l q )-bispindle if, for each 1 ≤ i ≤ p, P i is a directed (c, d)-path of length k i , for each 1 ≤ j ≤ q, Q j is a directed (d, c)-path
of length l j and the union of the P i and Q j is B(k 1 , . . . , k p ; l 1 , . . . , l q ).

Let F be a bispindle with p forward paths and q backward paths. Consider the big paths multidigraph BP(F). By Remark 9, we get the following.

Proposition 29. Let F be a bispindle with p forward paths and q backward paths. If p ≥ 1, q ≥ 1, and p + q ≥ 4, then F-SUBDIVISION is NP-complete.

On the other hand, if F has no backward paths or exactly one backward path and one forward path, then it is a spindle or a directed cycle, respectively. In both cases, F-SUBDIVISION can be solved in polynomial time as shown in Subsections 5.1 and 4.1, respectively.

We now show using Lemma 28 that, in the remaining cases, that is when F is a bispindle with two forward paths and one backward path, F-SUBDIVISION is polynomial-time solvable.

Theorem 30. If F is a bispindle with two forward paths and one backward path, then F-

SUBDIVISION can be solved in O(n |F|+1 (n + m)) time.
Proof. Let a be the left node of F and let b and c be its two out-neighbours in F. Question: Does D contain a subdivision of F?

In the next section, we give faster algorithms to solve B(1, 2; 1)-, B(1, 2; 2)-and B(1, 3; 1)-SUBDIVISION.

Polynomial-time solvable problems via handle decomposition

Let D be a strongly connected digraph. A handle h of D is a directed path (s, v 1 , . . . , v ℓ ,t) from s to t (where s and t may be identical) such that:

• for all 1 ≤ i ≤ ℓ, d -(v i ) = d + (v i ) = 1,

and

• the digraph D \ h obtained from D by suppressing h, that is removing the arcs and the internal vertices of h, is strongly connected.

The vertices s and t are the endvertices of h while the vertices v i are its internal vertices.

The vertex s is the origin of h and t its terminus. The length of a handle is the number of its arcs, here ℓ + 1. A handle of length one is said to be trivial.

Given a strongly connected digraph D, a handle decomposition of D starting at v ∈ V (D) is a triple (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ), where (D i ) 0≤i≤p is a sequence of strongly connected digraphs and (h i ) 1≤i≤p is a sequence of handles such that:

• V (D 0 ) = {v},
• for 1 ≤ i ≤ p, h i is a handle of D i and D i is the (arc-disjoint) union of D i-1 and h i , and

• D = D p .
A handle decomposition is uniquely determined by v and either (h i ) 1≤i≤p , or

(D i ) 0≤i≤p .
The number of handles p in any handle decomposition of D is exactly

|A(D)| -|V (D)| + 1.
The value p is also called the cyclomatic number of D. Observe that p = 0 when D is a singleton and p = 1 when D is a directed cycle.

A handle decomposition (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) is nice if all handles except the first on h 1 have distinct endvertices. The following proposition is well-known (see [START_REF] Bondy | Graph theory[END_REF] Theorem 5.13).

Proposition 32. Every robust digraph admits a nice handle decomposition.

Subdivision of the lollipop

The lollipop is the digraph L with vertex set {x, y, z} and arc set {xy, yz, zy}.

Proposition 33. L-SUBDIVISION can be solved in linear time.

Proof. If D contains a strong component of cyclomatic number greater than 1, then it contains a lollipop. Indeed, the smallest directed cycle C in the component is induced and is not the whole strong component. Hence there must be a vertex v dominating a vertex of C thus forming a lollipop-subdivision.

If not, then all the strong components are cycles. Thus D contains a lollipop if and only if one of its component is a directed cycle and is not an initial strong component (i.e some arc is entering it).

All this can be checked in linear time.

Faster algorithm for subdivision of bispindles

In this subsection, using handle decomposition, we show algorithms to solve B(1, 2; 1)-, B(1, 2; 2)-and B(1, 3; 1)-SUBDIVISION, whose running time is smaller than the complexity of Theorem 30.

Recall that a digraph D is robust if it is strongly connected and UG(D) is 2-connected.

The robust components of a digraph are its robust subdigraphs which are maximal by inclusion.

Because bispindles are robust, a subdivision S of a bispindle is also robust, and if a digraph D contains S, then S must be in a robust component of D. Finding the robust components of a digraph can be done in linear time, by finding the strong components and the 2-connected components of the underlying graphs of these. Therefore one can restrict our attention to subdivision of bispindles in robust digraphs.

Subdivision of the (1, 2; 1)-bispindle

Observe that a subdivision of the (1, 2; 1)-bispindle has cyclomatic number two. Conversely, one can easily check that every robust digraph of cyclomatic number 2 is a subdivision of the (1, 2; 1)-bispindle. Hence, we have the following.

Proposition 34. A digraph contains a subdivision of the (1, 2; 1)-bispindle if and only if one of its robust components has cyclomatic number at least two.

Corollary 35. B(1, 2; 1)-SUBDIVISION can be solved in linear time.

Proof. Finding the robust components can be done in linear time and computing the cyclomatic number of all of them in linear time as well.

Subdivision of the (1, 2; 2)-bispindle

In this subsection, we show that B(1, 2; 2)-SUBDIVISION is polynomial-time solvable. In order to prove it, we characterize the robust digraphs that contain no B(1, 2; 2)-subdivision.

Let us now describe the family F 1,2;2 . A double ring is a digraph obtained from an undirected cycle by replacing every edge by two arcs, one in each direction. See Figure 2. A digraph G is in F 1,2;2 if it is a double ring or it can be obtained from a (k 1 , . . . , k p )-spindle S, p ≥ 1, with tail x and head y as follows. Add the arc yx and possibly some back arcs, that are, arcs vu such that uv ∈ A(S), so that the unique directed (y, x)-path is the arc yx. See Figure 3.

Suppose now that D /

∈ F 1,2;2 . Let us prove that it contains a B(1, 2; 2)-subdivision. Let (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) be a nice handle decomposition of D, and let i be the smallest positive integer such that D i / ∈ F 1,2;2 . Clearly i ≥ 2 because every directed cycle is in F 1,2;2 .

Then D i-1 is in F 1,2;2 .

We shall prove that D i contains a B(1, 2; 2)-subdivision, and thus so does D. Suppose first that D i-1 is the double ring associated to a cycle x 1 x 2 . . . x n x 1 . Without loss of generality, we may assume that the origin of h i is x 1 and its terminus x j for 2 ≤ j ≤ n.

Then (h i , x 1 . . . x j ; x j . . . x n x 1 ) is a B(1, 2; 2)-subdivision. (Observe that if j = 2, then h i must have length at least 2, since there are no multiple arcs.)

Suppose now that D i-1 is not a double ring. Let x and y be the two vertices of D i-1 as in the definition of F 1,2;2 . In other words, D i-1 is obtained from a spindle (P 1 , P 2 , . . . , P k ) with tail x and head y by adding yx and some back arcs. We distinguish several cases according to the possible locations of the tail u and head v of h i . Observe that (u, v) ̸ = (x, y) for otherwise D i would be in F 1,2;2 .

(i) u = y and v = x. Since yx is an arc of D i-1 and there are no multiple arcs, the handle h i has length at least 2. Hence (yx, h i ; P 1 ) is a B(1, 2; 2)-subdivision.

(ii) u = x and v is an internal vertex of some P j . Since there are no multiple arcs, one of the two (x, v)-paths h i and P j [x, v] has length at least 2. Hence (h i , P j [x, v]; P j [v, y]x) is a B(1, 2; 2)-subdivision.

(iii) v = y and u is an internal vertex of some P j . This case is similar to the previous one by directional symmetry.

(iv) u = y and v is an internal vertex of some P j . Then (h i , yP j [x, u]; P j [u, y]) is a B(1, 2; 2)subdivision. Note that, since D i ̸ ∈ F 1,2;2 , at least one of h i and P j [u, y] has length more than one.

(v) v = x and u is an internal vertex of some P j . This case is similar to the previous one by directional symmetry.

(vi) u and v are internal vertices of the same P j and u precedes v on P j . Since there are no multiple arcs, one of the two (u, v)-paths h i and uP j v has length at least 2. Hence

(h i , P j [u, v]; P j [v, y]xP j [x, v]) is a B(1, 2; 2)-subdivision.
(vii) u and v are internal vertices of the same P j and v precedes u on P j . If h i is of length one, then in D i all the back arcs associated to arcs of P j exist, for otherwise D i would be in F 1,2;2 . These arcs induce a directed (y, x)-path R j of length at least 2. Moreover, k ≥ 2, for otherwise D i would be in F 1,2;2 with y as left node and x as right node. If k = 2 and the path of {P 1 , P 2 } \ {P j } was of length one, then D i would be a double ring. Hence, there is j ′ ̸ = j such that P j ′ has length at least two, and we have the B(1, 2; 2)-subdivision (yx, R j ; P ′ j )

(viii) u is an internal vertex of P j , v is an internal vertex of P j ′ and j ̸ = j ′ . Then (P j [u, y], h i P j ′ [v, y];

yP j [x, u]) is a B(1, 2; 2)-subdivision.
Corollary 37. B(1, 2; 2)-SUBDIVISION can be solved in linear time.

Subdivision of the (1, 3; 1)-bispindle

Observe that there is a C 4 in a (1, 3; 1)-bispindle. So, a digraph D that has no directed cycle of length greater than 3 contains no B(1, 3; 1)-subdivision.

Let D be a robust digraph and

C = (v 1 , . . . , v ℓ , v 1 ) a directed cycle in D. A handle decom- position (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) is said to be C-bad if (i) D 1 = C;
(ii) for all i ≥ 2, h i has length 1 or 2, its endvertices are on C and the distance between the origin and the terminus of

h i around C is 2. (iii) If h i is a (v k , v k + 2)-path and h j is a (v k-1 , v k + 1)-path (indices are taken modulo ℓ),
then these two handles have length 1. • D contains a B(1, 3; 1)-subdivision,

(iv) If ℓ ≥ 5, there no k such that (v k-2 , v k ), (v k-1 , v k+1 ) and (v k , v k+2 )
• C is not a longest circuit in D, or

• D has a C-bad handle decomposition. Proof. Set C = (v 1 , . . . , v ℓ , v 1 ). Let H = (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) be a nice handle decompo- sition of D such that D 1 = C. If H is not C-bad, then let k be the largest integer such that H k = (v, (h i ) 1≤i≤k , (D i ) 0≤i≤k )
is a C-bad handle decomposition. One of the following occurs:

(i) the origin s k+1 of h k+1 is the internal vertex of some h i , i ≥ 2. Since H k is C-bad, then necessarily h i = (s i , s k+1 ,t i ), and there is a directed path (s i , v i ,t i ) of length 2 in C. Let t k+1 be the terminus of h k+1 . If t k+1 is on C, we set h * = h k+1 and t * = t k+1 . If not, then t k+1 has an out-neighbour t * on C and we let h * be the concatenation of h k+1 and (t k+1 ,t * ). In both cases, h * is a directed (s k+1 ,t * )-path with no internal vertices in C. (ii) the terminus of h k+1 is the internal vertex of some h i , i ≥ 2. We get the result in a similar way to the preceding case.

If t * = v i , then h * ∪ (C \ {s i v i }) ∪ (s i , s k+1 ) is a directed cycle longer than C. If t * = s i , then (C ∪ h * ∪ (s i , s k+1 )) -v i is a B(1,
(iii) h k+1 has length greater than 2 and its two endvertices are on C. Then the union of C and h k+1 is a B(1, 3; 1)-subdivision.

(iv) h k+1 = (s,t) with s,t and C[s,t] has length at least 3. Then C ∪ (s,t) is a B(1, 3; 1)subdivision with right node s and left node t.

(v) h k+1 is one of the two handles h and h ′ , where h is a

(v k-1 , v k+1 )-handle and h ′ is a (v k , v k+2
) for some k, and one of h and h ′ has length two. If h has length two, say

(v k-1 , x 1 , v k+1 ), then the union of (v k-1 , v k )∪h ′ , (v k-1 , x 1 , v k+1 , v k+2 ) and C[v k+2 , v k-1 ] form a B(1, 3; 1)-subdivision. If h ′ has length two, say h ′ = (v k , x 2 , v k+2 ), then the union of h∪(v k+1 , v k+2 ), (v k-1 , v k , x 2 , v k+2 ) and C[v k+2 , v k-1 ] form a B(1, 3; 1)-subdivi- sion.
(vi) h k+1 is one of the three handles

(v k-2 , v k ), (v k-1 , v k+1 ), (v k , v k+2
) for some k and p ≥ 5. In this case, the union of

(v k-2 , v k-1 , v k+1 , v k+2 ), (v k-2 , v k , v k+2 ) and C[v k+2 , v k-2 ]
form a B(1, 3; 1)-subdivision. Suppose, by way of contradiction, that D p contains a B(1, 3; 1)-subdivision S. Necessarily, h p is a subdigraph of S. Free to rename, we may assume that v 1 and v 3 are the origin and the terminus, respectively, of h p . If v 2 is not in S, then replacing

h p with (v 1 , v 2 , v 3 ) in S,
we obtain a B(1, 3; 1)-subdivision contained in D p-1 , a contradiction. Hence v 2 ∈ V (S). By the conditions (iii) and (iv) of a C-bad handle decomposition, there cannot be both a handle ending at v 2 and a handle starting at v 2 . By directional symmetry, we may assume that v 2 has in-degree one, and so v 1 v 2 ∈ A(S), and v 1 is the left node of S. Now, v 2 v 3 is not an arc of S, for otherwise v 3 will be the right node of S, and the two directed (v 1 , v 3 )-paths in S have length at most 2, a contradiction. But, in S, there is an arc leaving v 2 , it must be in a handle, and so by (iv) and (ii) of the definition of C-bad, this arc must be v 2 Theorem 42 (Fortune, Hopcroft and Wyllie [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF]). For every fixed k the k-LINKAGE problem is polynomial-time solvable for acyclic digraphs.

Clearly the class of acyclic digraphs is closed under the operation given in Lemma 41 and hence we have the following.

Corollary 43 (Fortune, Hopcroft and Wyllie [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF]). For every digraph F, F-SUBDIVISION is polynomial-time solvable for acyclic digraphs. Theorem 45 (Johnson et al. [START_REF] Johnson | Directed tree-width[END_REF]). For every fixed k, k-LINKAGE is polynomial-time solvable on digraphs of bounded directed tree-width.

We will not give the definition of directed tree-width here as it is rather technical, but it suffices to say that the class of digraphs with bounded directed tree-width is closed on the operation of Lemma 41 so we have.

Theorem 46 (Johnson et al. [START_REF] Johnson | Directed tree-width[END_REF]). For every digraph F, F-SUBDIVISION is polynomial-time solvable on digraphs of bounded directed tree-width.

Theorem 47 (Chudnovsky et al. [START_REF] Chudnovsky | Disjoint paths in tournaments[END_REF]). For any digraph F, F-SUBDIVISION is polynomialtime solvable when restricted to the class of tournaments.

Let D = (V, A) be a digraph. We say that

W ⊆ V guards V ′ ⊆ V in D if N + (V ′ ) ⊆ W ,
that is, all out-neighbours of V ′ are in W . A DAG-decomposition of a digraph D is a pair (H, χ) where H is an acyclic digraph and χ = {W h : h ∈ V (H)} is a family of subsets of V (D) satisfying the following three properties: More generally, the property of having an F-subdivision can be defined in MSO1 monadic second order logic with vertex-set quantifications) and so can be solved in polynomial time on the class of digraphs with bounded directed clique-width. If F is not fixed, but specified in the input, it can also be solved in FPT-time when parameterized by V (F)|. See Theorem 1.24 of [START_REF] Courcelle | Graph structure and monadic second-order logic. A language-theoretic approach[END_REF]. Theorem 51 (Reed et al. [START_REF] Reed | Packing directed circuits[END_REF]). For every k, there is an integer f (k) such that every digraph has either k disjoint directed cycles or a feedback vertex set of size at most f (k).

(i) V (D) = ∪ h∈V (H) W h , (ii) for all h, h ′ , h ′′ ∈ V (H), if h ′ lies on a directed (h, h ′′ )-path, then W h ∩W h ′′ ⊆ W h ′ , and (iii) if (h, h ′ ) ∈ A(H), then W h ∩ W h ′ guards W ≥h ′ \ W h ,
The function f constructed by Reed at al. [START_REF] Reed | Packing directed circuits[END_REF] grows very quickly. It is a multiply iterated exponential, where the number of iterations is also a multiply iterated exponential.

The correct value of f (2) is 3 as shown by McCuaig [START_REF] Mccuaig | Intercyclic digraphs[END_REF] who also gave a polynomial-time algorithm for finding two disjoint directed cycles in a digraph or showing that it has τ(D) ≤ 3.

Corollary 52. For any digraph F, F-SUBDIVISION is polynomial-time solvable when restricted to the class of digraphs with bounded cycle-packing number.

F-SUBDIVISION for some special classes of digraphs

In this section the focus is on the structure of F rather than the method for solving F-SUBDIVISION or proving it NP-complete. For several of the classes we can provide (almost) complete characterizations in terms of complexity of F-SUBDIVISION .

Disjoint union of directed cycles

Since C k -SUBDIVISION can be solved in polynomial time for any fixed k, a natural question is to ask for the complexity of F-SUBDIVISION when F is the disjoint union of directed cycles. This is not a simple problem as can be seen from the observation that a digraph D contains k disjoint directed cycles if and only if it contains an F-subdivision where F is the disjoint union of k directed 2-cycles.

Hence, if F is the disjoint union of k directed 2-cycles, F-SUBDIVISION is equivalent to deciding if ν(D) ≥ k for a given digraph D. Using Theorem 51, Reed et al. [START_REF] Reed | Packing directed circuits[END_REF] proved that this can be done in polynomial time. Exercise 13.25 of [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. As observed in [START_REF] Grohe | Parameterized approximability of the disjoint cycle problem[END_REF], the problem parameterized with k is hard for the complexity class W [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] (this follows easily from the results of [START_REF] Slivkins | Parameterized tractability of edge-disjoint paths on directed acyclic graphs[END_REF]). This means that, unless

FPT = W [1],

Subdivisions of wheels and fans

The fan F k is the graph obtained from the directed path P k by adding a vertex, called In fact we will prove it for some classes of graphs contructed from T T 4 . For any nonnegative integer p, let T T 4 (p) be the digraph obtained from T T 4 with source u and sink v by adding p new vertices dominated by u and dominating v. In particular, T T 4 (0) = T T 4 . We denote by T T * 4 (p), the digraph obtained from T T 4 (p) by deleting the arc from its source u to its sink v. For simplicity, we abbreviate T T * 4 (0) in T T * 4 .

We need the following definitions. Let X be a set of vertices in a digraph D. The outsection generated by X in D is the set of vertices y to which there exists a directed path (possibly restricted to a single vertex) from x ∈ X; we denote this set by S + D (X). For simplicity, we write S + D (x) instead of S + D ({x}). The dual notion, the in-section, is denoted by S - D (X). Note that the out-section and the in-section of a set may be found in linear time by any tree-search algorithm. Subproof. Assume that |I(x)| ≥ 2. Without loss of generality, {1, 2} ⊂ I(x). We shall prove that D ′ contains a T T 4 (p)-subdivision with source u and sink v.

• Suppose first that S - H (x) ∩ Q 1 ̸ = / 0 and S + H (x) ∩ Q 2 ̸ = / 0. Then there is a directed (Q 1 , x)path and a directed (x, Q 2 )path whose concatenation contains a directed (Q 1 , Q 2 )path R. Let y be the first vertex on R in

∪ k i=2 Q i .
Free to swap the names of Q 2 and the path Q l containing y and taking the subpath of R from its origin to y instead of R, we may assume that y is the last vertex of R. Now the union of P 1 , . . . , P p+3 , and R form a T T 4 (p)-subdivision.

• If S - H (x) ∩ Q 2 ̸ = / 0 and S + H (x) ∩ Q 1 ̸ = / 0, the proof is similar to the previous case.

• Suppose now that S + H (x) ∩ Q 1 ̸ = / 0 and S + H (x) ∩ Q 2 ̸ = / 0. We may assume that S - H (x) ∩ ∪ k i=1 Q i = / 0, otherwise we are in one of the previous case, and we get the result. Let R be a shortest (u, x)-path in D ′ . Then every vertex in Ru is a vertex of H -

∪ k i=1 Q i .
Let S 1 be a shortest directed (x, Q 1 )-path and S 2 be a shortest directed (x, Q 2 )-path.

For i = 1, 2, let z i be the terminus of S i . We may assume that all the internal vertices of S 1 and S 2 are in H - x ∈ V (H). For 1

≤ i ≤ k, let V i = {x | I(x) = {i}}. Then (V 1 , . . .V k ) is a partition of V (H).
Moreover, by definition, there is no arc between two distinct parts of this partition. In addition, in D ′ ⟨X i ∪ {u, v}⟩, there cannot be two internally disjoint directed (u, v)-paths, for otherwise it would contradicts the maximality of (P 1 , . . . , P k ). Hence, D ′ contains no T T * 4subdivision, and so no T T 4 (p)-subdivision. ♢

This finishes the proof of Theorem 66. It remains to prove that D 3 -SUBDIVISION is polynomial-time solvable.

The bulky vertex of a D 3 -subdivision S is the unique vertex of S with degree 4. We now give a procedure that given a vertex v, two of its out-neihbours s 1 , s 2 and two of its in-neighbours t 1 , t 2 check if there is a D 3 -subdivision S in which v is the bulky vertex and {vs 1 , vs 2 ,t 1 v,t 2 v} ∈ A(S). Such a subdivision will be called suitable.

b(P) ≥ 2 ,

 2 then take ab as an arc of the first block of P and cd an arc of the first block of Q. Replacing ab and cd by ad and cb results necessarily in b(P ′ ) = 1 and b(Q ′ ) = b(P) + b(Q) -1. If b(P) = 1, take ab as an arc of the first block of P and cd an arc of the second block of Q. Then {b(P ′ ), b(Q

  two blocks and the other b(P) + b(Q) -2 blocks. So if {b(P), b(Q)} ̸ = {2, b(P) + b(Q) -2}, we have the result. Hence we may assume that {b(P), b(Q)} = {2, b(P) + b(Q) -2}, so b(P) = 2 because b(Q) ≥ 3. Hence b(Q) ≥ 6, because (P, Q) is not bad. Take ab be an arc of the first block of P and cd an arc of the third block of Q. Then one of P ′ , Q ′ has four blocks and the other has b(P) + b(Q) -4 blocks, so we have the result. If two digraphs D and D ′ are isomorphic, then we write D ∼ = D ′ . If they are not, then we write D ̸ ∼ = D ′ .

(a) If (P 1 , P 2 )

 12 is not a bad pair, then by our choice of ab and cd, {b(P ′ 1 ), b(P ′ 2 )} ̸ = {b(P 1 ), b(P 2 )}. Since b(P * 1 ) = b(P 1 ) and b(P

Problem 14 .

 14 Is the following problem is polynomial-time solvable? SPIDER-SUBDIVISION Input: A spider F and a digraph D. Question: Does D contain a subdivision of F? Similarly, one could ask if SPIDER-SUBDIVISION can be solved in FPT time whem parameterized by F, that is in f (|V (F)|) × n c time, where f is a computable function and c an absolute constant. Lemma 15. Let F 1 be a digraph and S a disjoint union of spiders. If F 1 -SUBDIVISION is polynomial-time solvable, then (F 1 + S)-SUBDIVISION is also polynomial-time solvable. Proof. For each set A of |S| vertices, we check if the digraph D⟨A⟩ induced by A contains S.

  there are O(n |V (W )|-1 ) choices for it, and there are n choices for x, hence the algorithm runs O(n |V (W )| ) times a Menger algorithm. Since a Menger algorithm runs in linear time, the overall complexity is O(n |V (W )| (n + m)). Clearly, given as input a windmill W and a digraph D, deciding if D contains a Wsubdivision is NP-complete because the Hamiltonian directed cycle problem is a particular case of it. Theorem 25 tells us that this problem parameterized by |W | is in XP. But is it fixed-parameter tractable? Problem 26. Is the following problem fixed-paramater tractable? CYCLE-WINDMILL SUBDIVISION Input: A cycle windmill W and a digraph D. Parameter: |V (W )|.

  via a Menger algorithm. If there are such paths, the union of them with the spiders is an F-subdivision and we return it. If such paths do not exist, we proceed to the next case. The number of possible cases is O(n |V (F)| ) and each run of the Menger algorithm can be done in linear time. Hence the complexity of the algorithm is O(n |V (F)| (n + m)).

FORK

  Input: A digraph D and three distinct vertices a, b and c. Question: Does D contain a fork with bottom vertex a and top vertices b and c? Lemma 28. FORK can be solved in linear time. Proof. Assume that a digraph D contains a fork with bottom vertex a and top vertices b and c. Then, clearly, there are a directed (a, b)-path in Dc and a directed (a, c)-path in Db.

  2 and head b 2 by identifying a 1 with b 2 into a vertex a, and a 2 with b 1 into a vertex b. The vertices a and b are called, respectively, the left node and the right node of the bispindle. The directed (a, b)-paths are called the forward paths, while the directed (b, a)-paths are called the backward paths.

For

  every subset S of |F| vertices, we check if D⟨S⟩ contains a copy of F \ {ab, ac} with a ′ , b ′ , c ′ corresponding to a, b, c, respectively. Then we check in D -(S \ {a ′ , b ′ , c ′ }) if there is a fork with bottom vertex a ′ and top vertices b ′ and c ′ . Since there are O(n |F| ) possible set S and FORK can be solved in linear time by Lemma 28, our algorithm runs in O(n |F|+1 (n + m)) time. The complexity given in Theorem 30 is certainly not best possible. Similarly to Proposition 23, one shows that given a digraph D and a bispindle F (with two forward paths and one backward path), deciding if D contains an F-subdivision is NP-complete. It is again natural to ask if it is FPT when parameterized by |F|. Problem 31. Is the following problem fixed-paramater tractable? PARAMETERIZED BISPINDLE-SUBDIVISION Input: A bispindle F with two forward paths and one backward path and a digraph D. Parameter: |V (F)|.

Figure 2 :

 2 Figure 2: The double ring of order 6.

Figure 3 :

 3 Figure3: A digraph in F 1,2;2 , which is not a double ring

  are handles. The notion of C-bad handle decomposition plays a crucial role for finding B(1, 3; 1)subdivision as shown by the next two lemmas. Lemma 38. Let D be a digraph and C a directed cycle in D of length at least 4. Then one of the following holds:

Lemma 39 .

 39 Let D be a robust digraph and C a directed cycle in D of length at least 4. If D has a C-bad handle decomposition, then it does not contain any B(1, 3; 1)-subdivision. Proof. By induction on the number p of handles of the handle decomposition, the result holding trivially if p = 1. Set C = (v 1 , . . . , v ℓ , v 1 ) and let H = (v, (h i ) 1≤i≤p , (D i ) 0≤i≤p ) be a C-bad handle decomposition of D. By the induction hypothesis D p-1 does not have any B(1, 3; 1)-subdivision.

v 4 .

 4 Again by (iii) of the definition of C-bad, there is no arc leaving v 3 except v 3 v 4 . Hence v 3 v 4 ∈ A(S). Then v 4 is the right node of S, and the two directed (v 1 , v 4 )-paths in S have length 2, a contradiction. Theorem 40. B(1, 3; 1)-SUBDIVISION can be solved in O(n • m) time. Proof. Given a digraph D, we compute the robust components of D and solve the problem separately on each of them. For each robust component, we first search for a directed cycle C 0 of length at least 4. This can be done in O(n • m) time by Theorem 19. If there is no such cycle, then we return 'no'. If not, then we build a handle decomposition starting from C := C 0 . Each time, we add a new handle, one can mimick the proof of Lemma 38, we either find a B(1, 3; 1)-subdivision which we return, or a C-bad handle decomposition, or a directed cycle C ′ longer than the current C. Observe that in this case, it is easy to derive a C ′ -bad handle decomposition containing the vertices added so far from the C-bad one. This can be done in O(n • m) time because an arc has to be considered only when it is added in a handle, and we just need to keep a set of at most m handles.

Proof.

  Let F be a digraph with vertex set {1, 2, . . . , r} and let D belong to D. It is sufficient to show that we can decide in polynomial time whether a fixed one-to-one mapping of V (F) to V (D) extends to a subdivision of F in D. So we assume below that a one-to-one mapping of V (F) to V (D) is given. For each vertex α ∈ V (F), fix an ordering of the arcs entering α and an ordering of the arcs leaving α: We label the d - F (α) in-neighbours of α by i α,1 , i α,2 , . . . , i α,d - F (α) and we label the d + F (α) out-neighbours of α by o α,1 , o α,2 , . . . , o α,d + F (α) . For a given arc e = αβ ∈ A(F) this gives two labels l + αβ and l - αβ (the number it has in α's out-labelling and in β's in-labelling). Given the one-to-one mapping f : V (F) → V (D) we make a new digraph D F from D by replacing each vertex f (α), α ∈ V (F) by two sets I f (α) = {i α,1 , i α,2 , . . . , i α,d - F (α) } and O f (α) = {o α,1 , o α,2 , . . . , o α,d + F (α) } and joining every in-neighbour x of f (α) in D to every vertex y in I f (α) by an arc x → y and every vertex p of O f (α) to every out-neighbour q of f (α) in D (it is possible that one of the sets I f (α) , O f (α) is empty in which case we add no arcs corresponding to that set). Now it is easy to check that f can be extended to a subdivision of F in D if and only if D F contains vertex-disjoint paths {P αβ | αβ ∈ A(F)} where P αβ starts in o α,l + αβ and ends in i β,l - αβ . Since D F is in D we can check the existence of the desired paths in polynomial time. Doing this for (at most) all possible one-to-one mappings of V (F) to V (D) we can decide in polynomial time (since |V (F)| is constant) whether D contains an F-subdivision.

A

  feedback vertex set or cycle transversal in a digraph D is a set of vertices S such that D -S is acyclic. The minimum number of vertices in a cycle transversal of D is the cycletransversal number and is denoted by τ(D). Corollary 50. For any digraph F, F-SUBDIVISION is polynomial-time solvable when restricted to the class of digraphs with bounded cycle-transversal number. Proof. Let X be a cycle-transversal of D. Then D ′ = D -X is acyclic and it is easy to see that D has DAG-width at most X, since we can take H = D ′ and W h = {h} ∪ X for all h ∈ V (D ′ ) to obtain a DAG-decomposition of D whose width is |X|. Now the result follows from Corollary 49. The maximum number of disjoint directed cycles in a digraph D is called the cyclepacking number and is denoted by ν(D). Clearly, ν(D) ≤ τ(D). Conversely, proving the so-called Gallai-Younger Conjecture, Reed et al. [17] proved that τ(D) is bounded above by a function of ν(D).

  the centre, dominated by every vertex of P k . The wheel W k is the graph obtained from the directed cycle C k by adding a vertex, called the centre, dominated by every vertex of C k . The path P k (resp. cycle C k ) is called the rim of F k (resp. W k ) and the arcs incident to the centre are called the spokes. Similarly, if D ′ is a subdivision of a wheel or a fan D, the centre of D ′ is the vertex corresponding to the centre of D, the rim of D ′ is the directed path or cycle corresponding to the rim of D, and the spokes of D ′ are the directed paths corresponding to the spokes of D. Proposition 57. A digraph D contains a W 2 -subdivision if and only if it contains some vertex z such that Dz has a strong component S and two directed (S, z)-paths having only z in common.

Theorem 66 .

 66 For every non-negative integer p, one can solve T T 4 (p)-SUBDIVISION in O(n 3 (n + m))-time. Proof. Let D be a digraph and let u and v be two distinct vertices of D. We shall describe a O(n(n + m))-time algorithm for finding a T T 4 (p)-subdivision in D with source u and sink v, if one exists. Observe that all vertices in such a subdivision are in S + D (u) ∩ S - D (v), hence we first restrict to the graph D ′ the digraph induced by this set. Then, using a maximum flow algorithm, we can find in D ′ a set of internally disjoint directed (u, v)-paths of maximum size in O(n(n + m))-time. Let (P 1 , . . . , P k ) denote this set. If k < p + 3, then return 'no', because in any T T 4 (p)-subdivision with source u and sink v, there are p + 3 internally disjoint directed (u, v)-paths Hence, we now assume that k ≥ 3. For 1 ≤ i ≤ k, set Q i = P i -{u, v}, and set H = D ′ -{u, v}. For every vertex x in V (H), we compute S(x) = S - H (x) ∪ S + H (x), and deduce I(x) = {i | V (Q i ) ∩ S(x) ̸ = / 0}. If there exists x, such that |I(x)| ≥ 2, then return 'yes'. Otherwise return 'no'.The validity of this algorithm is proved by Claim 66.2.Claim 66.1. For all x ∈ V (H), I(x) ̸ = / 0.Subproof. In D ′ , there are directed (u, x)-and (x, v)-paths, whose concatenation contains a directed (u, v)-path R. Since (P 1 , . . . , P k ) is a set of internally disjoint directed (u, v)-paths of maximum size, R -{u, v} must intersect one of the Q i 's, say Q i 0 . By definition, V (R) \ {u, v} ⊆ S(x), so i 0 ∈ I(x). ♢ Claim 66.2. D ′ contains a T T 4 (p)-subdivision with source u and sink v if and only if there exists x ∈ V (H) such that |I(x)| ≥ 2.

  for otherwise one vertex z among z 1 and z 2 satisfies the condition of one of the previous cases (up to a permutation of the labels). Then the union of paths P 2 , . . . , P p+3 , R, S 1 , S 2 andP 1 [z 1 , v] form a T T 4 (p)-subdivision. • If S - H (x) ∩ Q 1 ̸ = / 0 and S - H (x) ∩ Q 2 ̸ = / 0,the proof is similar to the previous case by directional symmetry. Assume now that |I(x)| < 2 for all x ∈ V (H). Then, by Claim 66.1, |I(x)| = 1 for all

Corollary 67 .

 67 For all non-negative integer p, the T T * 4 (p)-SUBDIVISION problem can be solved in O(n 3 (n + m)). Proof. Observe that a graph D contains a T T * 4 (p)-subdivision with source u and sink v, if and only if the graph D ∪ {uv} contains a T T 4 (p)-subdivision. Hence by just adding the arc uv to D if it does not exists in the above algorithm, we obtain a polynomial-time algorithm for T T * 4 (p)-SUBDIVISION.9.4. Subdivisions of digraphs with three verticesLet us denote by ⃗ K n the complete digraph on n vertices, in which there is an arc uv for any two distinct vertices u and v. Let D 3 be the digraph obtained from ⃗ K 3 by removing an arc.Theorem 68. Let F be a digraph on three vertices. Then F-SUBDIVISION is polynomial-time solvable unless F = ⃗ K 3 in which case it is NP-complete. Proof. If F is neither D 3 nor ⃗ K 3 ,then it is either a disjoint union of spiders, or a spindle, or a bispindle, or the lollipop (or its converse), or a windmill, and so F-SUBDIVISION can be solved in polynomial time by virtue of the results of the previous sections. If F = ⃗ K 3 , then F-SUBDIVISION is NP-complete by Corollary 10.

  Given a digraph D we form the digraph D F 2 by fixing one vertex x in F 2 and adding |V (D)| disjoint copies of F 2 such that the ith copy has its copy of x identified with the ith vertex of D. It is easy to check that D F 2 contains an F-subdivision if and only if D contains an F 1 -subdivision. This follows from the fact that F 2 contains no F 1 -subdivision and UG(F 1 )

	is 2-connected.
	Lemma 5. Let F be a digraph in which every vertex v satisfies max{d + (v), d -(v)} ≥ 2, and
	let S be a subdivision of F.
	(i) If F-SUBDIVISION is NP-complete, then S-SUBDIVISION is NP-complete.
	(ii) If S-SUBDIVISION is polynomial-time solvable, then F-SUBDIVISION is polynomial-
	time solvable.

again and notice that the digraphs A, B show that we need the assumption that F 1 is strongly connected in Lemma 3 (and the analogous version where the roles of F 1 and F 2 are interchanged).

A digraph D is robust if it is strongly connected and UG(D) is 2-connected.

Lemma 4. Let F 1 and F 2 be two digraphs such that F 1 is robust and F 2 contains no F 1subdivision. Let F be obtained from F 1 and F 2 by identifying one vertex of F 1 with one vertex

of F 2 . (i) If F 1 -SUBDIVISION is NP-complete, then F-SUBDIVISION is NP-complete. (ii) If F-SUBDIVISION is polynomial-time solvable, then F 1 -SUBDIVISION is polynomialtime solvable. Proof.

Proof. We shall prove a polynomial reduction from F-SUBDIVISION to S-SUBDIVISION.

Let D be an instance of F-SUBDIVISION and p be the length of a longest path in S corresponding to an arc in F. Let D p be the D-subdivision obtained by replacing every arc of D by a directed path of length p. One easily checks that D has an F-subdivision if and only if D p has an S-subdivision. It follows from the fact that every vertex v corresponding to one of F in S must be mapped onto a vertex corresponding to D in D p because max{d

  The proof is very similar to the one of Theorem 8. We give a reduction from 2-LINKAGE in digraphs with no big vertices in which x 1 and x 2 are sources and y 1 and y 2 are sinks.Let D, x 1 , x 2 , y 1 , y 2 be an instance of this problem. Let ab be an arc of the bar of D 1 and cd be an arc of the bar of D 2 . Moreover, if (P 1 , P 2 ) is not a bad pair, we choose ab and cd as decribed in Lemma 11. Let H be the digraph obtained from the disjoint union of F \ {ab, cd} and D by adding the arcs ax 1 , cx 2 , y 1 b, and y 2 d. We can then show that H has an F-subdivision if and only if D has a 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ).

  If k is not fixed but specified in the input, it is NP-complete to decide if a digraph has a directed cycle of length k because the Hamiltonian directed cycle is a particular case of it.Gabow and Nie proved that it is FPT to decide if a graph has a cycle of length at least k.Recall that two paths are internally disjoint if they have no internal vertices in common.For any fixed k, there exist algorithms running in linear time that, given a digraph D and two distinct vertices x and y, returns k internally disjoint directed (x, y)-paths in D if some exist, or returns 'no' otherwise. Indeed, in such a particular case, any flow algorithm like Ford-Fulkerson algorithm for example, performs at most k incrementing-path searches, because it increments the flow by 1 each time, and we stop when the flow has value k, or if we find a cut of size less than k, which by Menger's Theorem certifies that there do not exist k internally disjoint directed (x, y)-paths . Moreover each incrementing-path search consists in a search (usually Breadth-First Search) in an auxiliary digraph of the same size, and so is done in linear time. For more details, we refer the reader to the book of Ford and Fulkerson [? ] or Chapter 7 of[START_REF] Bondy | Graph theory[END_REF]. We call such an algorithm a Menger algorithm.

Proposition 17. C 2 -SUBDIVISION can be solved in linear time. Proof. A subdivision of the directed 2-cycle is a directed cycle. Hence a digraph has a C 2subdivision if and only if it is not acyclic. Since one can check in linear time if a digraph is acyclic or not [1, Section 2.1], C 2 -SUBDIVISION is linear-time solvable. Proposition 18. C 3 -SUBDIVISION can be solved in linear time. Proof. Let D be a digraph. If D has no directed 2-cycles, then D contains a C 3 -subdivision if and only if it is not acyclic, which can be tested in linear time. Assume now that D has some directed 2-cycles. Let H be the graph with vertex set V (D) and edge-set {xy | (x, y, x) is a 2-cycle of D}. The graph H can be constructed in linear time.

We first check, in linear time, if H contains a cycle. If H contains a cycle, then it has length at least 3 and any if its two directed orientations is a directed cycle in D, so we return such a cycle, certifying that D is a 'yes'-instance.

If not, then H is a forest. If there is any single arc uv (an arc which is not part of a 2-cycle) in D such that both u and v belong to the same connected component of H, then it is easy to produce a directed cycle of length at least 3 in D (following a path from u to v in H) so we may assume that all single arcs go between different components in H. Now it is easy to see that D contains a cycle of length at least 3 if and only if the digraph obtained by contracting (into a vertex) each connected component of H in D has a directed cycle. In case we find such a cycle, we can easily reproduce a directed cycle of length at least 3 in D. Theorem 19 (Gabow and Nie [11, 12]). One can decide in O(k 3k • n • m) time whether a digraph contains a directed cycle of length at least k. Problem 20. For any fixed k, can we solve C k -SUBDIVISION in linear time? In other words, does there exists a computable function f such that one can decide in O( f (k)(n + m)) time whether a digraph contains a directed cycle of length at least k? 5. Polynomial-time solvable problems via flows 5.1. Subdivision of spindles A (k 1 , . . . , k p )-spindle is the union of p pairwise internally disjoint directed (a, b)-paths P 1 , . . . , P p of respective length k 1 , . . . , k p . Vertex a is said to be the tail of the spindle and b its head. Proposition 21. If F is a spindle, then F-SUBDIVISION can be solved in O ( n |V (F)| (n + m) ) time.

Proof. Let F be a spindle with tail a and head b. Let a 1 , . . . , a p be the out-neighbours of a in F. An F-subdivision may be seen as an F-subdivision in which only the arcs aa i , 1 ≤ i ≤ p are subdivided. The following algorithm takes advantage of this property.

Let D be a digraph. For each pair (S, a ′ ) where S is a set of |V (F)| -1 vertices and a ′ a vertex of D -S, we first enumerate all the possible subdigraphs of D⟨S⟩ isomorphic to Fa with a ′ 1 , . . . , a ′ p corresponding to a 1 , . . . , a p . We then check if, in D -(S \ {a ′ 1 , . . . , a ′ p }), there exist p internally disjoint directed paths P i , 1 ≤ i ≤ p, each P i starting in a ′ and ending in a ′ i . This can be done using a Menger algorithm. Clearly, this algorithm decides if there is an F-subdivision in D. There are O(n |V (F)| ) possible pairs (S, a ′ ), and for each of them we run at most (|V (F)| -1)! times a Menger algorithm. Since such an algorithm runs in linear time, the time complexity of the above algorithm is O

  natural question is to ask about the complexity of deciding if a digraph contains a subdivision of a spindle, when the spindle is no more fixed but specified in the input. Reduction from the (undirected) Hamiltonian cycle problem.Let G be an undirected graph. Let D(G) be the symmetric digraph associated to G, that is D is the digraph obtained from G by replacing every edge uv by the two arcs uv and vu. Let F be any spindle of the same order as G (and D(G)). For order reason, the digraph contains an F-subdivision if and only if it contains F as a subgraph, and thus if and only if G has a

	Proposition 23. The following problem is NP-complete
	SPINDLE-SUBDIVISION
	Input: A spindle F and a digraph D.
	Question: Does D contain a subdivision of F?
	Proof. Hamiltonian cycle.

then finding an F-subdivision is equivalent to find p internally disjoint directed paths of length at least two from some vertex a to some other vertex b. Such paths exist if and only if in D \ ab there are p internally disjoint (a, b)-paths. For any pair (a, b), this can be checked in linear time by a Menger algorithm. A In view of Proposition 23, one could ask whether it is possible to solve SPINDLE-SUBDIVISION in f (|V (F)|) × n c time, where f is a computable function and c an absolute constant? This may be formulated in FPT setting as follows. Problem 24. Is the following problem fixed-paramater tractable? PARAMETERIZED SPINDLE-SUBDIVISION Input: A spindle F and a digraph D. Parameter: |V (F)|.

  (resp. R) with body u i (resp. v i ). If not we proceed to the next case. If yes, we check if there are p disjoint directed paths from {u 1 , . . . , u p } to {v 1 , . . . , v p } in the digraph

we check if for all i, D⟨U i ⟩ (resp. V i ) contains a spider isomorphic to L i

  At the end of this process, if no B(1, 3; 1)-subdivision has been returned, we end up with a C-bad decomposition of D. So, by Lemma 39, D has no B(1, 3; 1)-subdivision, and we can proceed to the next robust component, or return 'no' if there is none.8. Classes of digraphs for which F-SUBDIVISION is polynomial-time solvable for all FLemma 41. Let D be a class of digraphs which is closed under the operation which takes as input a digraph D ∈ D, a bounded set of vertices x 1 , x 2 , . . . , x r ∈ V (D) and integers i 1 , i 2 , . . . , i r , o 1 , o 2 , , . . . , o r , all between 0 and r and outputs the digraph D ′ that is obtained as follows: For j = 1, 2, . . . , r replace x j and all arcs incident to it by two sets of vertices I j = {v j,1 , . . . , v j,i j }, O j = {w j,1 , . . . , w j,o j } (if i j = 0 or o j = 0 the corresponding set is empty), all possible arcs from N - D (x j ) to I j and from O j to N + D (x j ). If k-LINKAGE is polynomial-time solvable for all fixed k for digraphs in D, then, for each digraph F, F-SUBDIVISION is polynomial-time solvable on digraphs in D.

  The algorithm given by Fortune, Hopcroft and Wyllie to solve k-LINKAGE problem has a runinng time in O(k!n k+2 ). Hence a natural question is to ask if it can be solved in O( f (k)n c ) time for some absolute constant c and computable function f . In the FPT setting, it can be phrased as follows. An acyclic digraph D and 2k distinct vertices x 1 , x 2 , . . . , x k , y 1 , y 2 , . . . , y k .Question: Is there a k-linkage from (x 1 , x 2 , . . . , x k ) to (y 1 , y 2 , . . . , y k ) in D?

	Problem 44. Is the following parameterized problem FPT?
	PARAMETERIZED ACYCLIC k-LINKAGE
	Input: Parameter: k.

  where W ≥h ′ is the union of all W h ′′ for which there exists a directed (h ′ , h ′′ )-path in H.The width of a DAG-decomposition (H, χ) is max h∈V (H) |W h |.The DAG-width of a digraph D (dagw(D)) is the minimum width over all possible DAG-decompositions of D. It is easy to see that a digraph D is acyclic if and only if it has DAG-width 1 (and then we can use D itself as H).

	Theorem 48 (Berwanger et al. [4], Johnson et al. [14]). For every fixed k, k-LINKAGE is
	polynomial-time solvable on digraphs of bounded DAG-width.
	Digraphs of bounded DAG-width are closed under the operation in Lemma 41 so we
	have.
	Corollary 49. For any digraph F, F-SUBDIVISION is polynomial-time solvable when re-
	stricted to the class of digraphs of bounded DAG-width.

  Theorem 53 (Reed et al.[START_REF] Reed | Packing directed circuits[END_REF]). For any fixed k, deciding if a digraph D has k disjoint directed cycles is polynomial-time solvable. Equivalently, if F is the disjoint union of directed 2-cycles, then F-SUBDIVISION is polynomial-time solvable.Remark 54. Determining ν(D) is NP-hard. Indeed, given a digraph D and an integer k, deciding whether D has at least k disjoint cycles is NP-complete. See Theorem 13.3.2 and

  there is no algorithm solving the problem with a f (k) • n O(1) running time. Problem 55. Let F be the disjoint union of p directed cycles of lengths k 1 , k 2 , . . . k p , respectively. Is F-SUBDIVISION polynomial-time solvable? Theorem 56. (C 2 +C 3 )-SUBDIVISION is polynomial-time solvable. Proof. Let D be a digraph. If D has no 2-cycles, then D has a C 2 +C 3 -subdivision if and only if it contains two disjoint cycles. This can be checked in polynomial time by Theorem 51.

Assume now that D contains 2-cycles. For each 2-cycle (x, y, x), we check if D -{x, y} has a directed cycle of length at least 3. This can be done in linear time according to Theorem

[START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF]

. If the answer is 'yes' for one of them, then we return 'yes'.

Suppose now that the answer is 'no' for all 2-cycles. Let D ′ be the digraph obtained from D by deleting the arcs of all the 2-cycles. Claim 56.1. D contains a (C 2 + C 3 )-subdivision if and only if D ′ contains two disjoint directed cycles. Subproof. Suppose that D contains a (C 2 +C 3 )-subdivision S. No cycle of S can contain two vertices x and y in a 2-cycle because D -{x, y} contains no directed cycle of length at least 3. In particular, all the arcs of S are in D ′ . Conversely, if D ′ contains two disjoint directed cycles, they form a (C 2 +C 3 )-subdivision since D ′ has no 2-cycles. ♢ Hence we check if D ′ has two disjoint directed cycles, which can be done in polynomial time according to Theorem 51.

A connected component of a digraph H is a connected component of UG(H).

Acknowledgement

The authors would like to thank Nicolas Trotignon for stimulating discussion and suggesting them the FORK problem.

Proof. Suppose D contains a subdivision of W 2 with centre z and cycle C. Then the strong component of Dz which contains C satisfies the required property.

Conversely, assume z is a vertex and S is a strong component of Dz such that there are two directed (S, z)-paths P and Q having only z in common. Let x and y be the origins of P and Q respectively.

Let R be a directed (x, y)-path in S and R ′ a directed (y, x)-path in S. (Such paths exists since S is a strong component.) If R and R ′ form a cycle we are done, with this cycle as rim and P, Q as spokes. Otherwise let q be the last vertex in R ′ \ {x, y} which is also on R. Then we have a W 2 -subdivision with rim R[x, q]R ′ [q, x] and spokes P and R[q, y]Q.

Theorem 59. For all k ≥ 4, W k -SUBDIVISION is NP-complete.

Proof. We give the proof for k = 4 (the case for larger k is very similar). We show a reduction from 2-LINKAGE in digraphs with no big vertices in which x 1 and x 2 are sources and y 1 and y 2 are sinks.

Let D, x 1 , x 2 , y 1 , y 2 be an instance of this problem. Let D ′ be the graph obtained by adding five new vertices z, a, b, c, d and the arcs az, bz, cz, dz, ab, cd, y 2 a, bx 1 , y 1 c, and dx 2 .

Let us prove that D ′ has a W 4 -subdivision if and only if D has a 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ).

If P 1 , P 2 form the desired 2-linkage in D, then we take P 1 y 1 cdP 2 abx 1 as the rim and the four arcs az, bz, cz, dz as the spokes.

Conversely, suppose W is a subdivision of W 4 in D ′ and let C be its rim. The centre of W must be z as this is the only vertex of in-degree 4 in D ′ . Thus the four paths ending in z will end in the arcs az, bz, cz, dz, respectively. Now observe that a (and similarly c) must belong to C since otherwise the path containing az cannot be disjoint from the path containing bz (they will meet in a). Thus a is on C and then b is on C since it is the only out-neighbour of a different from z. Similarly d is on C. Hence C contains the arcs ab and cd and this implies that C contains disjoint paths from x 1 to y 1 and x 2 to y 2 respectively. Remark 60. It is not difficult to modify the proof above to a proof that F-SUBDIVISION is NP-complete whenever F is any digraph obtained from a W k with k ≥ 4 by reorienting one or more of the spokes. E.g. if the arc dz is reversed, then we replace the arcs ab and cd by arcs ax 1 , y 1 b, cx 2 , y 2 d. We leave the details to the interested reader.

From this remark and Lemmas 2, 3 and 4 we get the following corollary. Notice that the resulting digraphs may still have only one big vertex so the conclusion does not follow from Let z be a vertex in a digraph D. A triple (x 1 , x 2 , x 3 ) is F 3 -nice with respect to z in D if the following holds:

• x 3 z is an arc;

• in Dx 3 , there exist a directed (x 1 , z)-path P 1 and a directed (x 2 , z)-path P 2 which intersect only in z;

• in D -{x 3 , z}, there is a directed (x 1 , x 2 )-path Q 1 , and in D -{x 1 , z}, there is a directed

Theorem 63. A digraph contains an F 3 -subdivision with centre z if and only if there is an F 3 -nice triple with respect to z. In particular F 3 -SUBDIVISION is polynomial-time solvable.

Proof. Trivially, if D contains an F 3 -subdivision with centre z, then it contains an F 3 -nice triple (x 1 , x 2 , x 3 ) with respect to z.

Conversely, assume that D contains an F 3 -nice triple (x 1 , x 2 , x 3 ) with respect to z. Let P 1 , P 2 , Q 1 and Q 2 be the directed paths as defined in the definition of F 3 -nice triple. We may assume that (x 1 , x 2 , x 3 ) is an F 3 -nice triple (x 1 , x 2 , x 3 ) with respect to z that minimizes

, that is the sum of the lengths of these paths.

We shall prove that P 1 , P 2 , Q 1 and Q 2 are internally disjoint, implying that these paths and the arc x 3 z form an F 3 -subdivision with centre z.

a) Let us prove that Q 2 and P 1 are internally disjoint. Suppose not. Then let x ′ 2 be the last vertex on Q 2 which also belongs to

P ′ 2 are internally disjoint because P 1 and P 2 were, Q ′ 1 does not go through

(which can be a walk), and

. This contradicts the minimality of ℓ.

c) Let us prove that Q 1 and P 1 are internally disjoint. Suppose not. Then let x ′ 1 be the last vertex on Q 1 which also belongs to P 1 . The path Q 2 does not go through x ′ 1 because Q 2 and P 1 are internally disjoint. Thus (x ′ 1 , x 2 , x 3 ) is F 3 -nice with associated paths

This contradicts the minimality of ℓ.

d) Let us prove that Q 1 and P 2 are internally disjoint. Suppose not. Then let x ′ 2 be the last internal vertex on Q 1 which also belongs to

which can be a walk). This contradicts the minimality of ℓ.

e) Let us prove that Q 1 and Q 2 are internally disjoint. Suppose not. Then let x ′ 2 be the last internal vertex on Q 2 which also belongs to Q 1 . Then (x 1 , x ′ 2 , x 3 ) is a good triple with associated paths

Indeed, since P 2 and Q 1 are internally disjoint, P ′ 2 is a path, and since P 1 and Q 1 are internally disjoint, the paths P ′ 1 and P ′ 2 are also internally disjoint.

Theorem 64. For all k ≥ 5, F k -SUBDIVISION is NP-complete.

Proof. Reduction from 2-LINKAGE in digraphs with no big vertices in which x 1 and x 2 are sources and y 1 and y 2 are sinks.

Let D, x 1 , x 2 , y 1 and y 2 be an instance of this problem. Let us denote by z the centre of We claim that D k has an F k -subdivision if and only if D has a linkage from (x 1 , x 2 ) to

Clearly, if there is a linkage (P 1 , P 2 ) from (x 1 , x 2 ) to (y 1 , y 2 ) in D, then D k contains an F k -subdivision, obtained from F k by replacing the arc v 1 v 2 and v 3 v 4 by the directed paths

Suppose now that D k contains an F k -subdivision S in D k . Since z is the unique vertex with in-degree k, the centre of S ′ is necessarily z. For 1 ≤ i ≤ k, let v ′ i be the vertex corresponding to v i in S, and P i be the directed (v ′ i , z)-path in S.

Since z has in-degree exactly k in D k , the v i 's are the penultimate vertices of the P j 's,

Moreover, for i = 3 and i ≥ 5, the path P ′ j containing v i must start at v i because the unique in-neighbour of v i is v i-1 .

Hence

Let Q 1 and Q 2 be the directed (v 1 , v 2 )and (v 3 , v 4 )-paths, respectively. Necessarily, the

and its penultimate vertex is y 1 (resp. y 2 ).

Hence

Subdivision of oriented paths and cycles

Conjecture 69. If F is an oriented path or cycle, then F-SUBDIVISION is polynomial-time solvable.

Proposition 70. If P is an oriented path with at most four blocks, then P-SUBDIVISION is polynomial-time solvable.

An antidirected path is an oriented path in which every vertex has either in-degree 0 or out-degree 0.

Theorem 71. If P is an antidirected path, then P-SUBDIVISION is polynomial-time solvable.

Proof. Let P = (a 1 , . . . , a p ) be an antidirected path. By directional symmetry, we may assume that a i has indegree 0 in P if and only if i is odd.

Let D be a digraph. For a p-tuple of vertices (v 1 , . . . , v p ), we shall describe a procedure that either returns a P-subdivision, or returns that there exists no P-subdivision in which each v i is the image of a i . Then applying this procedure for all p-tuples of vertices, we obtain the desired algorithm to finding a P-subdivision.

The procedure is as follows: For all odd (resp. even) i, we remove all the arcs entering v i (resp. leaving v i ) in D. Let D ′ be the resulting digraph. Clearly, D contains a P-subdivision in which each v i is the image of a i if and only if D ′ does. In UG(D ′ ), we check if there is a path Q going through v 1 , . . . , v p in this order. This can be done by checking for a linkage from

and thus in polynomial time by Robertson and Seymour algorithm [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF].

If no such Q is found, then D ′ (and thus D) contains certainly no P-subdivision in which each v i is the image of a i .

If such a Q is found, let Q be the oriented path corresponding to Q in D ′ . Since v i is a source in D ′ when i is odd, and a sink in D ′ when i is even, the path Q has at least p -1 blocks, and so contains a subdivision of P.

Remark 72. Using the same technique, one can show that if P is an oriented path, all blocks of which have length one except possibly two consecutive blocks, then P-SUBDIVISION is polynomial-time solvable.

Concluding remarks

The following conjecture, due to Seymour (private communication, 2011) would imply a number of the results on polynomial instances in the previous sections.

Conjecture 73 (Seymour). F-SUBDIVISION is polynomial-time solvable when F is a planar digraph with no big vertices.

This conjecture would indeed be implied by the following conjecture. An arc uv in a

Conjecture 74 (Johnson et al. [START_REF] Johnson | Directed tree-width[END_REF]). For every positive integer k there exists N(k) such that the following holds: If a digraph D has directed treewidth more than N(k), then D contains a minor isomorphic to J k .

If the directed tree-width of D is bounded, then, by Theorem 46, F-SUBDIVISION can be solved in polynomial time. If, on the other hand, the directed tree-width of D is unbounded, then (if the algorithmic version of the conjecture also holds) we can find a minor isomorphic to J k for a sufficiently large k and presumably use this to realize the desired subdivision using the fact the F is planar and has no big vertices.

Conjecture 75. F-SUBDIVISION is NP-complete for every non-planar digraph F.

For any positive integer p, let us denote by C p , the class of digraphs in which all directed cycles have length at most p. Then C 1 may be seen as the class of acyclic digraphs.

Problem 76. Is k-LINKAGE polynomial-time solvable on C p ?

Thomassen proved [START_REF] Thomassen | Highly connected non-2-linked digraphs[END_REF] that for every natural number p there exists a p-strongly connected digraph D p which is not 2-linked, that is, there exists no linkage from (s Hence for every two digraphs F 1 and F 2 such that F 1 -SUBDIVISION and F 2 -SUBDIVISION have been proved to be polynomial-time solvable, it is natural to ask for the complexity of (F 1 + F 2 )-SUBDIVISION. In particular, the following problem is one of the first to study.

Problem 78. Let F 1 and F 2 be two (1, 2)-spindles, i.e. transitive tournaments of order 3.

What is the complexity of (F 1 + F 2 )-SUBDIVISION?