Integer plane multiflows with a mixed number of demands (Q1322028)

We give a polynomial algorithm which decides the integer solvability of multicommodity 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 Pfeiffer 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 \(\nu(G,T)= \tau(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\).