{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:52Z","timestamp":1787323552127,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Given a graph and terminal pairs $(s_i,t_i)$, $i\\in[k]$, the edge-disjoint paths problem is to determine whether there exist $s_{i}t_{i}$ paths, $i\\in[k]$, that do not share any edges. We consider this problem on acyclic digraphs. It is known to be NP-complete and solvable in time $n^{O(k)}$ where n is the number of nodes. It has been a long-standing open question whether it is fixed-parameter tractable in k, i.e., whether it admits an algorithm with running time of the form $f(k)\\,n^{O(1)}$. We resolve this question in the negative: we show that the problem is $W[1]$-hard, hence unlikely to be fixed-parameter tractable. In fact it remains $W[1]$-hard even if the demand graph consists of two sets of parallel edges. On a positive side, we give an $O(m+k^{O(1)}\\,k!\\,n)$ algorithm for the special case when G is acyclic and $G+H$ is Eulerian, where H is the demand graph. We generalize this result (1) to the case when $G+H$ is \u201cnearly\u201d Eulerian, and (2) to an analogous special case of the unsplittable flow problem, a generalized version of disjoint paths that has capacities and demands.<\/jats:p>","DOI":"10.1137\/070697781","type":"journal-article","created":{"date-parts":[[2010,2,24]],"date-time":"2010-02-24T18:06:15Z","timestamp":1267034775000},"page":"146-157","source":"Crossref","is-referenced-by-count":35,"title":["Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs"],"prefix":"10.1137","volume":"24","author":[{"given":"Aleksandrs","family":"Slivkins","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,2,24]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"G. Baier, E. K\u00f6hler and M. Skutella,\n                      On the k-splittable flow problem\n                      , in Proceedings of the 10th Annual European Symposium on Algorithms, 2002, Lecture Notes in Comput. Sci. 2461, Springer, Berlin, 2002, pp. 101\u2013113.","DOI":"10.1007\/3-540-45749-6_13"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050043"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"R. Downey, V. Estivill-Castro, M. Fellows, E. Prieto, and F. Rosamund,\n                      Cutting up is hard to do: The parameterized complexity of k-cut and related problems\n                      , in Computing: The Australasian Theory Symposium, 2003 (electronic).","DOI":"10.1016\/S1571-0661(04)81014-4"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Parameterized Complexity\n                      , Springer-Verlag, New York, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0205048"},{"key":"R6","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Springer-Verlag, Berlin, 2006."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"J. Kleinberg,\n                      Single-source unsplittable flow\n                      , in Proceedings of the 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 68\u201377.","DOI":"10.1109\/SFCS.1996.548465"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"J. Kleinberg,\n                      Decision algorithms for unsplittable flow and the half-disjoint paths problem\n                      , in Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (Dallas, TX, 1998), ACM, New York, 1999 pp. 530\u2013539.","DOI":"10.1145\/276698.276867"},{"key":"R11","unstructured":"J. Kleinberg,\n                      Approximation Algorithms for Disjoint Paths Problems\n                      , Ph.D. thesis, MIT, Cambridge, MA, 1996."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90093-8"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"S. G. Kolliopoulos,\n                      Edge-disjoint Paths and Unsplittable Flow\n                      , in Handbook of Approximation Algorithms and Metaheuristics, T. F. Gonzalez, ed., Chapman & Hall\/CRC, 2007, 57-1.","DOI":"10.1201\/9781420010749.ch57"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799355314"},{"key":"R15","unstructured":"B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel, and A. Schrijver, eds.\n                      Paths, Flows and VLSI-Layouts\n                      , Springer-Verlag, Berlin, 1990."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-17.3.369"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"R18","unstructured":"A. Schrijver,\n                      Combinatorial Optimization. Polyhedra and Efficiency\n                      , Vols. A and C, Springer-Verlag, Berlin, 2003."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224061"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322207"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100260"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)E0177-Z"},{"key":"R23","unstructured":"J. Vygen,\n                      Disjoint Paths\n                      , Rep. 94846, Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany, 1998."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070697781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:08:43Z","timestamp":1787321323000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070697781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/070697781"],"URL":"https:\/\/doi.org\/10.1137\/070697781","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}