Integer and Unsplittable Multiflows in Series-Parallel Digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911065330155520 |
|---|---|
| author | Almoghrabi, Mohammed Majthoub Skutella, Martin Warode, Philipp |
| author_facet | Almoghrabi, Mohammed Majthoub Skutella, Martin Warode, Philipp |
| contents | An unsplittable multiflow routes the demand of each commodity along a single path from its source to its sink node. As our main result, we prove that in series-parallel digraphs, any given multiflow can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. This result confirms a 25-year-old conjecture by Goemans for single-source unsplittable flows, as well as a stronger recent conjecture by Morell and Skutella, for series-parallel digraphs - even for general multiflow instances where commodities have distinct source and sink nodes. Previously, no non-trivial class of digraphs was known for which either conjecture holds. En route to proving this result, we also establish strong integrality results for multiflows on series-parallel digraphs, showing that their computation can be reduced to a simple single-commodity network flow problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_05182 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Integer and Unsplittable Multiflows in Series-Parallel Digraphs Almoghrabi, Mohammed Majthoub Skutella, Martin Warode, Philipp Combinatorics Data Structures and Algorithms An unsplittable multiflow routes the demand of each commodity along a single path from its source to its sink node. As our main result, we prove that in series-parallel digraphs, any given multiflow can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. This result confirms a 25-year-old conjecture by Goemans for single-source unsplittable flows, as well as a stronger recent conjecture by Morell and Skutella, for series-parallel digraphs - even for general multiflow instances where commodities have distinct source and sink nodes. Previously, no non-trivial class of digraphs was known for which either conjecture holds. En route to proving this result, we also establish strong integrality results for multiflows on series-parallel digraphs, showing that their computation can be reduced to a simple single-commodity network flow problem. |
| title | Integer and Unsplittable Multiflows in Series-Parallel Digraphs |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.05182 |