2026-07-22T12:14:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6424 2024-03-06T10:38:14Z ddc:004 open_access

Routing with Congestion in Acyclic Digraphs Amiri, Saeed Akhoondian Kreutzer, Stephan Marx, Dániel Rabinovich, Roman algorithms disjoint paths congestion acyclic digraphs XP W[1]-hard We study the version of the k-disjoint paths problem where k demand pairs (s_1,t_1), ..., (s_k,t_k) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n^{O(d)} if we allow congestion k-d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f(k)n^{o(d*log(d))} for any computable function f. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Saeed Akhoondian Amiri and Stephan Kreutzer and Dániel Marx and Roman Rabinovich 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.7 urn:nbn:de:0030-drops-64244 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.7 eng https://creativecommons.org/licenses/by/3.0/legalcode