Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

Thanks.

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.