On Extremal Multiflows

Given an Eulerian multigraph, a subset T of its vertices, and a collection H of subsets of T, we ask how few edge-disjoint paths can contain maximum (A, T\A)-flows, for all A∈H at once. We answer the question for a certain class of hypergraphs H by presenting a strongly polynomial construction of a minimum set of such paths and a min-max formula for its cardinality. The method consists in reducing the problem to maximizing a b-matching in some graph. The result provides a solution to one interesting class of path packing problems.