A linear programming formulation of Mader's edge-disjoint paths problem

AbstractWe give a dual pair of linear programs for a min–max result of Mader describing the maximum number of edge-disjoint T-paths in a graph G=(V,E) with T⊆V. We conclude that there exists a polynomial-time algorithm (based on the ellipsoid method) for finding the maximum number of T-paths in a capacitated graph, where the number of T-paths using an edge does not exceed the capacity of that edge