Júlio Araújo

Victor A Campos
email: campos@lia.ufc.br

Ana Karolinna
email: karolmaia@lia.ufc.br

Ignasi Sau
email: ignasi.sau@lirmm.fr

Ana Silva
email: anasilva@mat.ufc.br.

On the complexity of finding internally vertex-disjoint long directed paths *

Keywords: 1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems, G.2.2 Graph Theory digraph subdivision, spindle, parameterized complexity, FPT algorithm, representative family, complexity dichotomy

For two positive integers k and , a (k × )-spindle is the union of k pairwise internally vertexdisjoint directed paths with arcs each between two vertices u and v. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed ≥ 1, finding the largest k such that an input digraph G contains a subdivision of a (k × )-spindle is polynomialtime solvable if ≤ 3, and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.

Introduction

A subdivision of a digraph F is a digraph obtained from F by replacing each arc (u, v) of F by a directed (u, v)-path. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains as a subdigraph a subdivision of a spindle, defined by Bang-Jensen et al. [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF] as follows. For k positive integers vertices s and t, finding the maximum number of internally vertex-disjoint (s, t)-paths whose lengths are at most or exactly equal to a fixed constant , and achieved dichotomies for both cases. Note that the problem we consider corresponds to a constraint of type 'at least' on the lengths of the desired paths. Hence, Theorem 1 together with the results of Itai et al. [START_REF] Itai | The complexity of finding maximum disjoint paths with length constraints[END_REF] provide a full picture of the complexity of finding a maximum number of length-constrained internally vertex-disjoint directed (s, t)-paths. For future work, one could consider mixed constraints, i.e., some of the paths of type 'at least', some 'at most', and some 'exactly equal'.

Due to the apparent hardness of finding an FPT algorithm for a general spindle, we decided to place special emphasis on finding subdivisions of spindles with exactly two paths, which we call 2-spindles. We mention that the existence of subdivisions of 2-spindles has attracted some interest in other contexts. Indeed, Benhocine and Wojda [START_REF] Benhocine | On the existence of specified cycles in a tournament[END_REF] showed that a tournament on n ≥ 7 vertices always contains a subdivision of an ( 1 , 2 )-spindle such that 1 + 2 = n. And more recently, Cohen et al. [START_REF] Cohen | Subdivisions of oriented cycles in digraphs with large chromatic number[END_REF] showed that a strongly connected digraph with chromatic number Ω(( 1 + 2 ) 4 ) contains a subdivision of an ( 1 , 2 )-spindle, and this bound was subsequently improved to Ω(( 1 + 2 ) 2 ) by Kim et al. [START_REF] Kim | Cycles with two blocks in k-chromatic digraphs[END_REF], who also provided improved bounds for Hamiltonian digraphs.

We consider two problems concerning the existence of subdivisions of 2-spindles. The first one is, given an input digraph G, find the largest integer such that G contains a subdivision of an ( 1 , 2 )-spindle with min{ 1 , 2 } ≥ 1 and 1 + 2 = . We call this problem Max (•, •)-Spindle Subdivision, and we show the following results.

Theorem 2. Given a digraph G and a positive integer , the problem of deciding whether there exist two strictly positive integers 1 , 2 with 1 + 2 = such that G contains a subdivision of an ( 1 , 2 )-spindle is NP-hard and FPT parameterized by . The running time of the FPT algorithm is 2 O( ) • n O (1) , which is asymptotically optimal unless the ETH fails. Moreover, the problem does not admit polynomial kernels unless NP ⊆ coNP/poly.

The second problem is, for a fixed strictly positive integer 1 , given an input digraph G, find the largest integer 2 such that G contains a subdivision of an ( 1 , 2 )-spindle. We call this problem Max ( 1 , •)-Spindle Subdivision, and we show the following results. Theorem 3. Given a digraph G and two integers 1 , 2 with 2 ≥ 1 ≥ 1, the problem of deciding whether G contains a subdivision of an ( 1 , 2 )-spindle can be solved in time 2 O( 2) • n O( 1 ) . When 1 is a constant, the problem remains NP-hard and the running time of the FPT algorithm parameterized by 2 is asymptotically optimal unless the ETH fails. Moreover, the problem does not admit polynomial kernels unless NP ⊆ coNP/poly.

The hardness results of Theorems 2 and 3 are based on a simple reduction from Directed Hamiltonian Cycle. Both FPT algorithms, which are our main technical contribution, are based on the technique of representative families in matroids introduced by Monien [START_REF] Monien | How to find long paths efficiently[END_REF], and in particular its improved version recently presented by Fomin et al. [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF]. The FPT algorithm of Theorem 3 also uses the color-coding technique of Alon et al. [START_REF] Alon | Color-coding[END_REF] as a subroutine.

Finally, we consider the case where the input digraph G is acyclic. We prove the following result by using a standard dynamic programming algorithm. Theorem 4. Given an acyclic digraph G and two positive integers k, , the problem of deciding whether G contains a subdivision of a (k × )-spindle can be solved in time

O( k • n 2k+1 ).
The above theorem implies, in particular, that when k is a constant the problem is polynomial-time solvable on acyclic digraphs, which generalizes the fact that Longest Path, which corresponds to the case k = 1, is polynomial-time solvable on acyclic digraphs (cf. [START_REF] Sedgewick | Algorithms[END_REF]).

XX:4

On the complexity of finding internally vertex-disjoint long directed paths

As observed by Bang-Jensen et al. [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF], from the fact that the k-Linkage problem is in XP on acyclic digraphs [START_REF] Metzlar | Disjoint paths in acyclic digraphs[END_REF], it easily follows that finding a subdivision of a general digraph F is in XP on DAGs parameterized by |V (F )|. Motivated by this, we prove two further hardness results about finding subdivisions of spindles on DAGs. Namely, we prove that if F is the disjoint union of (2 × 1)-spindles, then finding a subdivision of F is NP-complete on planar DAGs, and that if F is the disjoint union of a (k 1 × 1)-spindle and a (k 2 × 1)-spindle, then finding a subdivision of F is W [START_REF] Alon | Color-coding[END_REF]-hard on DAGs parameterized by k 1 + k 2 . These two results should be compared to the fact that finding a subdivision of a single (k × 1)-spindle can be solved in polynomial time on general digraphs by a flow algorithm.

Organization of the paper. In Section 2 we provide some definitions about (di)graphs, parameterized complexity, and matroids. In Section 3 we prove Theorem 1, and in Section 4 we prove Theorem 2 and Theorem 3. In Section 5 we focus on acyclic digraphs and we prove, in particular, Theorem 4. In Section 6 we present some open problems for further research.

Preliminaries

Graphs and digraphs. We use standard graph-theoretic notation, and we refer the reader to the books [START_REF] Diestel | Graph Theory[END_REF] and [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] for any undefined notation about graphs and directed graphs, respectively.

A (multi-)directed graph G, or just (multi-)digraph, consists of a non-empty set V (G) of elements called vertices and a finite (multi)set A(G) of ordered pairs of distinct vertices called arcs. All our positive results hold even for digraphs where multiple arcs between the same pair of vertices are allowed. We denote by (u, v) an arc from a vertex u to a vertex v. Vertex u is called the tail and vertex v is called the head of an arc (u, v), and we say that (u, v) is an arc outgoing from u and incoming at v.

For a vertex v in a digraph G, we let

N + G (v) = {u ∈ V (G) \ {v} : (v, u) ∈ A(G)}, N - G (v) = {w ∈ V (G) \ {v} : (w, v) ∈ A(G)}, and N G (v) = N + G (v) ∪ N - G (v)
, and we call these sets the out-neighborhood, in-neighborhood, and neighborhood of v, respectively. The out-degree (resp. in-degree) of a vertex v is the number of arcs outgoing from (resp. incoming at) v, and its degree is the sum of its out-degree and its in-degree. In all these notations, we may omit the subscripts if the digraph G is clear from the context.

A

subdigraph of a digraph G = (V, A) is a digraph H = (V , A ) such that V ⊆ V and A ⊆ A. Given vertices u, v ∈ V , a (u,v)-path G is a sequence (u = w 1 , . . . , w q = v
) such that (w i , w i+1 ) ∈ A for every i ∈ {1, . . . , q -1}. The length of a path is its number of arcs, and by an -path we denote a path of length . A directed acyclic graph, or DAG for short, is a digraph with no directed cycles. It is easy to prove that a digraph G is a DAG if and only if there exists a total ordering of V (G), called a topological ordering, so that all arcs of G go from smaller to greater vertices in this ordering.

For two positive integers k and , a (k × )-spindle is the union of k pairwise internally vertex-disjoint directed (u, v)-paths of length between two vertices u and v, which are called the endpoints of the spindle. More precisely, u is called the tail and v the head of a spindle. A 2-spindle is any ( 1 , 2 )-spindle with 1 , 2 ≥ 1.

For an undirected graph G, we denote by {u, v} an edge between two vertices u and v. A matching in a graph is a set of pairwise disjoint edges. A vertex v is saturated by a matching M if v is an endpoint of one of the edges in M . In that case, we say that v is M -saturated. Given two matchings M and N in a graph, we let M N denote their symmetric difference, that is,

M N = (M \ N ) ∪ (N \ M ).
Parameterized complexity. We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions. A parameterized problem is a decision problem whose instances are pairs (x, k) ∈ Σ * × N, where k is called the parameter. A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f , and a constant c such that given an instance I = (x, k), A (called an FPT algorithm) correctly decides whether I ∈ L in time bounded by f (k) • |I| c . A parameterized problem is slice-wise polynomial (XP) if there exists an algorithm A and two computable functions f, g such that given an instance I = (x, k), A (called an XP algorithm) correctly decides whether I ∈ L in time bounded by f (k) • |I| g (k) .

Within parameterized problems, the class W [START_REF] Alon | Color-coding[END_REF] may be seen as the parameterized equivalent to the class NP of classical optimization problems. Without entering into details (see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF] for the formal definitions), a parameterized problem being W[1]-hard can be seen as a strong evidence that this problem is not FPT. The canonical example of W [START_REF] Alon | Color-coding[END_REF]-hard problem is Independent Set parameterized by the size of the solution. To transfer W [START_REF] Alon | Color-coding[END_REF]-hardness from one problem to another, one uses a parameterized reduction, which given an input I = (x, k) of the source problem, computes in time f (k) • |I| c , for some computable function f and a constant c, an equivalent instance I = (x , k ) of the target problem, such that k is bounded by a function depending only on k. An equivalent definition of W[1]-hard problem is any problem that admits a parameterized reduction from Independent Set parameterized by the size of the solution.

Matroids.

A pair M = (E, I), where E is a ground set and I is a family of subsets of E, is a matroid if it satisfies the following three axioms:

1. ∅ ∈ I. 2. If A ⊆ A and A ∈ I, then A ∈ I. 3. If A, B ∈ I and |A| < |B|, then there is e ∈ B \ A such that A ∪ {e} ∈ I.
The sets in I are called the independent sets of the matroid. An inclusion-wise maximal set of I is called a basis of the matroid. Using the third axiom, it is easy to show that all the bases of a matroid M have the same size, which is called the rank of M. A pair M = (E, I) over an n-element ground set E is called a uniform matroid if I = {A ⊆ E : |A| ≤ k} for some for constant k. For a broader overview on matroids, we refer to [START_REF] Oxley | Matroid theory[END_REF].

For a positive integer k, we denote by [k] the set of all integers i such that 1 ≤ i ≤ k. Throughout the article, unless stated otherwise, we let n denote the number of vertices of the input digraph of the problem under consideration.

Complexity dichotomy in terms of the length of the paths

In this section we focus on the two natural optimization versions of finding subdivisions of spindles mentioned in the introduction, namely Max (k × •)-Spindle Subdivision and Max (• × )-Spindle Subdivision.

It is easy to prove that the first problem is NP-hard for any integer k ≥ 1, by a simple reduction from Longest Path.

Theorem 5. Let k ≥ 1 be a fixed integer. The Max (k × •)-Spindle Subdivision problem is NP-hard.
Proof. We provide a polynomial reduction from the Longest Path problem on general digraphs, which is NP-hard as it generalizes Hamiltonian Path [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]. For k = 1, Max (k × •)-Spindle Subdivision is exactly the Longest Path problem, and the result follows. For k > 1, let G be an instance of Longest Path with n vertices, and we build an instance

XX:6

On the complexity of finding internally vertex-disjoint long directed paths G of Max (k × •)-Spindle Subdivision as follows. We start with G and we add to it two vertices s and t together with k -1 internally vertex-disjoint paths of length n + 1 between them; then we add an arc from s to every vertex of G, and an arc from every vertex of G to t. Let G be the obtained graph. We claim that G has a path on vertices if and only if G has a subdivision of a (k, + 1)-spindle. Indeed, if G has a (u, v)-path P on vertices, then the k -1 disjoint (s, t)-paths together with the (s, t)-path going through P form a subdivision of a (k, + 1)-spindle in G . Conversely, suppose that S is a subdivision of a (k, + 1)-spindle in G with tail u and head v. If u = s and v = t, then the intermediate part of one of the k (s, t)-paths must be entirely contained in G, thus defining a path in G of length -1 (hence on vertices). Otherwise, because s is a source and t is a sink, one can verify that the intermediate part of each of the k (u, v)-paths is contained in G, yielding in particular a path on vertices in G.

We now present the complexity dichotomy for the second problem, in order to prove Theorem 1. We start with the hardness result. For every i ∈ [n], we add to G three vertices a i , b i , c i , corresponding to the elements in the sets A, B, C, respectively. Let H be the digraph with vertices x 0 , x 1 , y 0 , y 1 , z 0 , z 1 , a, b, c and arcs (x 0 , x 1 ), (x 1 , a), (x 1 , y 0 ), (y 0 , y 1 ), (y 1 , b), (x 0 , z 0 ), (z 0 , z 1 ), (z 1 , c) (see Figure 2(a)). For every triple T ∈ T , with T = (a i , b j , c p ), we add to G a copy of H and we identify vertex a with a i , vertex b with b j , and vertex c with c p . Finally, we add a new vertex s that we connect to all other vertices introduced so far, and another vertex t to which we connect all other vertices introduced so far except s. The constructed digraph G is easily seen to be a DAG. Indeed, we can define a topological ordering of V (G) so that all arcs go from left to right as follows. We select s (resp. t) as the leftmost (resp. rightmost) vertex. We divide the remaining vertices of G into two blocks. On the right, we place all the vertices {a i , b i , c i : i ∈ [n]}, and we order them arbitrarily. On the left, we place the remaining vertices of G, which we also order arbitrarily, except that for every triple T ∈ T , we order the vertices in its copy of H, distinct from a, b, c, such that x 0 < x 1 < y 0 < y 1 < z 0 < z 1 holds. One can check that, with respect to this ordering, all the arcs of G go from left to right.

a x 1 x 0 y 0 y 1 b z 0 z 1 c (a) a i x 1 x 0 y 0 y 1 b j z 0 z 1 c p (b) a i x 1 x 0 y 0 y 1 b j z 0 z 1 c p (c)
Note that |V (G)| = 3n + 6m + 2, and since each path in a (k × 4)-spindle has at least 3 internal vertices, we get that the largest possible integer k for which G contains a subdivision of a (k × 4)-spindle is k * := n + 2m. We claim that (A, B, C, T ) is a Yes-instance of 3-Dimensional Matching if and only if G contains a subdivision of a (k * × 4)-spindle.

Suppose first that (A, B, C, T ) is a Yes-instance, and let T ⊆ T be a solution. We proceed to define a set P of n + 2m vertex-disjoint 2-paths in G \ {s, t}, which together with s and t yield the desired spindle. For every T ∈ T , with T = (a i , b j , c p ), we add to P the three paths (x 0 , x 1 , a i ), (y 0 , y 1 , b j ), and (z 0 , z 1 , c p ) (see the thick arcs in Figure 2(b)). On the other hand, for every T ∈ T \ T , with T = (a i , b j , c p ), we add to P the two paths (x 1 , y 0 , y 1 ) and (x 0 , z 0 , z 1 ) (see the thick arcs in Figure 2(c)). Since T is a solution of 3-Dimensional Matching, it holds that |T | = n, and thus

P = 3n + 2(m -n) = n + 2m, as required.
Conversely, suppose that G contains a subdivision of a (k * × 4)-spindle S. First, note that each u ∈ V (G) \ (A ∪ B ∪ C ∪ {s, t}) has in-degree at most two and out-degree at most three. Also, each d i ∈ A ∪ B ∪ C has in-degree equal to one plus the number of triples it is involved in, which is at most m + 1, and out-degree at most one. Therefore, we get that s and t are the only vertices in G with in-degree and out-degree at least k * , respectively, hence they must be the endpoints of S. Since |V (G) \ {s, t}| = 3k * , it follows that S \ {s, t} consists of a collection P of k * vertex-disjoint 2-paths that covers all the vertices in V (G) \ {s, t}. Let H be the subdigraph in G associated with an arbitrary triple T ∈ T , and consider P ∩ H. By construction of H, it follows that if P ∩ H is not equal to one of the configurations corresponding to the thick arcs of Figure 2 For a general > 4, we define the digraph G in the same way, except that we subdivide the arcs outgoing from s exactly -4 times. The rest of the proof is essentially the same, and the result follows.

Note that, in the above hardness result, if we drop the hypothesis that the input digraph is a DAG, a simple NP-hardness reduction can be obtained directly from the problem of packing a maximum number of vertex-disjoint P 3 's in a directed graph [START_REF] Brewster | Packing paths in digraphs[END_REF].

We now turn to the cases that can be solved in polynomial time. We first need some ingredients to deal with the case = 3, which is the most interesting one. Let G be a digraph and let X and Y be two subsets of V (G). We say that a (simple) path P is directed from X to Y if P is a directed path with first vertex x and last vertex y such that x ∈ X and y ∈ Y . The path P is nontrivial if its endpoints are distinct.

The following proposition will be the key ingredient in the proof of Theorem 8. Its proof is inspired by similar constructions given by Schrijver [START_REF] Schrijver | A Short Proof of Mader's S-Paths Theorem[END_REF] on undirected graphs and by Kriesell [START_REF] Kriesell | Disjoint A-paths in digraphs[END_REF] on directed graphs, usually called vertex splitting procedure (see [2, Section 5.9]). In fact, the conclusion of Proposition 7 can be also derived as a corollary of the main result in [START_REF] Kriesell | Disjoint A-paths in digraphs[END_REF], noting that a polynomial-time algorithm can be extracted from that proof. We present a simpler proof here for completeness.

Proposition 7.

Let G be a digraph and let X and Y be two subsets of V (G). The maximum number of vertex-disjoint directed nontrivial paths from X to Y can be computed in polynomial XX:8

On the complexity of finding internally vertex-disjoint long directed paths time.

Proof. Let G be the undirected graph built from G as follows. The vertex set of G is obtained from V (G) by adding a copy v of each vertex v not in X ∪ Y . We build the edge set of G starting from the empty set as follows. For every vertex v not in X ∪ Y , add the edge {v, v }. For each arc (u, v) in G, we add the edge {u, v} if v ∈ X ∪ Y and the edge {u, v } otherwise. See Figure 3(a)-(b) for an example.

u 1 v 1 v 2 v 3 u 2 u 3 u 4 G (b) (c) (a) u 1 u 2 u 3 u 4 v 2 v 2 v 2 G v 1 v 1 v 3 v 3 v 2 v 2 v 2 G v 1 v 1 v 3 v 3 u 1 u 2 u 3 u 4

Claim 1. The digraph G contains a family of k vertex-disjoint directed nontrivial paths from X to Y if and only if G has a matching of size

k + |V (G) \ (X ∪ Y )|.
Proof of the claim. Let P be a family of k vertex-disjoint directed nontrivial paths from X to Y in G. If P ∈ P is a path between x ∈ X and y ∈ Y that contains an internal vertex w in X, then the set P obtained from P by removing P and adding P , the subpath of P between w and y, has the same cardinality as P and also contains only vertex-disjoint directed nontrivial paths, since w is internal, i.e., w = y. A similar argument also holds when w ∈ Y , hence we can suppose that each path in P has no internal vertices in X ∪ Y . Observe that we can therefore assume that G has no arcs to a vertex in X \ Y or from a vertex in Y \ X. Let U be the subset of vertices of V (G) \ (X ∪ Y ) that are not in a path in P.

We build a matching M of G starting with M = {{u, u } : u ∈ U } as follows. For every arc (u, v) used in some path of P, we add to M either {u, v} if v ∈ X ∪ Y , or {u, v } otherwise (see Figure 3(c)). Note that M is indeed a matching, as vertices in X ∪ Y appear in at most one arc on a path in P. For a vertex v not in X ∪ Y , v appears at most once as an internal vertex in a path P of P. Therefore, it appears in exactly two arcs of P and exactly once in an arc to v and once in an arc from v.

We now claim that the number of

M -saturated vertices in G is 2(k + |V (G) \ (X ∪ Y )|). This claim implies that M has k + |V (G) \ (X ∪ Y )| edges.
To prove this claim, first note that all vertices in V (G) \ (X ∪ Y ) are saturated. Indeed, if v is in U , then both v and v are initially saturated. Otherwise, v is an internal vertex of a path in P and is contained in two edges that saturate both v and v . To conclude, note that every path in P contains exactly two vertices in X ∪ Y , namely its endpoints, and, therefore, saturates exactly two

vertices of X ∪ Y in G . Now, let M be a matching of G of size k + |V (G) \ (X ∪ Y )|. Let N be the matching {{v, v } : v ∈ V (G) \ (X ∪ Y )} and H = G[M N ],
where denotes the symmetric difference. Since |M | = k + |N |, H contains at least k components with more edges in M than in N . We claim that from these components we can obtain k vertex-disjoint nontrivial paths in G.

To prove this claim, let C be a component of H with more edges in M than in N . Since C has more edges in M , then it is a path alternating between edges of M and N that starts and ends with an edge of M , its endpoints are N -unsaturated and its internal vertices are N -saturated. Thus, the endpoints of C are its only vertices in X ∪ Y . Also note that if a vertex w of V (C) ∩ V (G) is not in X ∪ Y , then both w and w are in C and neither w nor w appear in any other component of H.

Let u and v be the endpoints of C and the set W of internal vertices of C that are also in V (G) be {w 1 , . . . , w }. Note that u = v as C contains at least one edge in M . If W = ∅, then uv is an edge of G and assume the edge {u, v} is directed in G from u to v. If W = ∅, then assume the transversal of C from u to v visits the vertices in the order u, w 1 , w 1 , w 2 , w 2 , . . . , w , w , v. In both cases, note that u, w 1 , . . . , w , v is the transversal of a directed path from u to v in G. Since G has no edge leaving a vertex of Y \ X and no edge going into a vertex of X \ Y , then u ∈ X and v ∈ Y .

Claim 1 tells us that we can obtain a maximum number of vertex-disjoint nontrivial paths from X to Y in G by finding a maximum matching in the graph G , which can be done in polynomial time [START_REF] Diestel | Graph Theory[END_REF]. The proposition follows.

We are now ready to prove the main algorithmic result of this section. Theorem 8. Let ≤ 3 be a fixed positive integer. Then, the Max (• × )-Spindle Subdivision problem can be solved in polynomial time.

Proof. If = 1, then the problem can be solved just by computing a maximum flow with unit capacities between every pair of vertices of the input digraph, which can be done in polynomial time [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. If = 2, we use the same algorithm, except that for every pair of vertices we first delete all the arcs between them before computing a maximum flow, as the paths of length one are the only forbidden ones in a subdivision of a (k × 2)-spindle.

Let us now focus on the case = 3. We first guess a pair of vertices s and t of V (G) as candidates for being the tail and head of the desired spindle, respectively, and we delete the arcs between s and t, if any. The crucial observation is that the largest integer k such that G contains a (k × 3)-spindle having s and t as tail and head, respectively, equals the maximum number of vertex-disjoint directed nontrivial paths from N + (s) to N -(t) in the digraph G \ {s, t}. Now the result follows directly by applying the polynomial-time algorithm given by Proposition 7 with input graph G \ {s, t}, X = N + (s), and Y = N -(t).

We now prove a generalization of the result given in Theorem 8, using similar techniques. Theorem 9. Given a digraph G and three non-negative integers k 1 , k 2 , k 3 , let α be the sequence containing k 1 1's, followed by k 2 2's, followed by k 3 3's (for instance, for

k 1 = k 2 = k 3 = 2, α = (1, 1, 2, 2, 3, 3)).
Then, deciding whether G contains a subdivision of an α-spindle can be solved in polynomial time.

Proof. We iterate on pairs of vertices s and t in G to decide if the desired spindle exists with tail s and head t. From now on, we consider a fixed pair of vertices s and t. If an α-spindle subdivision exists with tail s and head t, let S be one such subdivision.

Let p be the number of arcs with tail s and head t. Note that if S exists, it can use at most min{p, k 1 } arcs between s and t. In fact, we can assume S uses exactly min{p, k 1 } arcs between s and t as, otherwise, there is a 1-path which was subdivided and can be changed to an unused arc from s to t. All other 1-paths of the spindle must have been subdivided and have length at least two in S. Therefore, S exists if and only if there is a subdivision of an α -spindle with tail s and head t, where α consists of k 2 + k 1 -min{p, k 1 } 2's, followed by k 3 3's. So, from now on assume k 1 = 0.

Let X = N + (s), Y = N -(t), and H be obtained from G by removing s and t. Observe that S exists if and only if there are k 2 + k 3 paths from X to Y in H such that at most k 2 of these paths are trivial. For W ⊆ X ∩ Y , let G W be the graph built in Proposition 7 from H -W to find paths from X \ W to Y \ W . We build G from G ∅ by adding a set N of k 2 new vertices and adding an edge from every vertex in N to every vertex in X ∩ Y . We claim that S exists if and only if G has a matching of size k 2 + k 3 + |V (H) \ (X ∪ Y )|. Note that the theorem follows from the proof of this claim as we can build G and find a maximum matching in it in polynomial time [START_REF] Diestel | Graph Theory[END_REF].

Let

W ⊆ X ∩ Y . Note that G W = G ∅ -W by construction. Furthermore, Claim 1 states that a matching in G W of size k + |V (H) \ (X ∪ Y )| exists if and only if there are k vertex-disjoint directed nontrivial paths from X \ W to Y \ W in H \ W .
Let first M be a matching in G and let W be the set of vertices of

X ∩ Y matched to vertices in N . Note that |W | ≤ |N | = k 2 . Now, let M be the matching of size |M | -|W | obtained from the edges of M in G W . From Claim 1, M has size at least k 2 + k 3 -|W | + |V (H) \ (X ∪ Y )| if and only if there is a collection of k 2 + k 3 -|W | vertex-disjoint directed nontrivial paths from X \ W to Y \ W in H \ W ,

and this happens if and only if M has size at least

k 2 + k 3 + |V (H) \ (X ∪ Y )|.
We can find the desired number of paths by choosing |W | trivial paths using the vertices of W .

Conversely, let P be a collection of k 2 + k 3 paths from X to Y in H such that at most k 2 of these paths are trivial. Let W be the set of vertices of X ∩ Y which are in trivial paths of P and note that

|W | ≤ k 2 . Since P contains k 2 + k 3 -|W | nontrivial paths from X \ W to Y \ W in H \ W , Claim 1 tells us that G W has a matching M of size k 2 + k 3 -|W | + |V (H) \ (X ∪ Y )|. We find a matching in G of size k 2 + k 3 + |V (H) \ (X ∪ Y )| from M
by matching the vertices of W arbitrarily to vertices of N .

Finding subdivisions of 2-spindles

In this section we focus on finding subdivisions of 2-spindles, and we prove Theorem 2 and Theorem 3. We prove the negative and the positive results of both theorems separately. Namely, we provide the hardness results in Section 4.1 and we focus on the FPT algorithms in Section 4.2.

Hardness results

We start by proving the NP-hardness results.

Proposition 10. The Max (•, •)-Spindle Subdivision problem is NP-hard. For every fixed integer 1 ≥ 1, the Max ( 1 , •)-Spindle Subdivision problem is NP-hard.
Proof. For both problems, we present a reduction from the Directed Hamiltonian (s, t)-Path problem, which consists in, given a digraph G and two vertices s, t ∈ V (G), deciding whether G has an (s, t)-path that is Hamiltonian. This problem is easily seen to be NPhard by a simple reduction from Directed Hamiltonian Cycle, which is known to be NP-hard [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]: given an instance G of Directed Hamiltonian Cycle, construct from G an instance G of Directed Hamiltonian (s, t)-Path by choosing an arbitrary vertex v ∈ V (G) and splitting it into two vertices s and t such that s (resp. t) is incident to exactly those arcs in G that were outgoing from (resp. incoming at) v.

We first prove the hardness of Max (•, •)-Spindle Subdivision. Given an instance G of Directed Hamiltonian (s, t)-Path, with |V (G)| = n, build an instance G of Max (•, •)-Spindle Subdivision as follows. Start from G, and delete all the arcs incoming at s or outgoing from t, if any. Finally, add a new vertex v and arcs (s, v) and (v, t). We claim that G has a Hamiltonian (s, t)-path if and only if G contains a subdivision of an ( 1 , 2 )spindle with min{ 1 , 2 } ≥ 1 and 1 + 2 = n + 1. Assume first that G has a Hamiltonian (s, t)-path P . Then G contains a (2, n -1)-spindle defined by the 2-path (s, v, t) together with the Hamiltonian (s, t)-path P . Conversely, assume that G contains a subdivision S of an ( 1 , 2 )-spindle with min{ 1 , 2 } ≥ 1 and 1 + 2 = n + 1. Suppose that the newly added vertex v ∈ V (G ) does not belong to S, which implies that |V (S)| ≤ |V (G)| = n. Since an ( 1 , 2 )-spindle contains exactly 1 + 2 vertices, it follows that |V (S)| ≥ 1 + 2 = n + 1, a contradiction to the previous sentence. Therefore, v ∈ V (S) and so (s, v, t) is one of the two paths of S. Thus, the remaining path of S is an (s, t)-path of length n -1 in G, that is, a Hamiltonian (s, t)-path in G.

We now prove the hardness of Max ( 1 , •)-Spindle Subdivision for every fixed integer

1 ≥ 1. Given an instance G of Directed Hamiltonian (s, t)-Path, with |V (G)| = n, build an instance G of Max ( 1 , •)-
Björklund et al. [START_REF] Björklund | Approximating longest directed paths and cycles[END_REF] showed that assuming the Exponential Time Hypothesis1 (ETH) of Impagliazzo et al. [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF], the Directed Hamiltonian Cycle problem cannot be solved in time 2 o(n) . This result together with the proof of Proposition 10 directly imply the following two results assuming the ETH, claimed in Theorem 2 and Theorem 3, respectively. The first one is that, given a digraph G and a positive integer , the problem of deciding whether there exist two strictly positive integers 1 , 2 with 1 + 2 = such that G contains a subdivision of an ( 1 , 2 )-spindle cannot be solved in time 2 o( ) • n O (1) . The second one is that, given a digraph G and two integers 1 , 2 with 2 ≥ 1 ≥ 1, the problem of deciding whether G contains a subdivision of an ( 1 , 2 )-spindle cannot be solved in time

2 o( 2) • n O( 1 ) .
Concerning the existence of polynomial kernels, it is easy to prove that none of the above problems admits polynomial kernels unless NP ⊆ coNP/poly. Indeed, taking the disjoint union of t instances of any of these two problems defines a cross-composition, as defined by Bodlaender et al. [START_REF] Bodlaender | Kernelization lower bounds by crosscomposition[END_REF], from the problem to itself, directly implying the desired results as both problems are NP-hard by Proposition 10. We refer to [START_REF] Bodlaender | Kernelization lower bounds by crosscomposition[END_REF] for the missing definitions.

FPT algorithms

Our FPT algorithms for finding subdivisions of ( 1 , 2 )-spindles are based on the technique of representative families introduced by Monien [START_REF] Monien | How to find long paths efficiently[END_REF]. We use the improved version of this technique recently presented by Fomin et al. [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF] and, more precisely, our algorithms and notation are inspired by the ones for Long Directed Cycle given in [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF]. We start with some definitions introduced in [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF] that can also be found in [START_REF] Cygan | Parameterized Algorithms[END_REF]. Definition 11. Let M be a matroid. Two independent sets A, B of M fit if A ∩ B = ∅ and A ∪ B is independent. Also, let A be a family of sets of size p in M. A subfamily A ⊆ A is said to q-represent A if for every set B of size q such that there is an A ∈ A that fits B, there is an A ∈ A that also fits B. If A q-represents A, we write A ⊆ q rep A.

Finding 2-spindles with large total size

We start with the algorithm to solve the problem of, given a digraph G and a positive integer , deciding whether there exist two strictly positive integers 1 , 2 with 1 + 2 = such that G contains a subdivision of an ( 1 , 2 )-spindle, running in time 2 O( ) • n O (1) . If a subdigraph S of G is a subdivision of an ( 1 , 2 )-spindle, for some choice of 1 , 2 such that min{ 1 , 2 } ≥ 1 and 1 + 2 = , we say that S is a good spindle for . Suppose that S is a good spindle for with tail u and head v, and let 1 , 2 be as before. A subset X ⊆ V (G) containing two internally vertex-disjoint subpaths of S starting at u on 1 and 2 vertices is called a starting set for S. Recall that 1 , 2 are the minimum number of edges in the paths defining S. Therefore, in X, we are taking only the first 1 -1, 2 -1 edges in each path, which implies that v / ∈ X. Also, we may assume that max{ 1 , 2 } ≥ 2, as otherwise the desired spindle is just an arc with multiplicity two, which can be detected in polynomial time by using a maximum flow algorithm.

Our algorithm is inspired by the following naive approach. One could compute, for every pair of integers 1 , 2 ≥ 1 with 1 + 2 = , and for every triple of vertices u, u 1 , u 2 , the family S 1 , 2 u,u1,u2 containing the possible candidates for starting sets of good spindles for with tail u. More formally, let

S 1 , 2 u,u1,u2 = X : X ⊆ V (G), |X| = 1 + 2 -1,
and G[X] contains a (u, u 1 )-path P u 1 on 1 vertices and a (u, u 2 )-path P u 2 on 2 vertices such that V (P u 1 ) ∩ V (P u 2 ) = {u} .

Then, for every X ∈ S 1, 2 u,u1,u2 , in order to complete the desired spindle we can just run a flow algorithm in the graph G -(X \ {u 1 , u 2 }) to decide whether there exists some vertex v that is reachable from u 1 and u 2 . Observe that, if such a vertex exists, this would give us the desired spindle and, conversely, if such a spindle exists, then some execution of the described algorithm finds it. The drawback of this approach is the size of the set S 1 , 2 u,u1,u2 : it can be roughly as large as n 1 + 2 . The trick is to prove that only a "small" subset of S 1 , 2 u,u1,u2 is needed, namely a subset that "represents" a good spindle.

To give some intuition before getting into the details, let S be a good spindle for with tail u and head v, and let P u 1 , P u 2 be subpaths in S starting at u containing 1 , 2 vertices, respectively, with min{ 1 , 2 } ≥ 1 and 1 + 2 = . Note that this means that X = V (P 1 ) ∪ V (P 2 ) ∈ S 1, 2 u,u1,u2 and |X| = -1. Therefore, by letting w ∈ S \ X (it exists since v / ∈ X), if we consider the uniform matroid with ground set V (G) and rank , then X fits {w}, and any 1-representative family (see Definition 11) for S 1, 2 u,u1,u2 must contain some X that also fits {w}. We shall prove that a good spindle for is found when iterating over X . For the proof to work, we need to compute q-representative families for larger values of q.

More precisely, for every triple of vertices u, u 1 , u 2 ∈ V (G) and positive integers 1 , 2 , q with 1 ≤ 1 , 2 ≤ -1 and 1 ≤ q ≤ -1, we compute in time 2 O( ) • n O (1) a q-representative family for S 1, 2 u,u1,u2 in the uniform matroid with ground set V (G) and rank + q -1, denoted by S 1, 2 ,q u,u1,u2 ⊆ q rep S 1 , 2 u,u1,u2 .

vertex u ∈ V (G), vertices u + , u -and an arc (u + , u -) between them, and adding arc (u -, v + ) for each arc (u, v) ∈ A(G). Note that H is also acyclic, and fix an arbitrary topological ordering of V (H).

Claim 2. There exists a subdivision of a (k × )-spindle in G if and only if there exist x, y ∈ V (H) and k arc-disjoint (x, y)-paths in H, each of length at least 2 -1.

Proof of the claim. On the one hand, each path of a (k × )-spindle gives rise to a path in H of length at least 2 -1, since each internal vertex of a path is split into two (these paths are actually vertex-disjoint). On the other hand, let P 1 , . . . , P k be arc-disjoint paths between x, y ∈ V (H), each of length at least 2 -1. Since either |N + (z)| = 1 or |N -(z)| = 1 for every z ∈ V (H), and since P 1 , . . . , P k are arc-disjoint, we get that P 1 , . . . , P k are actually internally vertex-disjoint. Now, to obtain the desired (k × )-spindle, it suffices to observe that if u + ∈ V (P i ) \ {y}, for some u ∈ V (G) and some i ∈ {1, . . . , k}, then u -∈ V (P i ).

We want to decide whether H has the desired paths. For each x ∈ V (H), we define the We compute these tables starting at small values of k i=1 t i . Namely, for t 1 = t 2 = . . . = t k = 0, it holds that P x (e 1 , t 1 , . . . , e k , t k ) = true if and only if {e 1 , . . . , e k } = ∅. Now, to compute P x (e 1 , t 1 , . . . , e k , t k ), let w be the greatest vertex in {z ∈ V (H) : (z , z) ∈ {e 1 , . . . , e k }}, and let w be the greatest vertex in {z ∈ V (H) : (z, w) ∈ {e 1 , . . . , e k }}, according to the chosen topological ordering of V (H). Also, let e i = (w , w). If w = x, then the entry is given above, so suppose otherwise. Claim 3. P x (e 1 , t 1 , . . . , e k , t k ) = true if and only if P x (e 1 , t 1 , . . . , e, t i -1, . . . , e k , t k ) = true, for some arc e ∈ A(H) \ {e 1 , . . . , e k } incoming at w . Proof of the claim. Suppose first that P x (e 1 , t 1 , . . . , e k , t k ) = true, and let P 1 , . . . , P k be arc-disjoint paths starting at x and ending at e 1 , . . . , e k of length at least t 1 , . . . , t k , respectively. Let e be the arc preceding e i in path P i (e can denote the empty set when e i is incident to x). Then, P 1 , . . . , P i-1 , P i -e i , P i+1 , . . . , P k are arc-disjoint paths ending at e 1 , . . . , e i-1 , e, e i+1 , . . . , e k of length at least t 1 , . . . , t i-1 , t i -1, t i+1 , . . . , t k , respectively.

Conversely, let P 1 , . . . , P k be arc-disjoint paths that certify entry P x (e 1 , t 1 , . . . , e, t i -1, . . . , e k , t k ). If e i / ∈ A(P j ), for every j ∈ {1, . . . , k}, then P 1 , . . . , P i-1 , P i + e i , P i+1 , . . . , P k are the desired paths. So suppose that e i ∈ A(P j ). If j = i, then we get a cycle in H, a contradiction. Otherwise, because e i = e j and P j ends in e j , we get that there is a path starting in w and ending in z , where e j = (z, z ). This contradicts the choice of w.

By Claim 3, the entry P x (e 1 , t 1 , . . . , e k , t k ) can be computed by verifying at most |N + (w )| smaller entries. By Claim 2, the desired spindle exists if and only if there exist x, y ∈ V (H) and k arcs e 1 , . . . , e k incoming at y such that P x (e 1 , 2 -1, e 2 , 2 -1, . . . , e k , 2 -1) = true. The theorem follows.

Motivated by the fact that finding a subdivision of a general digraph F is in XP parameterized by |V (F )| on acyclic digraphs [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF][START_REF] Metzlar | Disjoint paths in acyclic digraphs[END_REF], we now present two hardness results about finding subdivisions of disjoint spindles on acyclic digraphs. The first result holds even for planar acyclic digraphs. Proposition 15. If F is the disjoint union of (2 × 1)-spindles, then deciding whether a planar acyclic digraph contains a subdivision of F is NP-complete.

Proof. We reduce from the problem of deciding whether the edges of a tripartite graph can be partitioned into triangles, which is known to be NP-complete [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF], even restricted to planar tripartite graphs [START_REF] Venkatesan | Approximate triclique coloring for register allocation[END_REF]. Let G be an input planar tripartite (undirected) graph, and let A ∪ B ∪ C be a tripartition of V (G). We build from G a planar acyclic digraph G by orienting all edges from A to B, from B to C, and from A to C. It is clear that E(G) admits a partition into triangles if and only if G contains as a subdivision (in fact, as a subdigraph) the digraph containing |E(G)|/3 disjoint copies of a (2 × 1)-spindle.

Our next result shows that, for some choices of F , finding a subdivision of F is W[1]-hard on acyclic digraphs. We just present a sketch of proof, as the reduction is based on a minor modification of an existing reduction of Slivkins [START_REF] Slivkins | Parameterized tractability of edge-disjoint paths on directed acyclic graphs[END_REF]. Proposition 16. If F is the disjoint union of a (k 1 × 1)-spindle and a (k 2 × 1)-spindle, then deciding whether an acyclic digraph contains a subdivision of

F is W[1]-hard parameterized by k 1 + k 2 .

Sketch of proof.

The proof is done by appropriately modifying the reduction for Edge-Disjoint Paths on acyclic digraphs given by Slivkins [START_REF] Slivkins | Parameterized tractability of edge-disjoint paths on directed acyclic graphs[END_REF], which carries over to the vertex-disjoint version as well. The reduction is from k-Clique, and the sets of demands to be satisfied consist just of a multiarc with multiplicity k 2 and another one with multiplicity k between two given pairs of terminals. The idea is the following: since in our problem we do not have fixed terminals, we "simulate" them by leaving only four vertices of high degree, so that finding the desired subdivision will only be possible by using the prescribed four vertices as endpoints. To do so, we take the construction of Slivkins [START_REF] Slivkins | Parameterized tractability of edge-disjoint paths on directed acyclic graphs[END_REF] and for each vertex, except for the four prescribed ones, we replace its outgoing (resp. incoming) arcs by an out-arborescence (resp. in-arborescence) of out-degree (resp. in-degree) at most two. Note that this operation may blow up the size of the subdivision, but it does not matter, as the parameter remains the same. By taking F to be the disjoint union of a ( k 2 × 1)-spindle and a (k × 1)-spindle, the result follows.

It is worth noting that the problem considered in Proposition 16 is para-NP-hard on general digraphs, as the conditions of [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF]Theorem 8] are easily seen to be fulfilled.

Conclusions

We studied the complexity of several problems consisting in finding subdivisions of spindles on digraphs. For a general spindle F , we do not know if finding a subdivision of F is FPT on general digraphs parameterized by |V (F )|, although we believe that it is indeed the case. As a partial result, one could try to prove that, for a fixed value of ≥ 4, finding a subdivision of a (k × )-spindle is FPT parameterized by k (the problem is NP-hard by Theorem 1). The above question is open even if the input digraph is acyclic (note that Theorem 4 does not answer this question), or even if F is a 2-spindle. Concerning 2-spindles, one may try to use the technique we used to prove Theorems 2 and 3, based on representative families in matroids. However, the technique does not seem to be easily applicable when the parameter is the total size of a prescribed 2-spindle. Namely, using the terminology from XX:20 On the complexity of finding internally vertex-disjoint long directed paths Section 4.2.2, the bottleneck is to find spindles that have one "short" and one "long" path. On the other hand, generalizing this technique to spindles with more than two paths seems pretty complicated.

It may be possible that the trick used by Zehavi [START_REF] Zehavi | A randomized algorithm for long directed cycle[END_REF] to avoid the use of representative families to solve Long Directed Cycle can be adapted to our setting as well. Another approach might be to use the divide-and-color technique [START_REF] Kneis | Divide-and-color[END_REF].

Cai and Ye [START_REF] Cai | Finding two edge-disjoint paths with length constraints[END_REF] recently studied the problem of finding two edge-disjoint paths on undirected graphs with length constraints between specified vertices. These length constraints can be an upper bound, a lower bound, or an equality on the lengths of each of the two desired paths, or no restriction at all, resulting in nine different problems. Interestingly, out of these nine problems, Cai and Ye [START_REF] Cai | Finding two edge-disjoint paths with length constraints[END_REF] gave FPT algorithms for seven of them, and left open only the following two cases: when there is only one constraint of type 'at least', and when both constraints are of type 'at least'. Observe that this latter problem is closely related to finding a subdivision of a 2-spindle.

In general, very little is known about the complexity of finding subdivisions on digraphs. Bang-Jensen et al. [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF] conjectured that, considering |V (F )| as a constant, the problem of finding a subdivision of F is either polynomial-time solvable or NP-complete. This conjecture is wide open. Recently, Havet et al. [START_REF] Havet | Finding a subdivision of a prescribed digraph of order 4[END_REF] studied the cases where |V (F )| = 4, and managed to classify all of them up to five exceptions. Even less is known about the parameterized complexity of the cases that are polynomial-time solvable for fixed F , that is, the cases in XP. In this article we focused on spindles, but there are other potential candidates such as, using the terminology of [START_REF] Bang-Jensen | Finding a subdivision of a digraph[END_REF], windmills, palms, or antipaths.

Theorem 6 .

 6 Let ≥ 4 be a fixed integer. The Max (• × )-Spindle Subdivision problem is NP-hard, even when restricted to DAGs. Proof. We provide a polynomial reduction from 3-Dimensional Matching, which is NPhard [15]. In the 3-Dimensional Matching problem, we are given three sets A, B, C of the same size and a set of triples T ⊆ A × B × C. The objective is to decide whether there exists a set T ⊆ T of pairwise disjoint triples with |T | = |A|. Given an instance (A, B, C, T ) of 3-Dimensional Matching, with |A| = n and |T | = m, we construct an instance G of Max (• × )-Spindle Subdivision as follows. We first present the reduction for = 4, and then we explain how to modify it for a general > 4.

Figure 2

 2 Figure 2 (a) Digraph H. (b) Selected paths when T ∈ T . (c) Selected paths when T ∈ T \ T .

  (b) or Figure 2(c), necessarily at least one vertex in V (H) would not be covered by P, a contradiction. Let T be the set of triples in T such that the corresponding gadget H intersects P as in Figure 2(b). It follows that 3|T | + 2(m -|T |) = |P| = k * = n + 2m, and therefore |T | = n. Since all the 2-paths in P associated with the triples in T are vertex-disjoint, we have that T is a collection of n pairwise disjoint triples, hence a solution of 3-Dimensional Matching.

Figure 3

 3 Figure 3 (a) Digraph G with X = {u1, u2, u3} and Y = {u3, u4}. (b) Graph G associated with G. (c) The thick edges define a matching of size five in G , corresponding to the two vertex-disjoint directed nontrivial paths (u1, v1, u3) and (u2, v3, u4) from X to Y in G.

  Spindle Subdivision as follows. Start from G, and delete all the arcs incoming at s (resp. outgoing from t), if any, and the arc (s, t), if it exists. Finally, add an (s, t)-path with 1 arcs consisting of new vertices and arcs. One can easily check that G has a Hamiltonian (s, t)-path if and only if G contains a subdivision of an (

1 , n -

table P x

 P with entries (e 1 , t 1 , . . . , e k , t k ), for each choice of at most k distinct arcs e 1 , . . . , e k (some of these may not exist, in which case we represent it by 'null'), and for each choice of k values t 1 , . . . , t k from the set {0, 1, . . . , 2 -1}. Observe that P x has size (|A(H)| + 1) k • (2 ) k , which, since we need to analyze the table of each vertex, gives us the claimed complexity of the algorithm. The meaning of an entry is given below: P x (e 1 , t 1 , . . . , e k , t k ) = true if and only if there exist k arc-disjoint paths P 1 , . . . , P k starting at x and ending at e 1 , . . . , e k of length at least t 1 , . . . , t k , respectively.

The ETH states that there is no algorithm solving 3-SAT on a formula with n variables in time

o(n) .

Work supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010), CNPq grants 304576/2017-4 and 304478/2018-0, CNPq Universal Project 401519/2016-3, FUNCAP-PRONEM PNE-0112-00061.01.00/16 and CAPES-PRINT. A conference version of this article appeared in the Proc.

We postpone the computation of the above q-representative families in time 2 O( ) • n O (1) to Section 4.2.3, and assume now that we already have these families at hand. The following lemma states that they are enough to find the desired good spindle. Lemma 12. G contains a good spindle S for with tail u if and only if G contains a good spindle for with starting set X , for some X ∈ S 1 , 2,q u,u1,u2 , u 1 , u 2 ∈ V (G), 1 , 2 ∈ [ -1] such that 1 + 2 = , and some q ∈ [ -1].

Proof. Clearly, we only need to prove the sufficiency part. Let S be a good spindle for in G with minimum number of vertices, which exists by hypothesis, and let u and v be the tail and the head of S, respectively. Let P u 1 = (u, . . . , u 1 ) and P u 2 = (u, . . . , u 2 ) be two subpaths in S outgoing from u, on 1 and 2 vertices, respectively, with 1 + 2 = . Let also P v 1 = (u 1 , . . . , v) and P v 2 = (u 2 , . . . , v) be the two subpaths in S from u 1 and u 2 to v, respectively; see Figure 4. Let S u = V (P u 1 ) ∪ V (P u 2 ), and note that |S u | = -1 and S u ∈ S 1, 2 u,u1,u2 . If |V (S) \ S u | ≤ -2, then, by letting B = V (S) \ S u and q = |B|, there exists S u ∈ S 1, 2 ,q u,u1,u2 , and S u ∪ B clearly contains a good spindle with starting set S u . Therefore, suppose |V (S) \ S u | ≥ -1, and let q = -1. Recall that v / ∈ {u 1 , u 2 }, and let B be the union of two subpaths P B 1 = (v 1 , . . . , v) and

Note that there may be several choices for the lengths of P B 1 and P B 2 , as far as their joint number of vertices is equal to -1. Since S u ∈ S 1, 2 u,u1,u2 and S u ∩ B = ∅, by definition of q-representative family there exists S u ∈ S 1, 2,q u,u1,u2 such that S u ∩ B = ∅. We claim that S u ∩ (V (P v 1 ) ∪ V (P v 2 )) = {u 1 , u 2 }, which concludes the proof of the lemma. Let P u 1 and P u 2 be the two paths in G[ S u ] with

then a good spindle can be easily obtained, so suppose otherwise; we distinguish two cases.

Suppose first that each of the paths P u 1 and P u 2 intersects exactly one of the paths P v 1 and P v 2 . By hypothesis, there exists a vertex w ∈ ( S u ∩ (V (P v 1 ) ∪ V (P v 2 ))) \ {u 1 , u 2 }, and suppose without loss of generality that w ∈ V ( P u 1 ) ∩ V (P v 1 ); see Figure 5(a) for an illustration. We define a good spindle for , S, in G as follows. The tail and head of S are vertices u and v, respectively. The first path of S starts at u, follows P u 1 until its first intersection with P v 1 (vertex w in Figure 5 and w 2 be vertices of

, and there is no vertex of P u 1 between w 1 and w 2 that belongs to V (P v 1 ) ∪ V (P v 2 ); see Figure 5(b) for an illustration. We define a good spindle for S, in G as follows. The tail and head of S are vertices w 1 and v, respectively. The first path of S starts at w 1 and follows P v 1 until v. The second path of S starts at w 1 , follows P u 1 until w 2 , and then follows P v 2 until v. By the choice of w 1 and w 2 and since |B| = -1, it follows that S is indeed a good spindle for . On the other hand, by construction

Wrapping up the algorithm. We finally have all the ingredients to describe our algorithm, which proceeds as follows. First, for every triple of vertices u, u 1 , u 2 ∈ V (G) and positive integers 1 , 2 , q with 1 ≤ 1 , 2 ≤ -1 and 1 ≤ q ≤ -1, we compute, as explained in Section 4.2.3, a q-representative family S 1, 2 ,q u,u1,u2 1) . Then the algorithm checks, for every combination of values u, u 1 , u 2 , 1 , 2 , for every S ∈ S 1 , 2,q u,u1,u2 and every

Note that the latter check can be easily performed in polynomial time by a flow algorithm [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. The correctness of the algorithm follows directly from Lemma 12, and its running time is 2 O( ) • n O (1) , as claimed. In order to keep the exposition as simple as possible, we did not focus on optimizing either the constants involved in the algorithm or the degree of the polynomial factor. Nevertheless, explicit small constants can be derived by carefully following the details in Fomin et al. [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF], or alternatively in [START_REF] Shachnai | Representative families: A unified tradeoff-based approach[END_REF].

Finding 2-spindles with two specified lengths

We now turn to the problem of finding 2-spindles with two specified lengths. Namely, given a digraph G and two integers 1 , 2 with 2 ≥ 1 ≥ 1, our objective is to decide whether G contains a subdivision of an ( 1 , 2 )-spindle in time 2 O( 2) • n O ( 1) . Note that this problem differs from the one considered in Section 4.2.1, as now we specify both lengths of the desired spindle, instead of just its total size. Our approach is similar to the one presented in Section 4.2.1, although some more technical ingredients are needed, and we need to look at the problem from a slightly different point of view.

In the proof of Lemma 12 in the previous section, we consider the existence of an ( 1 , 2 )spindle S, which is good for the total size = 1 + 2 , and with starting set S u , and prove that there must exist a good spindle for with a starting set S u that is contained in the set of q-representatives. For this, we use the fact that the part of S \ S u is either so small that it must be disjoint from any q-representative, or that it is already big enough, i.e., has total XX:15 size at least . However, we cannot ensure that the "residual" paths in S \ S u have sizes at least 1 and 2 , respectively. This is why in this section we need to use a different approach. Note that the running time we are aiming at allows us to guess the first 1 vertices in the "short" path.

Given integers 1 , 2 with 2 ≥ 1 ≥ 1, we say that a subdigraph S of G is a good spindle (for ( 1 , 2 )) if it is a subdivision of an ( 1 , 2 )-spindle. We may again assume that max{ 1 , 2 } ≥ 2. The main difference with respect to Section 4.2.1 is that now we will only represent the candidates for the first 2 vertices of the "long" path. To this end, we define, similarly to [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF], the following set for every pair of vertices u, u ∈ V (G) and positive integer 2 :

and G[X] contains a (u, u )-path on 2 vertices .

The above sets are exactly the same as those defined by Fomin et al. [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF] to solve the Long Directed Cycle problem. Therefore, we can just apply [14, Lemma 5.2] and compute, for every pair of vertices u, u ∈ V (G) and positive integers 2 , q with q ≤ 1 + 2 ≤ 2 2 , a q-representative family 1) . Now we would like to state the equivalent of Lemma 12 adapted to the new representative families. However, it turns out that the families P 2,q u,u do not yet suffice in order to find the desired spindle. To circumvent this cul-de-sac, we use the following trick: we first try to find "short" spindles using the color-coding technique of Alon et al. [START_REF] Alon | Color-coding[END_REF], and if we do not succeed, we can guarantee that all good spindles have at least one "long" path. In this situation, we can prove that the families P 2 ,q u,u are indeed enough to find a good spindle. More precisely, a good spindle S is said to be short if both its paths have at most 2 2 vertices, and it is said to be long otherwise. Note that Lemma 13 only applies to digraphs without good short spindles.

Similarly as before, given a long spindle S defined by two internally vertex-disjoint paths P 1 , P 2 , where P 2 contains at least 2 2 vertices, we say that the subset X ⊆ V (G) containing the first 2 vertices of P 2 is the starting set for S. Also, if u is the extremity of X distinct from u, we say that X ends in u .

Lemma 13.

Let G be a digraph containing no good short spindles. If G contains a good long spindle with starting set that ends in a vertex u , then G contains a long spindle with starting set X ⊆ V ( P u 2 ), for some V ( P u 2 ) ∈ P 2,q u,u with q = 1 + 2 -1.

Proof. Let S be a good long spindle in G with minimum number of vertices, which exists by hypothesis, and let u and v be the tail and the head of S, respectively. Let P 1 be the shortest of the two (u, v)-paths of S, and let u be the vertex on the other path of S at distance exactly 2 -1 from u. Let P u 2 and P v 2 be the (u, u )-path and the (u , v)-path in S, respectively; see Figure 6. Note that P u 2 ∈ P 2 u,u . Since by hypothesis S is a long spindle, it follows that |V (P v 2 )| > 2 . Again, in order to apply the properties of q-representative families, we define a vertex set B ⊆ V (S) as follows, crucially using the hypothesis that S is a good long spindle. Namely, B contains the last 1 vertices of the path P 1 together with the last 2 vertices of the path P v 2 , including v. Note that |B| = 1 + 2 -1 and that, since

u,u and V (P u 2 ) ∩ B = ∅, by definition of q-representative family there exists a set in P 2 ,q u,u corresponding to a (u, u )-path P u 2 such that V ( P u 2 ) ∩ B = ∅. We claim that V ( P u 2 ) ∩ V (S) ⊆ V (P u 2 ), which concludes the proof of the lemma. Assume for contradiction that (V ( P u 2 ) ∩ V (S)) \ V (P u 2 ) = ∅, and we again distinguish two cases. Suppose first that P u 2 is disjoint from P 1 , except for vertex u. Let w be the first vertex of P u 2 in V (P v 2 ) \ {u }; see Figure 7(a) for an illustration. We define a good spindle S in G as follows. The tail and head of S are vertices u and v, respectively. The first path of S is equal to P 1 . The second path of S starts at u, follows P u 2 until its first intersection with P v 1 (vertex w in Figure 7 Suppose now that P u 2 intersects P 1 . Since P u 2 ends at vertex u / ∈ V (P 1 ), there exist vertices w 1 , w 2 such that w 1 ∈ V (P 1 ), w 2 ∈ V ( P u 2 ) ∪ V (P v 2 ), and there is no vertex of P u 1 between w 1 and w 2 that belongs to V (P 1 )∪V ( P u 2 )∪V (P v 2 ); see Figure 7(b) for an illustration. We define a good spindle S in G as follows. The tail and head of S are vertices w 1 and v, respectively. The first path of S starts at w 1 and follows P 1 until v. The second path of S starts at w 1 , follows P u 2 until w 2 , and then follows P u 2 ∪ P v 2 until v. By the choices of B, w 1 , and w 2 , it follows that S is a good spindle with |V ( S)| < |V (S)|, contradicting again the choice of S.

Wrapping up the algorithm. We start by trying to find good small spindles. Namely, for every pair of integers 1 , 2 with 1 ≤ 1 ≤ 2 2 and 2 ≤ 2 ≤ 2 2 , we test whether G contains an ( 1 , 2 )-spindle as a subgraph, by using the color-coding technique of Alon et al. [START_REF] Alon | Color-coding[END_REF]. Since the treewidth of an undirected spindle is two, this procedure takes time 2 O( 2) • n O (1) .

If we succeed, the algorithm stops. Otherwise, we can guarantee that G does not contain any good short spindle, and therefore we are in position to apply Lemma 13. Before this, we first compute, for every pair of vertices u, u ∈ V (G) and positive integers 2 , q with q ≤ 1 + 2 ≤ 2 2 , a q-representative family P 2 ,q u,u ⊆ q rep P 2 u,u of size 2 O( 2) in time 2 O( 2) •n O (1) , using [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF]Lemma 5.2]. Now, for each path P u 2 such that V ( P u 2 ) ∈ P 2,q u,u , with q = 1 + 2 -1, we proceed as follows. By Lemma 13, it is enough to guess a vertex v ∈ V (G) and check whether G contains a (u, v)-path P 1 of length at least 1 , and a (u , v)-path P v 2 such that V (P 1 ) ∩ V ( P u 2 ) = {u}, V (P 1 ) ∩ V (P v 2 ) = {v}, and V ( P u 2 ) ∩ V (P v 2 ) = {u }. In order to do so, we apply brute force and we guess the first 1 vertices of P 1 in time n O ( 1 ) . Let these vertices be u, u 2 , . . . , u 1 . All that remains is to test whether the graph G \ {u 2 , . . . , u 1-1 } \ (V ( P u 2 ) \ {u }) contains two internally vertex-disjoint paths from u 1 and u to u, which can be done in polynomial time by using a flow algorithm [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. The correctness of the algorithm follows by the above discussion, and its running time is 2 O( 2 ) • n O( 1 ) , as claimed. Again, we did not focus on optimizing the constants involved in the algorithm.

Computing the representative families efficiently

We now explain how the representative families used in Sections 4.2.1 and 4.2.2 can be efficiently computed, by using the results of Fomin et al. [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF]. As discussed in Section 4.2.2, the families P 2,q u,u are exactly the same as those used by Fomin et al. [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF], so we can directly use [14, Lemma 5.2] and compute them in time 2 O( 2 ) • n O (1) . Let us now explain how the results of Fomin et al. [START_REF] Fomin | Efficient computation of representative families with applications in parameterized and exact algorithms[END_REF] can be used to compute efficiently the families S 1, 2 ,q u,u1,u2 used in Section 4.2.1. We need the following lemma. Lemma 14 (Fomin et al. [14]). Let M = (E, I) be a matroid and S be a family of subsets of E.

The key observation is that the families S 1, 2 u,u1,u2 can be obtained by combining pairs of elements in the families P 2 u,u . More precisely, for every triple of vertices u, u 1 , u 2 and positive integers 1 , 2 , it holds that S 1, 2 u,u1,u2 ⊆ P 1 u,u1 ∪ P 2 u,u2 .

Note that in the above equation we do not have equality, as some pairs of paths in P 1 u,u1 and P 2 u,u2 , respectively, may intersect at other vertices distinct from u. By Lemma 14, if P 1,q u,u1 ⊆ q rep P 1 u,u1 and P 2 ,q u,u2 ⊆ q rep P 2 u,u2 , then P 1 ,q u,u1 ∪ P 2,q u,u2 ⊆ q rep P 1 u,u1 ∪ P 2 u,u2 .

To conclude, it just remains to observe that, by the definition of q-representative family, it holds that if M = (E, I) is a matroid, S is a family of subsets of E, S ⊆ S and S ⊆ q rep S, then S ⊆ q rep S as well. Therefore, for every triple of vertices u, u 1 , u 2 and positive integers 1 , 2 with 1 , 2 ≤ , in order to compute a q-representative family for S 1 , 2 u,u1,u2 , we can just take the union of q-representative families for P 1 u,u1 and P 2 u,u2 , and these latter families can be computed in time 2 O( ) • n O (1) by [14, Lemma 5.2].

Finding spindles on directed acyclic graphs

In this section we focus on the case where the input digraph is acyclic. We start by proving Theorem 4. The proof uses classical dynamic programming along a topological ordering of the vertices of the input acyclic digraph.

Proof of Theorem 4. Given an acyclic digraph G and positive integers k, , recall that we want to prove that one can decide in time O(2 k • k • n 2k+1 ) whether G has a subdivision of a (k × )-spindle. For this, let H be obtained from the empty digraph by adding, for each