The Parameterised Complexity Of Integer Multicommodity Flow

Isja Mannens; Jelle Oostveen; Erik Jan van Leeuwen; Sukanya Pandey; Hans L. Bodlaender

doi:10.4230/LIPIcs.IPEC.2023.6

The Parameterised Complexity Of Integer Multicommodity Flow

Isja Mannens, Jelle Oostveen, Erik Jan van Leeuwen, Sukanya Pandey, Hans L. Bodlaender

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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.

Original language	English
Title of host publication	18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Editors	Neeldhara Misra, Magnus Wahlström
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Pages	91-109
ISBN (Electronic)	9783959773058
ISBN (Print)	978-3-95977-305-8
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2023.6
Publication status	Published - 13 Dec 2023

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss-Dagstuhl - Leibniz Zentrum für Informatik
Volume	285
ISSN (Print)	1868-8969

Bibliographical note

Publisher Copyright:
© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

Funding

Isja Mannens: The research of Isja Mannens was supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 853234). Funding Isja Mannens: The research of Isja Mannens was supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 853234). Jelle J. Oostveen: The research of Jelle Oostveen was supported by the NWO grant OCENW.KLEIN. 114 (PACAN).

Funders	Funder number
Horizon 2020 Framework Programme
European Research Council
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	OCENW.KLEIN
Horizon 2020	853234

Keywords

XALPcompleteness
XNLP-completeness
multicommodity flow
parameterised complexity

Access to Document

10.4230/LIPIcs.IPEC.2023.6Licence: CC BY

LIPIcs.IPEC.2023.6Final published version, 1.55 MBLicence: CC BY

Cite this

Mannens, I., Oostveen, J., van Leeuwen, E. J., Pandey, S., & Bodlaender, H. L. (2023). The Parameterised Complexity Of Integer Multicommodity Flow. In N. Misra, & M. Wahlström (Eds.), 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) (pp. 91-109). Article 6 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 285). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2023.6

Mannens, Isja ; Oostveen, Jelle ; van Leeuwen, Erik Jan et al. / The Parameterised Complexity Of Integer Multicommodity Flow. 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). editor / Neeldhara Misra ; Magnus Wahlström. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2023. pp. 91-109 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{b6235288b3c3484fac67cd64d6dcdb01,

title = "The Parameterised Complexity Of Integer Multicommodity Flow",

abstract = "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.",

keywords = "XALPcompleteness, XNLP-completeness, multicommodity flow, parameterised complexity",

author = "Isja Mannens and Jelle Oostveen and \{van Leeuwen\}, \{Erik Jan\} and Sukanya Pandey and Bodlaender, \{Hans L.\}",

year = "2023",

month = dec,

day = "13",

doi = "10.4230/LIPIcs.IPEC.2023.6",

language = "English",

isbn = "978-3-95977-305-8",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik",

pages = "91--109",

editor = "Misra, \{Neeldhara \} and Wahlstr{\"o}m, \{Magnus \}",

booktitle = "18th International Symposium on Parameterized and Exact Computation (IPEC 2023)",

}

Mannens, I, Oostveen, J, van Leeuwen, EJ, Pandey, S & Bodlaender, HL 2023, The Parameterised Complexity Of Integer Multicommodity Flow. in N Misra & M Wahlström (eds), 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)., 6, Leibniz International Proceedings in Informatics (LIPIcs), vol. 285, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 91-109. https://doi.org/10.4230/LIPIcs.IPEC.2023.6

The Parameterised Complexity Of Integer Multicommodity Flow. / Mannens, Isja; Oostveen, Jelle; van Leeuwen, Erik Jan et al.
18th International Symposium on Parameterized and Exact Computation (IPEC 2023). ed. / Neeldhara Misra; Magnus Wahlström. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2023. p. 91-109 6 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 285).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The Parameterised Complexity Of Integer Multicommodity Flow

AU - Mannens, Isja

AU - Oostveen, Jelle

AU - van Leeuwen, Erik Jan

AU - Pandey, Sukanya

AU - Bodlaender, Hans L.

PY - 2023/12/13

Y1 - 2023/12/13

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

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

KW - XALPcompleteness

KW - XNLP-completeness

KW - multicommodity flow

KW - parameterised complexity

UR - https://www.scopus.com/pages/publications/85180554765

U2 - 10.4230/LIPIcs.IPEC.2023.6

DO - 10.4230/LIPIcs.IPEC.2023.6

M3 - Conference contribution

SN - 978-3-95977-305-8

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 91

EP - 109

BT - 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

A2 - Misra, Neeldhara

A2 - Wahlström, Magnus

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

ER -

Mannens I, Oostveen J, van Leeuwen EJ, Pandey S, Bodlaender HL. The Parameterised Complexity Of Integer Multicommodity Flow. In Misra N, Wahlström M, editors, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. 2023. p. 91-109. 6. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.IPEC.2023.6

The Parameterised Complexity Of Integer Multicommodity Flow

Abstract

Publication series

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this