On one maximum multiflow problem and related metrics Original Research Article

We consider the undirected maximum multiflow (multicommodity flow) problem in the case when the commodity graph is the disjoint union of K3 and K2. We prove that if the supply graph satisfies a certain Eulerian-type condition, then the problem has an integer optimal solution. To obtain this result, we first study the corresponding dual problem on metrics and show that an optimal solution to the latter is achieved on some (2,3)-metric or some 3-cut metric.