Consider the multicommodity flow problem on an undirected graph with k source-destination pairs and specified capacity constraints on the edges. The set of concurrently achievable flows (R_1,R_2,...,R_k) forms a polytope. We know that for k=1 (Ford-Fulkerson theorem) and k=2 (T.C. Hu's theorem), the cutset outer bound on the flow region is tight, so the polytope is completely specified by the cutset bound inequalities.
We also know that for k=3, the cutset outer bound is not tight in general. I am interested in what is known about the faces of this polytope for k=3.
- Is there a universal bound on the number of faces of the polytope (for all graphs where k=3)? Or is it the case that given any N>0, one can construct a graph with 3 source-destination pairs whose flow polytope has more than N faces?
- Is it possible to express the equations for the new faces, namely the faces that don't correspond to the cutset bound, in terms of some combinatorial quantities associated with the graph?