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

Denis Cornaz (1) , Roland Grappe (2) , Mathieu Lacroix (2)

1 LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
2 LIPN - Laboratoire d'Informatique de Paris-Nord

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.

Mots clés: Box-TDI system; Series–parallel graph; Multiflow

Domaines: Informatique [cs]

Denis Cornaz, Roland Grappe, Mathieu Lacroix. Trader multiflow and box-TDI systems in series-parallel graphs. Discrete Optimization, 2019, 31 (1), ⟨10.1016/j.disopt.2018.09.003⟩. ⟨hal-02186541⟩