Criticality for multicommodity flows

21 May 2013
Paul Seymour
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 (depending on k, but 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.
  • Combinatorial Theory Seminar