Trader multiflow and box-TDI systems in series–parallel graphs.

Abstract Series–parallel graphs are known to be precisely the graphs for which the standard linear systems describing the cut cone, the cycle cone, the T -join polytope, the cut polytope, the multicut polytope and the T -join dominant are TDI. We prove that these systems are actually box-TDI. As a byproduct, our result yields a min–max relation for a new problem: the trader multiflow problem. The latter generalizes both the maximum multiflow and min-cost multiflow problems and we show that it is polynomial-time solvable in series–parallel graphs. [ABSTRACT FROM AUTHOR]