On extremal multiflows

Given an Eulerian multigraph, a subset T of its vertices, and a collection. H of subsets of. we asl; how few edge-disjoint paths can contain maximum ( Am T\A)-flows, for all A epsilon H at once. We answer the question for a ce rtain class of hypergraphs H by presenting a strongly polynomial constructi on of a minimum set of such paths and a min-max formula for its cal cardina lity. The method consists in reducing the problem to maximizing a b-matchin g in some graph. The result provides a solution to one interesting class of path packing problems. (C) 2000 Academic Press.