Jørgen Bang-Jensen

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

A Karolinna

Finding a subdivision of a digraph

Keywords: Algorithmique, programmation, logiciels et architectures NP-completeness, 2-linkage, flows, DAG and handle decompositions NP-complétude, 2-linkage, Flots, décompositions en DAG et en oreilles

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 polynomial-time 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 that can be performed in time O(n 11 ) 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.

When we move to digraphs, the situation becomes more complicated, even for the subdigraph containment relation. In this paper, by digraph we mean a simple digraph, that is a digraph with no parallel arcs nor loops. Sometimes however, multiple arcs are possible. In such cases, we write multidigraph. We rely on [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] for classical notation and concepts. A few things are in order to state here though. Unless otherwise stated the letters n and m will always denote the number of vertices and arcs (edges) of the input digraph (graph) of the problem in question. By linear time, we mean O(n + m) time. If D is a digraph, then we denote by UG(D) the underlying (multi)graph of D, that is, the (multi)graph we obtain by replacing each arc by an edge. A digraph D is connected if UG(D) is a connected graph. If xy is an arc from x to y, then we say that x dominates y. When H, H ′ are digraphs we denote by H + H ′ the disjoint union of H and H ′ (no arcs between disjoint copies of these).

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.

In this paper, we consider the following problem for a fixed digraph F.

F -SUBDIVISION

Input: A digraph D. Question: Does D contain a subdivision of F?

In [START_REF] Bang-Jensen | Finding an induced subdivision of a digraph[END_REF] the problem INDUCED-F-SUBDIVISION of finding an induced subdivision of a prescribed digraph F in a given digraph D was studied. It turns out that here there is a big difference in the complexity of the problem depending on whether or not D is an oriented graph or it may contain 2-cycles. In the later case INDUCED-F -SUBDIVISION is NP-complete for every oriented digraph F which is not the disjoint union of spiders (see definition of these digraphs below) and it was conjectured that INDUCED-F-SUBDIVISION is NP-complete unless F is the disjoint union of spiders and at most one 2-cycle. Let x 1 , x 2 ,...,x k , y 1 , y 2 ,...,y k be distinct vertices of a digraph D.Ak-linkage from (x 1 , x 2 ,...,x k ) to (y 1 , y 2 ,..., y k ) in D is a system of disjoint directed paths P 1 , P 2 ,...,P k such that P i is an (x i , y i )-path in D.

Similarly to the situation for undirected graphs, the D-SUBDIVISION problem is related to the following k-LINKAGE problem.

RR n°8024

k-LINKAGE Input: A 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?

However, contrary to graphs, unless P=NP, k-LINKAGE cannot be solved in polynomial time in general digraphs. Fortune, Hopcroft and Wyllie [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF] showed that already 2-LINKAGE is NP-complete. Using this result, we show that for lots of F, the F-SUBDIVISION problem is NP-complete. We also give some digraphs F for which we prove that F-SUBDIVISION is polynomial-time solbvable. We believe that there is a dichotomy between NP-complete and polynomial-time solvable instances.

Conjecture 1. For every digraph F, the F-SUBDIVISION problem is polynomial-time solvable or NP-complete.

To prove such a conjecture, a first idea would be to try to establish for any digraph G and subdigraph F, that if G-SUBDIVISION is NP-complete, then F-SUBDIVISION is also NP-complete, and conversely, if F-SUBDIVISION is polynomial-time solvable, then G-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 24.

v 2 AB 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 NPcompleteness 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 NP-completeness 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.W efirst give some easy brute force algorithms, then algorithms based on max 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.

2 Some general lemmas Lemma 2. Let F 1 and F 2 be two digraphs.

RR n°8024 (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 po-lynomial-time solv- able.
Proof. Let D be a digraph. We shall prove that D contains an F 1 -subdivision if and only if D + F 2 contains an

(F 1 + F 2 )-subdivision. Clearly if D contains an F 1 -subdivision S, then S + F 2 is an (F 1 + F 2 )-subdivision in D + F 2 .
Conversely, assume that D + F 2 contains an (F 1 + F 2 )-subdivision S = S 1 + S 2 with S 1 an 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 1 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 polynomial-time 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 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 1 -subdivision. 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 polynomial-time solvable.
Proof. 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. 1 A connected component of a digraph H is a connected component of UG(H).

RR n°8024

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 D. 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 F-subdivision. It follows form the fact that every vertex vcorresponding to one of F in S must be mapped onto a vertex corresponding to D in D p because max{d

+ (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 polynomial-time solvable.
3 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.

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 outarborescence.

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 out-degree 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 D. Theorem 8. Let F be a digraph. If F contains two arcs ab and cd whose endvertices are big vertices and such that (BP(F) \{ab, cd}) ∪{ad, cb} is not isomorphic to BP(F), then F-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 , y 2 be an instance of this problem. 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 claim 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 ).

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 1 , y 2 )and an (x 2 , y 1 )-path, for otherwise (BP(F) \{ab, cd}) ∪ {ad, cb} = BP(S) is isomorphic to BP(F) since S is an F-subdivsion. Hence, there is 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ).

Remark 9.

Observe that if BP(F) has two arcs ab and cd which are consecutive (i.e. b = c) or contains an antidirected path (a, b, c, d) of length 3, then (BP(F) \{ab, cd}) ∪{ad, cb} is not isomorphic to BP(F). Hence, by Theorem 8, F-SUBDIVISION is NP-complete.

Corollary 10. If F is a digraph with no small vertices, then F-SUBDIVISION is NP-complete.

Proof. If F has no small vertices, then BP(F)=F. Moreover if F does not contain two consecutives arcs, then V (F) can be partitionned into two sets A and B such that all arcs in F have tail in A and head in B. In this case, F contains an antidirected path of length 3. So by Remark 9, the F-SUBDIVISION problem is NP-complete.

For many digraphs F, the condition of Theorem 8 is verified and so F-SUBDIVISION is NP-complete. However, there are graphs that do not verifies this condition but yet 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 subdipaths 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, 4}};

• P and Q are both in-paths {b(P), b(Q)}∈{{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 verifies {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).I n 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 b(P) ≥ 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 ′ )} = {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 two blocks and the other b(P)+b(Q) -2 blocks. So {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},sob(P)=2 because (P, Q) is not bad.
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 ′ . Theorem 12. Let F be a dumbbell set. Let D 1 and D 2 be two dumbbells of F, and for i = 1, 2, let L i ,R i ,u i ,v i and P i be the left plate, right plate, left clip, right clip and bar of D i . If one of the following holds

(a) (P 1 , P 2 ) is not a bad pair, (b) L 1 ∼ = L 2 ,L 1 ∼ = R 2 ,R 1 ∼ = L 2 and R 1 ∼ = R 2 , (c) P 1 and P 2 are both directed paths, L 1 ∼ = L 2 and R 1 ∼ = R 2 , (d) P 1 is a directed path and P 2 is an out-path (resp. in-path) with two blocks and L 1 ∼ = 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 F = D 1 + D 2 . 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 ).

Clearly, if there is a 2-linkage R 1 , R 2 in D, then the union of F \{ab, cd} and the paths

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 }.N o wi nS, 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 .S o(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.
)=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 .N o w , since L 1 ∼ = L 2 ,wehaveL * 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 polynomial-time 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.

Subdivision of directed cycles

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

Proposition 15. 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 time O(n k • m).
The running time above is certainly not best possible. For example, when k = 2ork = 3, we can find lineartime algorithms.

Proposition 16. C 2 -SUBDIVISION can be solved in linear time.

RR n°8024

Proof. A subdivision of the directed 2-cycle is a directed cycle. Hence a digraph has a C 2 -subdivision 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 17. 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 3inD (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.

Dabow and Nie proved that it is FPT to decide if a graph has a cycle of length at least k.

Theorem 18 (Gabow and Nie [10,[START_REF] Gabow | Finding a long directed cycle[END_REF]). One can decide in time O(k 3k •n•m) whether a digraph contains a directed cycle of length at least k. 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.A nF-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,wefirst 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 independent directed paths P i ,1≤ i ≤ p, each P i starting in a ′ and ending in a ′ i . This can be done using a flow 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 flow algorithm. There exists such an algorithm running in time O(n 3 ). So the time complexity of the above

algorithm is O n |V (F)|+3 .
The complexity given in Proposition 20 is certainly not optimal. For example, it can be improved for spindles with paths of small lengths. Proposition 21. 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 5 ) time.

Proof. If some of the k i , say k 1 , equals 1, then finding an F-subdivision is equivalent to find p independent 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 time O(n 3 ) using flows.

If k i = 2 for all 1 ≤ i ≤ 2, then finding an F-subdivision is equivalent to find p independent 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 independent (a, b)-paths. For any pair (a, b), this can be checked in time O(n 3 ).

Subdivision of corrals

A corral is an oriented tree C such that there is a vertex r, called the root, of in-degree 0 such that Cr is the disjoint union of spiders.

Proposition 23. If C is a corral, then C-SUBDIVISION can be solved in time O n |V (C)|+2 .
Proof. The proof is similar to the one for spindles. Thus we leave it to the reader.

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 NP-complete. 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 24. 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 there 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 RR n°8024

and for each possibility we check via a max flow algorithm if there are disjoints 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 , we check if for all i, D U i (resp. V i ) contains a spider isomorphic to L i (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 D \ ( p i=1 (U i ∪V i ) \{u i , v i }) via a flow 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 exists, we proceed to the next case.

The number of possible cases is O(n |V (F)| ) and each run of the flow algorithm can be done in O(n 3 ). Hence the complexity of the algorithm is O(n |V (F)|+3 ).

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 time O(n |W |+3 ).

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 disjoint 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 iv 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 maximum flow algorithm. If these paths exist, then return the desired subdivision of W formed by the union of 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 • every vertex excepta has in-degree 1 and a has in-degree 0, and • all vertices exceptb, c and t have out-degree 1 and b and c have out-degree 0 and t has out-degree 2.

X 1 ∪ X 2 ∪ ...∪ X p is |W |-1, there are O(n | W |-1)
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 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 graph 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 ,..., c)-path of length l j and the union of the P i and

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,
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 28. 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 27 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. In the next section, we give faster algorithms to solve B(1, 2; 1)-,B(1, 2; 2)-and B(1, 3; 1)-SUBDIVISION.

RR n°8024 7 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 digraphD \ 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 tail of h and t its head. 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,ahandle 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.

Subdivision of the lollipop

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

Proposition 31. 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 29.

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 32. 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 33. 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.

Theorem 34. A robust digraph D contains a B(1, 2; 2)-subdivision if and only if D /

∈ F 1,2;2 .

Proof. Let us first prove that if D ∈ F 1,2;2 , then it contains no B(1, 2; 2)-subdivision. Suppose for a contradiction, that there is such a subdivision S. Let a and b be the left and right nodes of a subdivision of S. Then the connectivity between a and b is at least 2 in one direction. So, by construction, either (a, b)=(x, y),o r(a, b) is such that ab is a back arc. But, in both cases, the unique directed (b, a)-path is (b, a) which has length less than 2, this is a contradiction.

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 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 tail of h i is x 1 and its head 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.) Figure 3: A digraph in F 1,2;2 , which is not a double ring 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 is 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 edges, 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 duality.

(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 duality.

(vi) u and v are internal vertices of the same P j and u precedes v on P j . Since there are no multiple edges, 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 .Ifh 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 (h i , uP j yP j ′ v; vP j ′ xP j u) is a B(1, 2; 2)-subdivision.

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

RR n°8024

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 decomposition (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.

(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 ) 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 36. Let D be a digraph and C a directed cycle in D of length at least 4. Then one of the following holds:

• D contains a B (1, 3; 1)-subdivision,

• 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 handle decomposition 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 (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.

h i =(s i , s k+1 ,t i ),
(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 Proof. By induction on the number p of handles of the handle decomposition, the result holding trivially if p = 1.

(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(
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. 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, the vertices of C, we may assume that v 1 and v 3 are the origin and the terminus, respectively, of h p .I fv 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 duality, 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.No w ,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 v 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 38. 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 18. 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 36, 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 time O(n • m) 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.

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 37, D has no B(1, 3; 1)-subdivision, and we can proceed to the next robust component, or return 'no' if there none.

Classes of digraphs for which F-SUBDIVISION is polynomial-time solvable for all F

Lemma 39. 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 ).I fk -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.

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 (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.

RR n°8024

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 Theorem 40 (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.

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

Corollary 41 (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.

The algorithm given by Fortune, Hopcroft and Wyllie to solve k-LINKAGE problem has a runnng time in O(k!n k+2 ). Hence a natural question is to ask if it can be solved in time O( f (k)n c ) for some absolute constante c and arbitrary function f . In the FPT setting, it can be phrased as follows.

Problem 42. Is the following parameterized problem FPT? PARAMETERIZED ACYCLIC k-LINKAGE Input: An acyclic digraph D and 2k distinct vertices x 1 , x 2 ,...,x k , y 1 , y 2 ,...,y k . Parameter: k. Question: Is there a k-linkage from (x 1 , x 2 ,...,x k ) to (y 1 , y 2 ,...,y k ) in D?

Theorem 43 (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 39 so we have.

Theorem 44 (Johnson et al. [13]). For every digraph F, F-SUBDIVISION is polynomial-time solvable on digraphs of bounded directed tree-width.

Theorem 45 (Chudnovsky et al. [START_REF] Chudnovsky | Disjoint paths in tournaments[END_REF]). For any digraph F, F-SUBDIVISION is polynomial-time 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 .ADAG-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:

(i) V (D)= h∈V(H) W h , (ii) for all h, h ′ , h ′′ ∈ V (H),ifh ′ lies on a directed path from h to h ′′ , then W h ∩W h ′′ ⊆ W h ′ , and (iii) if (h, h ′ ) ∈ A(H), then W h ∩ W h ′ guards W ≥h ′ \ W h ,
where W ≥h ′ is the union of all W h ′′ for which there exists an (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 46 (Berwanger et al. [4], 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 DAG-width.

Digraphs of bounded DAG-width are closed under the operation in Lemma 39 so we have.

Corollary 47. For any digraph F, F-SUBDIVISION is polynomial-time solvable when restricted to the class of digraphs of bounded DAG-width.

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 cycle-transversal number and is denoted by τ(D).

Corollary 48. 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 47.

The maximum number of disjoint directed cycles in a digraph D is called the cycle-packing number and is denoted by ν(D). Clearly, ν(D) ≤ τ(D). Conversely, proving the so-called Gallai-Younger Conjecture, Reed et al. [START_REF] Reed | Packing directed circuits[END_REF] proved that τ(D) is bounded above by a function of ν(D).

Theorem 49 (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).

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 50. 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 2-cycles.

Hence, if F is the disjoint union of k 2-cycles, F-SUBDIVISION is equivalent to deciding if ν(D) ≥ k for a given digraph D. Using Theorem 49, Reed et al. [START_REF] Reed | Packing directed circuits[END_REF] proved that this can be done in polynomial time.

Theorem 51 (Reed et al. [16]). For any fixed k, deciding if a digraph D has k disjoint directed cycles is polynomialtime solvable. Equivalently, if F is the disjoint union of directed 2-cycles, then F-SUBDIVISION is polynomial-time solvable.

Remark 52. 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 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 [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF], there is no algorithm solving the problem with a running time f (k) • n O (1) . Problem 53. Let F be the disjoint union of p directed cycles of lengths k

Subdivisions of wheels and fans

The fan F k is the graph obtained from the directed path P k by adding a vertex, called 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. 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.

Corollary 56. W 2 -SUBDIVISION is solvable in time O(n • m).
Theorem 57. For all k ≥ 4,W k -SUBDIVISION is NP-complete.

RR n°8024

Proof. We give the proof for k = 4, the proof being very similar for larger k. 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 58. 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 Theorem 8.

Corollary 59. Let W ′

k ,k≥ 4 be the strongly connected digraph obtained from W k by reversing between one and k -1 spokes and let G be any digraph not containing a subdivision of W ′ k then F-SUBDIVISION and F ′ -SUBDIVISION are NP-complete, where F is obtained from W ′ k and G by adding zero or more arcs from V (W ′ k ) to V (G) and F ′ is obtained from W ′ k and G by identifying the big vertex of W ′ k with an arbitrary vertex of G.

Corollary 56 and Theorem 57 determine the complexity of W k -SUBDIVISION for all k except 3. So we are left with the following problem.

Problem 60. What is the complexity of W 3 -SUBDIVISION ?

We now turn to fans. Notice that F k is W k where one arc of the rim is deleted. Observe that F 2 is TT3 which is the (1, 2)-spindle. Thus F 2 -SUBDIVISION can be solved in O(n 4 ) time by Proposition 21. The next result shows that F 3 -SUBDIVISION is polynomial.

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 1 , x 2 , x 3 are distinct vertices of Dz;

• x 3 z is an arc;

• i n 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;

• i n D -{x 3 , z}, there is a directed (x 1 , x 2 )-path Q 1 , and in in D -{x 1 , z}, there is a directed (x 2 , x 3 )-path Q 2 .
Theorem 61. 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 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 repect 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 ℓ = ℓ(P 1 )+ℓ(P 2 )+ℓ(Q 1 )+ℓ(Q 2 ), that is the sum of the lengths of these paths.

Subdivisions of transitive tournaments

Denote by TT k the transitive tournament on k vertices. For k ≤ 3, TT k -SUBDIVISION is polynomial-time solvable because TT 1 and TT 2 are spiders and TT 3 is the (1, 2)-spindle. On the other hand, for all k ≥ 5, TT k -SUBDIVISION is NP-complete by Corollary 10. We shall now prove that TT 4 -SUBDIVISION is polynomial-time solvable.

In fact we will prove it for some classes of graphs contructed from TT 4 . For any non-negative integer, let TT 4 (p) be the digraph obtained from TT 4 with source u and sink v by adding p new vertices dominated by u and dominating v. In particular, TT 4 (0)=TT 4 . We denote by TT * 4 (p), the digraph obtained from TT 4 (p) by deleting the arc from its source u to its sink v. For simplicity, we abbreviate TT * 4 (0) in TT * 4 . We need the following definitions. Let X be a set of vertices in a digraph D. The out-section 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.

Theorem 64. For every non-negative integer p, the T T 4 (p)-SUBDIVISION problem is polynomial-time solvable.

Proof. Let D be a digraph and let u and v be two distinct vertices of D. We shall describe a polynomial-time algorithm for finding a TT 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 any polynomial-time maximum flow algorithm, we can find in D ′ a set of internally disjoint directed (u, v)-paths of maximum size. Let (P 1 ,...,P k ) denote this set. If k < p + 3, then return 'no', because in any TT 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 Subproof. Assume that |I(x)|≥2. Without loss of generality, {1, 2}⊂I(x). We shall prove that D ′ contains a TT 4 (p)-subdivision with source u and sink v.

1 ≤ i ≤ k, set Q i = P i -{u,
• Suppose first thatS - 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 Ry instead of R,wemay assume that y is the last vertex of R. Now the union of P 1 ,...,P p+3 , and R form a TT 4 (p)-subdivision.

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

RR n°8024

• Suppose now thatS + 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 -k i=1 Q i 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 paths P 2 ,...,P p+3 , RxS 1 z 1 P 1 and S 2 form a TT 4 (p)-subdivision.

• I f S - H (x) ∩ Q 1 = / 0 and S - H (x) ∩ Q 2 = / 0,
x)| = 1 for all 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 partitions. 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 TT * 4 -subdivision, and so no TT 4 (p)-subdivision. ♦

This finishes the proof of Theorem 64.

Corollary 65. For all non-negative integer p, the T T * 4 (p)-SUBDIVISION problem is polynomial-time solvable.

Proof. Observe that a graph D contains a TT * 4 (p)-subdivision with source u and sink v, if and only if the graph D ∪{uv} contains a TT 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 TT * 4 (p)-SUBDIVISION.

Subdivisions of digraphs with three vertices

Let 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 66. 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. 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.

Applying a flow algorithm, check if in Dv there are two disjoint directed paths P 1 and P 2 from {s 1 , s 2 } to {t 1 ,t 2 }. If not, then D certainly does not contain any suitable D 3 -subdivision. If yes, then check if there is a directed path Q from P 1 to P 2 or from P 2 to P 1 . If such a Q exists, then P 1 , P 2 , Q together with v and the arcs vs 1 , vs 2 ,t 1 v,t 2 v form a suitable D 3 -subdivision. If not, then no suitable D 3 -subdivision using the chosen arcs exists, because there is no vertex s ∈{s 1 , s 2 } such that there exists in Dv both a directed (s,t 1 )-path and a directed (s,t 2 )-path.

A D 3 -subdivision is clearly suitable with respect to its bulky vertex and its neighbours in this subdivision. Hence checking if there is a suitable D 3 -subdivision for every 5-tuple (v, s 1 , s 2 ,t 1 ,t 2 ) such that s 1 , s 2 are out-neighbours of v and t 1 , t 2 are out-neighbours yields a polynomial-time algorithm to decide if there is a D 3subdivision in a digraph.

Subdivision of oriented paths and cycles

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

Proposition 68. 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 69. 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 duality, 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 (v 1 , v 2 ,...,v p-1 ) to (v 2 , v 3 ,...,v p ) 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 70. Using the same technique, one can show that if P is a directed 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 71 (Seymour). F-SUBDIVISION is polynomial-time solvable when F is a planar digraph with no big vertices.

The motivation for this conjecture is the following conjecture. An arc uv in a digraph is contractible if min{d + (u), d -(v)} = 1. A minor of a digraph D is any subdigraph D of D which can be obtained from a subdigraph H of D by contracting zero or more contractible arcs of H.F o rk = 1, 2,...,k the digraph J k is obtained from the union of k directed cycles (each of length 2k) C 1 ,C 2 ,...,C k , where C i = u i,1 v i,1 u i,2 v i,2 ...u i,k v i,k u i,1 , for i = 1, 2 ...,k and paths P i , Q i , i = 1, 2 ...,k, where P i = u 1,i u 2,i ...u k,i and Q i = v k,i v k,i-1 ...v k,1 for i = 1, 2 ...,k.

Conjecture 72 (Johnson et al. [13]). For every natural number k there exist 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 44, 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 73. 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.

RR n°8024

Proposition 13 .

 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. Lemma 14. 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. Then, if yes, we check if D -A has an F-subdivision.

Problem 19 .

 19 For any fixed k, can we solve C k -SUBDIVISION in linear time? In other words, does there exists a function f such that one can decide in time O( f (k)(n + m)) whether a digraph contains a directed cycle of length at least k? 5 Polynomial-time solvable problems via flows 5.1 Subdivision of spindles Two paths are independent if they have no internal vertices in common. A (k 1 ,...,k p )-spindle is the union of p pairwise independent 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 20. If F is a spindle, then F-SUBDIVISION can be solved in time O n |V (F)|+3 .

  Hence a natural question is to ask is the following: given a spindle F and a digraph D, one can decide in timef (|V (F)|) × n c if D contains an F-subdivision,where f is an arbitrary function and c an absolute constant. This may be formulated in FPT setting as follows. Problem 22. Is the following problem fixed-paramater tractable? SPINDLE-SUBDIVISION Input: A spindle F and a digraph D. Parameter: |V (F)|. Question: Does D contain a subdivision of F?

  choices for it, and there are n choices for x, hence the algorithm runs O(n | W |) times a maximum flow algorithm. Since there is exists an O(n 3 ) algorithm for maximum flow in a network, the overall complexity is O(n |W |+3 ). Clearly, given as input a windmill W and a digraph D, deciding if D contains a W -subdivision is NP-complete because the Hamiltonian 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 )|. Question: Does D contain a subdivision of W ? 6 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),

  FORK Input: A digraph D and three distinct vertices a, b and c. RR n°8024 Question: Does D contain a fork with bottom vertex a and top vertices b and c? Lemma 27. 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.

Theorem 29 .

 29 If F is a bispindle with two forward paths and one backward path, then F-SUBDIVISION can be solved in time O(n |F|+1 • m). Proof. Let a be the left node of F and let b and c be its two out-neighbours in F. 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 27, our algorithm runs in time O(n |F|+1 • m). The complexity given in Theorem 29 is certainly not best possible. Again a natural question is to ask if given a digraph D and a bispindle F with two forward paths and one backward path, one can decide in time f (|V (F)|) × n c if D contains an F-subdivision, where f is an arbitrary function and c an absolute constant. Problem 30. Is the following problem fixed-paramater tractable? BISPINDLE-SUBDIVISION Input: A bispindle F with two forward paths and one backward path and a digraph D. Parameter: |V (F)|. Question: Does D contain a subdivision of F?

Figure 2 :

 2 Figure 2: The double ring of order 6.

1 , 3 ; 1 )

 131 -subdivision. Lemma 37. 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.

  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.

Proposition 55 .

 55 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.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.

  Proposition 21 and Theorems 61 and 62 determine the complexity of F k -SUBDIVISION for all k except 4. So we are left with the following problem.Problem 63. What is the complexity of F 4 -SUBDIVISION ?

  Hence, the subpaths of P * 1 ∩ D and P * 2 ∩ D must be two disjoint directed paths in D, with origins in {x 1 , x 2 } and terminus in {y 1 , y 2 }, for otherwise b(P

* 1 )+b(P * 2 ) > b(P 1 )+b(P 2 ). Let P ′ 1 and P ′ 2 be the oriented paths obtained from P 1 and P 2 by replacing ab and cd by ad and cb.B y construction, if there is no 2-linkage from (x 1 , x 2 ) to (y 1 , y 2 ) in D, then P * 1 and P * 2 consist in a P ′ 1 -subdivision and a P ′ 2 -subdivision, and so {b(P ′ 1 ), b(P ′ 2 )} = {b(P * 1 ), b(P * 2 )}. RR n°8024 (a) If (P 1 , P 2 ) 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 * 2

  1 , k 2 ,...k p , respectively. Is F-SUBDIVISION polynomial? Theorem 54. (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 49. 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 17. 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. D contains a (C 2 + C 3 )-subdivision if and only if D ′ contains two disjoint directed cycles. Proof. 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 49.

	Claim 54.1.

  the proof is similar to the previous case by directional duality.Assume now that |I(x)| < 2 for all x ∈ V (H). Then, by Claim 64.1, |I(

RR n°8024

Acknowledgement

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

supported by ANR Blanc AGAPE and CAPES/Brazil.

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 1 . Then (x 2 , x ′ 2 , x 3 ) is F 3 -nice by the choice of paths P ′ 1 = P 2 ,

. Indeed, P ′ 1 and P ′ 2 are internally disjoint because P 1 and P 2 were, Q ′ 1 does not go through x 3 nor z, because Q 2 is a directed (x 2 , x 3 )-path in Dz, and Q ′ 2 does not go through x 2 nor z,for the same reason. This contradicts the minimality of ℓ.

b) Let us prove that Q 2 and P 2 are internally disjoint. Suppose not. Then let x ′ 2 be the last vertex on Q 2 which also belongs to P 2 . One easily verifies that (x 1 , x ′ 2 , x 3 ) is F 3 -nice by the choice of paths

(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.

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

) 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 62. 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 F k and by (v 1 , v 2 ,...,v k ) the directed path F kz. Let D k be the digraph obtained from the disjoint union of D and F k by removing the arcs v 1 v 2 and v 3 v 4 and adding the arcs v 1 x 1 , y 1 v 2 , v 3 x 2 and y 2 v 4 .

We claim that D k has an F k -subdivision if and only if D has a linkage from (x 1 , x 2 ) to (y 1 , y 2 ).

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 v 1 x 1 P 1 y 1 v 2 and v 3 x 2 P 2 y 2 v 4 , respectively.

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

Since z has in-degree exactly k in D k , the v i 's are the pernultimate vertices of the P j 's, each v i on a different

Moreover, for i = 3 and i ≥ 5, the path

and (v 3 , v 4 )-paths, respectively. Necessarily, the second vertex of Q 1 (resp. Q 2 )i sx 1 , (resp. x 2 ) and its penultimate vertex is y 1 (resp. y 2 ). Hence

Problem 74. 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 1 , s 2 ) to (t 1 ,t 2 ) for some choice of distinct vertices s 1 , s 2 ,t 1 ,t 2 of D p .

Problem 75. Let F be a fixed digraph. Does there exists k F such that every k F -strongly connected digraph contains an F-subdivision or at least such that F-SUBDIVISION is polynomial-time solvable when restricted to k F -strongly connected digraphs? Note that if F 1 -SUBDIVISION and F 2 -SUBDIVISION are both polynomial-time solvable, then (F 1 + F 2 )-SUBDIVISION is sometimes polynomial-time solvable and sometimes NP-complete. For example, if F 1 is the disjoint union of spiders and F 2 -SUBDIVISION is polynomial-time solvable, then (F 1 + F 2 )-SUBDIVISION is polynomial time solvable. On the other hand, assume that F 1 and F 2 are (1, 2, 2)-spindles. Then by Proposition 21, F 1 -SUBDIVISION and F 2 -SUBDIVISION are both polynomial-time solvable, but according to Theorem 8, (F 1 + F 2 )-SUBDIVISION is NP-complete.

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 complexty of (F 1 + F 2 )-SUBDIVISION. In particular, the following problem is one of the first to study. Problem 76. 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?