Integer Plane Multiflows with a Fixed Number of Demands

We give a polynomial algorithm which decides the integer solvability of multi-commodity flow problems where the union of "capacity-" and "demand-edges" forms a planar graph, and the number of demand edges is bounded by a prefixed integer k. This problem was solved earlier for k = 2 by Seymour and for k = 3 by Korach. For k = 4 much work has been done by Korach and Newmann. The main result of the present note is a polynomial algorithm that finds such a multiflow or proves that it does not exist, for arbitrary fixed k. Middendorf and Pfeiller have recently proved that this problem is NP-complete in general (without fixing k). We actually give a more general polynomial algorithm, namely to decide whether the relation ν(G, T) = τ(G, T) or its weighted generalization holds for the pair (G, T) (where G is not necessarily planar), provided |T| is fixed, thus extending Seymour′s method and result for |T| = 4.