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