Integer and unsplittable multiflows in series-parallel digraphs
研究证明在串并联有向图中，任意给定的多流都能表示成不可分多流的凸组合，且每条弧上总流量的偏差小于最大商品需求。该结果验证了Goemans和Morell与Skutella的猜想，并建立了强整数性结论，对网络流研究者有参考价值。
Abstract 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.