The Parameterized Complexity Landscape of the Unsplittable Flow Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913559481417728 |
|---|---|
| author | Ganian, Robert Rocton, Mathis Unterberger, Daniel |
| author_facet | Ganian, Robert Rocton, Mathis Unterberger, Daniel |
| contents | We study the well-established problem of finding an optimal routing of unsplittable flows in a graph. While by now there is an extensive body of work targeting the problem on graph classes such as paths and trees, we aim at using the parameterized paradigm to identify its boundaries of tractability on general graphs. We develop novel algorithms and lower bounds which result in a full classification of the parameterized complexity of the problem with respect to natural structural parameterizations for the problem -- notably maximum capacity, treewidth, maximum degree, and maximum flow length. In particular, we obtain a fixed-parameter algorithm for the problem when parameterized by all four of these parameters, establish XP-tractability as well as W[1]-hardness with respect to the former three and latter three parameters, and all remaining cases remain paraNP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_16964 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Parameterized Complexity Landscape of the Unsplittable Flow Problem Ganian, Robert Rocton, Mathis Unterberger, Daniel Data Structures and Algorithms We study the well-established problem of finding an optimal routing of unsplittable flows in a graph. While by now there is an extensive body of work targeting the problem on graph classes such as paths and trees, we aim at using the parameterized paradigm to identify its boundaries of tractability on general graphs. We develop novel algorithms and lower bounds which result in a full classification of the parameterized complexity of the problem with respect to natural structural parameterizations for the problem -- notably maximum capacity, treewidth, maximum degree, and maximum flow length. In particular, we obtain a fixed-parameter algorithm for the problem when parameterized by all four of these parameters, establish XP-tractability as well as W[1]-hardness with respect to the former three and latter three parameters, and all remaining cases remain paraNP-hard. |
| title | The Parameterized Complexity Landscape of the Unsplittable Flow Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.16964 |