Members’ Seminar

The ``k-commodity flow problem'' is: we are given k pairs of vertices of a graph, and we ask whether there are 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, the sum of the absolute values of the flows along it is at most one. We may also require the flows to be 1/2-integral, or indeed 1/p-integral for some fixed p. If the problem is feasible (that is, the desired flows exist) then it is still feasible after contracting any edge, so let us say a flow problem is ``critical'' if it is infeasible, but becomes feasible when we contract any edge. In many special cases, all critical instances have only two vertices, but if we ask for integral flows (that is, p = 1, essentially the edge-disjoint paths problem), then there arbitrarily large critical instances, even with k = 2. But it turns out that p = 1 is the only bad case; if p>1 then all critical instances have bounded size (independent of p), and the same is true if there is no integrality requirement at all. The proof gives rise to a very simple algorithm for the k edge-disjoint paths problem in 4-edge-connected graphs. It also has the consequence that for for all k there exists p(k) such that if a k-commodity flow problem has a real solution, then it has a rational solution with denominators at most p(k). This seems to be new even for k = 3.