Akhoondian Amiri, Saeed; Kreutzer, Stephan; Marx, Dániel; Rabinovich, Roman Routing with congestion in acyclic digraphs. (English) Zbl 1461.05098 Inf. Process. Lett. 151, Article ID 105836 (2019). Summary: We study the version of the \(k\)-disjoint paths problem where \(k\) demand pairs \((s_1,t_1),\dots,(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\). Cited in 4 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C85 Graph algorithms (graph-theoretic aspects) 05C38 Paths and cycles 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68R10 Graph theory (including graph drawing) in computer science Keywords:algorithms; disjoint paths; congestion; acyclic digraphs; W[1]-hard problem PDFBibTeX XMLCite \textit{S. Akhoondian Amiri} et al., Inf. Process. Lett. 151, Article ID 105836 (2019; Zbl 1461.05098) Full Text: DOI Link References: [1] Akhoondian Amiri, Saeed; Golshani, Ali; Kreutzer, Stephan; Siebertz, Sebastian, Vertex disjoint paths in upward planar graphs, (Computer Science - Theory and Applications: 9th International Computer Science Symposium in Russia, Proceedings. Computer Science - Theory and Applications: 9th International Computer Science Symposium in Russia, Proceedings, CSR 2014, Moscow, Russia, June 7-11 (2014), Springer International Publishing: Springer International Publishing Cham), 52-64 · Zbl 1408.68105 [2] Akhoondian Amiri, Saeed; Dudycz, Szymon; Schmid, Stefan; Wiederrecht, Sebastian, Congestion-free rerouting of flows on dags, (45th International Colloquium on Automata, Languages, and Programming. 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13 (2018)), 143:1-143:13 · Zbl 1499.68242 [3] Akhoondian Amiri, Saeed; Kreutzer, Stephan; Marx, Dániel; Rabinovich, Roman, Routing with congestion in acyclic digraphs, (41st International Symposium on Mathematical Foundations of Computer Science. 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, Kraków, Poland, August 22-26 (2016)), 7:1-7:11 · Zbl 1398.68208 [4] Andrews, Matthew; Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal; Zhang, Lisa, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, Combinatorica, 30, 5, 485-520 (2011) · Zbl 1240.68113 [5] Bang-Jensen, Jorgen; Gutin, Gregory Z., Digraphs - Theory, Algorithms and Applications (2010), Springer · Zbl 1210.05001 [6] Chalermsook, Parinya; Chuzhoy, Julia; Ene, Alina; Li, Shi, Approximation algorithms and hardness of integral concurrent flow, (Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing. Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC ’12 (2012), ACM: ACM New York, NY, USA), 689-708 · Zbl 1286.05060 [7] Chekuri, C.; Khanna, S.; Shepherd, F. B., Edge-disjoint paths in planar graphs, (Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004)), 71-80 [8] Chekuri, Chandra; Ene, Alina, Poly-logarithmic approximation for maximum node disjoint paths with constant congestion, (Khanna, Sanjeev, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8 (2013), SIAM), 326-341 · Zbl 1421.68200 [9] Chekuri, Chandra; Ene, Alina, The all-or-nothing flow problem in directed graphs with symmetric demand pairs, (Lee, Jon; Vygen, Jens, Integer Programming and Combinatorial Optimization - 17th International Conference, Proceedings. Integer Programming and Combinatorial Optimization - 17th International Conference, Proceedings, IPCO 2014, Bonn, Germany, June 23-25, 2014. Integer Programming and Combinatorial Optimization - 17th International Conference, Proceedings. Integer Programming and Combinatorial Optimization - 17th International Conference, Proceedings, IPCO 2014, Bonn, Germany, June 23-25, 2014, Lecture Notes in Computer Science, vol. 8494 (2014), Springer), 222-233 · Zbl 1418.90272 [10] Chekuri, Chandra; Khanna, Sanjeev; Bruce Shepherd, F., Multicommodity flow, well-linked terminals, and routing problems, (Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, New York, NY, USA (2005), ACM), 183-192 · Zbl 1192.90017 [11] Chekuri, Chandra; Khanna, Sanjeev; Bruce Shepherd, F., An \(o(\sqrt{n})\) approximation and integrality gap for disjoint paths and unsplittable flow, Theory Comput., 2, 7, 137-146 (2006) · Zbl 1213.68700 [12] Chuzhoy, J.; Li, S., A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2, (IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE 53rd Annual Symposium on Foundations of Computer Science, FOCS (2012)), 233-242 [13] Cygan, M.; Marx, D.; Pilipczuk, M.; Pilipczuk, M., The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable, (IEEE 54th Annual Symposium onFoundations of Computer Science. IEEE 54th Annual Symposium onFoundations of Computer Science, FOCS (2013)), 197-206 [14] Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket, Parameterized Algorithms (2015), Springer · Zbl 1334.90001 [15] Diestel, Reinhard, Graph Theory (2010), Springer-Verlag · Zbl 1204.05001 [16] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM J. Comput., 5, 4, 691-703 (1976) · Zbl 0358.90021 [17] Fortune, Steven; Hopcroft, John; Wyllie, James, The directed subgraph homeomorphism problem, Theor. Comput. Sci., 10, 2, 111-121 (1980) · Zbl 0419.05028 [18] Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis, Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052 [19] Johnson, Thor; Robertson, Neil; Seymour, Paul D.; Thomas, Robin, Directed tree-width, J. Comb. Theory, Ser. B, 82, 1, 138-154 (2001) · Zbl 1027.05045 [20] Kolliopoulos, G. Stavros; Stein, Clifford, Approximating disjoint-path problems using packing integer programs, Math. Program., 99, 1, 63-87 (2003) · Zbl 1059.90107 [21] Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket, Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci., 105, 41-72 (2011) · Zbl 1258.68068 [22] Marx, Dániel, Can you beat treewidth?, Theory Comput., 6, 1, 85-112 (2010) · Zbl 1213.68316 [23] N. Robertson, P.D. Seymour, Graph minors I-XXIII, Journal of Combinatorial Theory, Series B, from 1982-2010.; N. Robertson, P.D. Seymour, Graph minors I-XXIII, Journal of Combinatorial Theory, Series B, from 1982-2010. · Zbl 1216.05151 [24] Slivkins, Aleksandrs, Parameterized tractability of edge-disjoint paths on directed acyclic graphs, SIAM J. Discrete Math., 24, 1, 146-157 (2010) · Zbl 1207.68169 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.