.. .. , .. .. I+1, and .. , 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 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 [3, 23], we now present two hardness results about finding subdivisions of disjoint spindles on acyclic digraphs, The first result holds even for planar acyclic digraphs

N. Alon, R. Yuster, and U. Zwick, Color-coding, Journal of the ACM, vol.42, issue.4, pp.844-856, 1995.

J. Bang-jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2008.

J. Bang-jensen, F. Havet, and A. K. Maia, Finding a subdivision of a digraph, Theoretical Computer Science, vol.562, pp.283-303, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00720500

A. Benhocine and A. P. Wojda, On the existence of specified cycles in a tournament, Journal of Graph Theory, vol.7, issue.4, pp.469-473, 1983.

A. Björklund, T. Husfeldt, and S. Khanna, Approximating longest directed paths and cycles, Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP), vol.3142, pp.222-233, 2004.

H. L. Bodlaender, B. M. Jansen, and S. Kratsch, Kernelization lower bounds by crosscomposition, SIAM Journal on Discrete Mathematics, vol.28, issue.1, pp.277-305, 2014.

R. C. Brewster, P. Hell, S. H. Pantel, R. Rizzi, and A. Yeo, Packing paths in digraphs, Journal of Graph Theory, vol.44, issue.2, pp.81-94, 2003.

L. Cai and J. Ye, Finding two edge-disjoint paths with length constraints, Proc. of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol.9941, pp.62-73, 2016.

N. Cohen, F. Havet, W. Lochet, and N. Nisse, Subdivisions of oriented cycles in digraphs with large chromatic number, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01411115

M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx et al., Parameterized Algorithms, 2015.

R. Diestel, Graph Theory, vol.173, 2012.

R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science, 2013.

J. Flum and M. Grohe, Parameterized Complexity Theory, 2006.

F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh, Efficient computation of representative families with applications in parameterized and exact algorithms, Journal of the ACM, vol.63, issue.4, 2016.

M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, 1979.

M. Grohe, K. Kawarabayashi, D. Marx, and P. Wollan, Finding topological subgraphs is fixed-parameter tractable, Proc. of the 43rd ACM Symposium on Theory of Computing (STOC), pp.479-488, 2011.

F. Havet, A. K. Maia, and B. Mohar, Finding a subdivision of a prescribed digraph of order 4, Journal of Graph Theory
URL : https://hal.archives-ouvertes.fr/hal-01202650

R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity?, Journal of Computer and System Sciences, vol.63, issue.4, pp.512-530, 2001.

A. Itai, Y. Perl, and Y. Shiloach, The complexity of finding maximum disjoint paths with length constraints, Networks, vol.12, issue.3, pp.277-286, 1982.

R. Kim, S. Kim, J. Ma, and B. Park, Cycles with two blocks in k-chromatic digraphs, 2016.

M. , Disjoint A-paths in digraphs, Journal of Combinatorial Theory, Series B, vol.95, issue.1, pp.168-2005, 2005.

L. Lovász, Matroid matching and some applications, Journal of Combinatorial Theory, Series B, vol.28, issue.2, pp.208-236, 1980.

A. Metzlar, Disjoint paths in acyclic digraphs, Journal of Combinatorial Theory, Series B, vol.57, issue.2, pp.228-238, 1993.

B. Monien, How to find long paths efficiently, Annals of Discrete Mathematics, vol.25, pp.239-254, 1985.

R. Niedermeier, Invitation to Fixed-Parameter Algorithms, 2006.

J. G. Oxley, Matroid theory, 1992.

A. Schrijver, A Short Proof of Mader's S-Paths Theorem, Journal of Combinatorial Theory, Series B, vol.82, issue.2, pp.319-321, 2001.

R. Sedgewick and K. Wayne, Algorithms, 2011.

A. Slivkins, Parameterized tractability of edge-disjoint paths on directed acyclic graphs, SIAM Journal on Discrete Mathematics, vol.24, issue.1, pp.146-157, 2010.

G. Venkatesan and C. Pandu-rangan, Approximate triclique coloring for register allocation, Information Processing Letters, vol.60, pp.249-253, 1996.