Half-integral five-terminus flows (Q581412)

Suppose that G is an undirected graph whose edge have nonnegative integral capacities, that \(s_ 1,...,s_ k\) are k dinstinguished vertices in G, and that \(d_{ij}\), \(1\leq i<j\leq k\), are nonnegative integral demands. We consider the problem of existence and of an admissible multicommodity flow \(F=\{F_{ij}:\) \(1\leq i<j\leq k\}\) in which each \(F_{ij}\) is a flow of value \(d_{ij}\) between \(s_ i\) and \(s_ j\). It is known that if \(k\geq 5\), then satisfying the obvious requirements of Ford-Fulkerson's type (concerning cuts of G) does not guarantee, in general, that such a multicommodity flow exists. We give a combinatorial criterion of solvability of this problem for \(k=5\) and prove that if \(k=5\) and the problem has a solution, then it has also a half-integral solution. This generalizes a number of known results on half-integral multicommodity flows. Also other results on multicommodity flows and metrics are presented.