Criticality for multicommodity flows

For k≥1k≥1, the k-commodity flow problem is, we are given k pairs of vertices in a graph G, and we ask whether there exist k flows in the graph, where•the ith flow is between the ith pair of vertices, and has total value one; and•for each edge e, the sum of absolute values of the flows along e is at most one. We prove that for all k   there exists n(k)n(k) such that if G is connected, and contraction-minimal such that the k  -commodity flow problem is infeasible (that is, minimal in the sense that contracting any edge makes the problem feasible) then |V(G)|+|E(G)|≤n(k)|V(G)|+|E(G)|≤n(k).For integers k,p≥1k,p≥1, the (k,p)(k,p)-commodity flow problem   is as above, with the extra requirement that the flow value of each flow along each edge is a multiple of 1/p1/p. We prove that if p>1p>1, and G   is connected, and contraction-minimal such that the (k,p)(k,p)-commodity flow problem is infeasible, then |V(G)|+|E(G)|≤n(k)|V(G)|+|E(G)|≤n(k), with the same n(k)n(k) as before, independent of p  . In contrast, when p=1p=1 there are arbitrarily large contraction-minimal instances, even when k=2k=2.We give some other corollaries of the same approach, including•a proof that for all k≥0k≥0 there exists p>0p>0 such that every feasible k  -commodity flow problem has a solution in which all flow values are multiples of 1/p1/p, and•a very simple polynomial-time algorithm to solve the (k,p)(k,p) multicommodity flow problem when p>1p>1.