<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Integer and unsplittable multiflows in series-parallel digraphs

  • Mohammed Majthoub Almoghrabi,
  • Martin Skutella,
  • Philipp Warode

摘要

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.