Integer and unsplittable multiflows in series-parallel digraphs

• 成果类型: Article; Early Access
• 署名作者: Majthoub Almoghrabi, Mohammed; Skutella, Martin; Warode, Philipp
• 署名单位: Technical University of Berlin; Humboldt University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02392-8
• 发表日期: 2026-06-29
• 关键词: Multiflow; integrality; Unsplittable flow; Series-parallel digraph; multicommodity flows; cuts

摘要

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.