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 ,

Color-coding, Journal of the ACM, vol.42, issue.4, pp.844-856, 1995. ,

Digraphs: Theory, Algorithms and Applications, 2008. ,

Finding a subdivision of a digraph, Theoretical Computer Science, vol.562, pp.283-303, 2015. ,

URL : https://hal.archives-ouvertes.fr/hal-00720500

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

Approximating longest directed paths and cycles, Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP), vol.3142, pp.222-233, 2004. ,

Kernelization lower bounds by crosscomposition, SIAM Journal on Discrete Mathematics, vol.28, issue.1, pp.277-305, 2014. ,

Packing paths in digraphs, Journal of Graph Theory, vol.44, issue.2, pp.81-94, 2003. ,

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

Subdivisions of oriented cycles in digraphs with large chromatic number, 2016. ,

URL : https://hal.archives-ouvertes.fr/hal-01411115

, Parameterized Algorithms, 2015.

, Graph Theory, vol.173, 2012.

Fundamentals of Parameterized Complexity. Texts in Computer Science, 2013. ,

, Parameterized Complexity Theory, 2006.

Efficient computation of representative families with applications in parameterized and exact algorithms, Journal of the ACM, vol.63, issue.4, 2016. ,

Computers and intractability. A guide to the theory of NP-completeness, 1979. ,

Finding topological subgraphs is fixed-parameter tractable, Proc. of the 43rd ACM Symposium on Theory of Computing (STOC), pp.479-488, 2011. ,

Finding a subdivision of a prescribed digraph of order 4, Journal of Graph Theory ,

URL : https://hal.archives-ouvertes.fr/hal-01202650

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

The complexity of finding maximum disjoint paths with length constraints, Networks, vol.12, issue.3, pp.277-286, 1982. ,

Cycles with two blocks in k-chromatic digraphs, 2016. ,

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

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

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

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

Invitation to Fixed-Parameter Algorithms, 2006. ,

Matroid theory, 1992. ,

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

, Algorithms, 2011.

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

Approximate triclique coloring for register allocation, Information Processing Letters, vol.60, pp.249-253, 1996. ,