MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

  1. 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?
  2. 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?


share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.