Tight spans of distances and the dual fractionality of undirected multiflow problems

In this paper, we give a complete characterization of the class of weighted maximum multiflow problems whose dual polyhedra have bounded fractionality. This is a common generalization of two fundamental results of Karzanov. The first one is a characterization of commodity graphs H for which the dual of maximum multiflow problem with respect to H has bounded fractionality, and the second one is a characterization of metrics d on terminals for which the dual of metric-weighed maximum multiflow problem has bounded fractionality. A key ingredient of the present paper is a nonmetric generalization of the tight span, which was originally introduced for metrics by Isbell and Dress. A theory of nonmetric tight spans provides a unified duality framework to the weighted maximum multiflow problems, and gives a unified interpretation of combinatorial dual solutions of several known min–max theorems in the multiflow theory.