Morell and Skutella's two-sided convex-combination conjecture for acyclic single-source flows

From papers

Consider the single-source unsplittable flow problem on an acyclic directed graph, with common source ss, commodities ending at sinks tit_i with demands did_i, and a fractional flow (xe)eE(x_e)_{e\in E}. An unsplittable flow (ye)eE(y_e)_{e\in E} is induced by one ss--tit_i path for each commodity, and let dmaxmaxi[k]did_{\max}\coloneqq\max_{i\in[k]}d_i. Define the upper and lower bounds

yexe+dmaxfor every arc eE,y_e\leq x_e+d_{\max}\qquad\text{for every arc }e\in E,

and

yexedmaxfor every arc eE.y_e\geq x_e-d_{\max}\qquad\text{for every arc }e\in E.

Morell and Skutella's conjecture. Any fractional flow (xe)eE(x_e)_{e\in E} can be expressed as a convex combination of unsplittable flows (ye)eE(y_e)_{e\in E} 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

No solutions have been posted yet.