2026-07-24T06:45:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19425 2024-03-06T11:04:01Z ddc:004 open_access

The Parameterised Complexity Of Integer Multicommodity Flow Bodlaender, Hans L. Mannens, Isja Oostveen, Jelle J. Pandey, Sukanya van Leeuwen, Erik Jan multicommodity flow parameterised complexity XNLP-completeness XALP-completeness The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Path problem, have been considered. Therefore, we investigate the parameterised complexity of the general Integer Multicommodity Flow problem. We show that the decision version of this problem on directed graphs for a constant number of commodities, when the capacities are given in unary, is XNLP-complete with pathwidth as parameter and XALP-complete with treewidth as parameter. When the capacities are given in binary, the problem is NP-complete even for graphs of pathwidth at most 13. We give related results for undirected graphs. These results imply that the problem is unlikely to be fixed-parameter tractable by these parameters. In contrast, we show that the problem does become fixed-parameter tractable when weighted tree partition width (a variant of tree partition width for edge weighted graphs) is used as parameter. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Isja Mannens and Jelle J. Oostveen and Sukanya Pandey and Erik Jan van Leeuwen 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.6 urn:nbn:de:0030-drops-194250 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.6 eng https://creativecommons.org/licenses/by/4.0/legalcode