Morell and Skutella's two-sided convex-combination conjecture for acyclic single-source flows
Morell and Skutella's two-sided convex-combination conjecture for acyclic single-source flows
Consider the single-source unsplittable flow problem on an acyclic directed graph, with common source , commodities ending at sinks with demands , and a fractional flow . An unsplittable flow is induced by one -- path for each commodity, and let . Define the upper and lower bounds
and
Morell and Skutella's conjecture. Any fractional flow can be expressed as a convex combination of unsplittable flows satisfying both bounds. The supplied text states that the analogous existence result for a single unsplittable flow is known for acyclic planar digraphs, but does not state a resolution of this convex-combination strengthening.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Mohammed Majthoub Almoghrabi, Martin Skutella and Philipp Warode, “Integer and Unsplittable Multiflows in Series-Parallel Digraphs”, arXiv:2412.05182 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.