When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks

Amit Chakrabarti, Lisa Fleischer, Christophe Weibel

Let $G=(V,E)$ be a supply graph and $H=(V,F)$ a demand graph defined on the same set of vertices. An assignment of capacities to the edges of $G$ and demands to the edges of $H$ is…