6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ For the first question, do you mean a constant upper bound by "a universal bound"? I assumed so from the description of the latter part of the first question, but if so, the answer is trivially no (even when k=1). $\endgroup$ Commented Jan 4, 2012 at 9:31
  • $\begingroup$ @yoshio-okamato: Yes, I meant a constant upper bound. I don't follow how the answer is trivially no. For instance, suppose that for k=2, we are given a graph with specified edge capacities and source destination pairs $s_1-d_1$ and $s_2-d_2$ carrying flows $R_1$ and $R_2$ respectively. Then we compute the following four numbers: $c(s_1;d_1), c(s_2;d_2), c(s_1,s_2;d_1,d_2), c(s_1,d_2;s_2,d_1)$, ie the four mincut quantities. (contd) $\endgroup$
    – user7823
    Commented Jan 4, 2012 at 11:50
  • $\begingroup$ (contd) Then T.C. Hu's theorem says that the multicommodity flow polytope is given by: $R_1,R_2\geq 0, R_1\leq c(s_1;d_1), R_2\leq c(s_2;d_2), R_1+R_2\leq \min\{c(s_1,s_2;d_1,d_2), c(s_1,d_2;s_2,d_1)\}.$ Thus, the polytope has at most three faces in addition to the non-negativity faces. Is there such a constant upper bound for $k=3$? $\endgroup$
    – user7823
    Commented Jan 4, 2012 at 11:50
  • $\begingroup$ Thank you. I misunderstood the definition of the multicommodity flow polytope. I thought it was the set of all feasible flows. $\endgroup$ Commented Jan 4, 2012 at 12:07

1 Answer 1

6
$\begingroup$

This will be a bit long, but please bear with me.

First, let me clarify the terminology a bit. I think what you are interested in here are in fact the facets of the polytope (i.e., "the minimum set of irredundant valid inequalities" or the "maximal dimensional faces still distinct from the polytope itself") rather than the faces. Plus, as you write, the object you study is much better called the "aggregate-flow polytope" or, as some authors refer to it, the "demand polytope" or the "throughput polytope". Call this polytope $T$.

Here is what I know about $T$:

  1. Associated with any capacitated graph $G$ and set of source-destination pairs $(s_k, d_k): k \in 1, \ldots, K$, there is an "aggregate-flow set" $T$.

  2. This $T$ is a polyhedron and it is well-defined. You can see this for yourself by considering the following construction: take the multicommodity-flow polytope (i.e., the polyhedron of the feasible arc-flows or path-flows) and apply an affine mapping that to each commodity orders the sum of the individual flows. As affine maps of polyhedra are again polyhedra, you get the required result.

  3. If $G$ is connected and the edge capacities $c$ are strictly positive, then $T$ is a full-dimensional, compact, convex polyhedron in $\mathbb{R}^n_+$ (so it is in fact a polytope).

  4. $T$ is down-monotone: $t \in T \Rightarrow \forall x \in [0, t]: x \in T$.

  5. You can obtain all the valid inequalities that describe $T$ using the Japanese Theorem due to Onaga and Iri: for any non-negative weight set $w_{ij}: (i,j) \in E$ on the edges $E$ of $G$, the inequality: $$\sum_{k=1}^K \beta_k . t_k \le \sum_{(i,j) \in E} w_{ij} c_{ij} $$ is valid for $T$, where $\beta_k$ denotes the shortest path distance from $s_k$ to $d_k$ for commodity $k$ over the weights $w$, $t_k$ is the aggregate-flow for the $k$th commodity and $c_{ij}$ is the capacity of edge $(i,j)$. In fact, you get all the valid inequalities for $T$ this way.

  6. Any weight set that is not an extreme ray of the below projection cone $W$ generates redundant inequalities for $T$, where $$W = \{(w,\beta): \forall k, \forall P \in \mathcal{P_k}: \sum_{(i,j) \in P} w_{ij} \le \beta_k, w \ge 0\}$$ where $\mathcal{P_k}$ denotes the set of all paths between $s_k$ and $d_k$. This sort of answers your second question.

Now, regarding the number of facets needed to describe $T$.

First, I believe your conjecture "for any $N$ there is a graph for which $T$ has more than $N$ facets" is not true. What we can show is that $T$ has finitely many facets, because the projection cone $W$ has only a finite number of extreme rays, and these generate all the facets (unfortunately, usually many more inequalities too). Note, however that this alone does not disprove your conjecture.

However, that this still allows the number of facets to be exponential, and curiously this is precisely the case. At least for directed graphs, I seem to have a proof somewhere that for the complete bipartite graph $K_{n,n}$ on $n$ nodes with $n$ distinct source nodes in one partition and $n$ distinct destination nodes in the other and capacities all equal to $1$, all the $\{0,1\}^n$ vectors $b$ except for the all-zero vector generate a facet $\sum_n b_n t_n \le q$ for some appropriate $q$, and this gives you $2^{n}-1$ facets. I don't know about the undirected case, the above may either hold or not hold.

For $K=3$ in particular, this gives 7 facets (plus the non-negativity conditions, but that's trivial) for $K_{3,3}$ in the directed case. As far as I can work it out now, the same applies to the undirected case as well. I have fairly good reasons to believe that this is in fact the upper bound for the directed case, but I may be completely wrong here.

You can find an awful lot of results on this topic in Schriver's heroic survey:

Alexander Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Volume 3, Part VII, Multiflows and Disjoint Paths

Should you have any comments, results, or further reading (apart from my own papers) on this topic, count me very very interested.

$\endgroup$
1
  • 2
    $\begingroup$ that's a nice answer ! $\endgroup$ Commented Jan 5, 2012 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.