- Input: A graph \(G\text{,}\) vertices \(s_i,t_i\) of \(G\) and quotas \(q_i\in[0,\infty)\) for \(1\leq i\leq k\) and a capacity function \(c\text{.}\)
- Problem: Does there exist a \(k\)-tuple \((f_1,\dots,f_k)\) (called a multicommodity flow) where \(f_i\) is an \((s_i,t_i)\)-flow of value at least \(q_i\) and\begin{equation*} \sum_{i=1}^k|f_i(u,v)| \leq c(u,v) \end{equation*}for all \(u,v\in V(G)\text{?}\)
Section 3.7 Multicommodity Flows
Imagine that there are \(k\) different freight train companies. Each company has a product that they are trying to transport through an intricate network of train tracks from an origin city to a destination city, which may be different for different companies. The companies all have specific quotas in terms of the amount of product that they need to deliver per hour, and each section of track has a maximum capacity of traffic that it can handle per hour. A natural question arises: Can all of the companies reach their quota without exceeding the maximum capacity of any section of track?
This can be modeled as a flow problem in a graph. This problem is also interesting for digraphs, but we will only consider graphs in this section. Because we are dealing with undirected graphs, it will be useful to have a slightly different definition of capacity functions and flows. For a graph \(G\text{,}\) a capacity function will be a mapping \(c:V(G)\times V(G)\to[0,\infty)\) with the properties that \(c(u,v)=0\) if \(uv\notin E(G)\) and \(c(u,v)=c(v,u)\) for all \(u,v\in V(G)\text{.}\) For two vertices \(s,t\in V(G)\text{,}\) and \((s,t)\)-flow is a function \(f:V(G)\times V(G)\to \mathbb{R}\) with the property that \(f(u,v)=-f(v,u)\) for all vertices \(u,v\in V(G)\) and \(\sum_{v\in V(G)}f(u,v)=0\) for all \(u\in V(G)\setminus \{s,t\}\text{.}\) The value of an \((s,t)\)-flow \(f\) is \(\sum_{v\in V(G)}f(s,v)\text{.}\) The focus of this section is on the following decision problem, where \(k\) is a positive integer.
Problem 3.7.1. The \(k\)-Commodity Flow Problem.
Here, we take the absolute value of the flow because different commodities may flow in different directions along the same edge and these flows do not “cancel out.” Of course, in the case \(k=1\text{,}\) tis problem simply reduces to the max-flow problem from the previous section. Interestingly, the conditions required for a multicommodity flow to exist are more complicated than in the max-flow min-cut theorem. The natural analogue of the min-cut condition is that, for any set \(U\subseteq V(G)\text{,}\) the total capacity of the edges from \(U\) to \(V(G)\setminus U\) cannot be smaller than the sum over all \(i\) such that \(s_i\) and \(t_i\) are on different sides of the cut \((U,V(G)\setminus U)\text{.}\) In other words, if we let \(\sep_U(s_i,t_i)\) be equal to \(1\) if \(s_i\) and \(t_i\) are on different sides of the cut \((U,V(G)\setminus U)\) and \(0\) otherwise, then
\begin{equation}
\sum_{u\in U, v\in V(G)\setminus U}c(u,v) \geq \sum_{i=1}^k q_i \cdot \sep_U(s_i,t_i) \text{ for every set }U\subseteq V(G).\tag{3.7.1}
\end{equation}
As it turns out, while (3.7.1) is sufficient in the case \(k=1\) (i.e. in the setting of the usual max-flow min-cut theorem), it is not sufficient for general \(k\text{.}\) An example which demonstrates this can be found in Figure 9.2 of Schrijver (here, all capacities and quotas are equal to \(1\)).
While the cut condition is no longer the correct “dual problem” for multicommodity flows in general, it is nonetheless possible to solve Problem 3.7.1 in polynomial time via a linear programming reduction; see Exercise 42. However, the LP will provide a fractional solution which, in reality, may not be very practical. For example, the fractional solution may have the property that all of the flows \(f_i\) send a tiny amount of flow along a huge number of paths from \(s_i\) to \(t_i\) in the graph. In solving the freight train problem described earlier, a solution of this type would be extremely complicated to implement in practice. It is therefore natural to ask whether a more “well-behaved” multicommodity flow. In particular, it would be particularly nice to have multicommodity flow that is integer-valued or, if that is not possible, then it is desirable for it to be as “close” to integer-valued as possible.
Unfortunately, even in the case that \(k=2\) and all of the capacities are equal to \(1\text{,}\) the problem of finding an integer-valued multicommodity flow is NP-complete! In other words, it is NP-complete to determine whether, for a graph \(G\) and vertices \(s_1,t_1,s_2,t_2\) of \(G\text{,}\) there exist edge disjoint paths paths, one from \(s_1\) to \(t_1\) and one from \(s_2\) to \(t_2\text{.}\)
1
Miraculously, if you change “edge disjoint” to “vertex disjoint” here, then the problem becomes polynomial-time solvable for all \(k\text{.}\)
For this reason, unfortunately, we do not have much hope to find a polynomial-time algorithm for determining whether or not there is an integer-valued multicommodity flow. However, we will be able to prove the following surprising result of Hu in the case of two commodoties. Say that a real number \(x\) is half-integer if there exists an integer \(m\) such that \(x=m/2\text{.}\) As it turns out, not only can we always find half-integer 2-commodity flows, but the cut condition (3.7.1) is necessary and sufficient for being able to do so.
Theorem 3.7.2. Hu’s Two Commodity Flow Theorem.
For an instance of the 2-commodity flow problem with integer-valued capacities and quotas, there exists a half-integer-valued multicommodity flow \((f_1,f_2)\) if and only if (3.7.1) is satisfied. Moreover, such a multicommodity flow can be found in polynomial time.Proof.
The trick in this proof is to solve the max-flow problem twice by viewing the commodities as one commodity in two different ways and then to observe that these two flows, if they exist, can be cleverly combined to yield a half-integer-valued 2-commodity flow. Moreover, if these one of these two flows does not exist, then it will turn out that (3.7.1) is violated.
First, add two vertices \(s\) and \(t\) to the graph and add edges of capacity \(q_i\) from \(s\) to \(s_i\) and from \(t\) to \(t_i\) for each \(i\in\{1,2\}\text{.}\) If there exists a flow of value \(q_1+q_2\) from \(s\) to \(t\text{,}\) then let \(g\) be such a flow. If such a flow \(g\) does not exist, then there must be an \((s,t)\)-cut of capacity less that \(q_1+q_2\text{.}\) We claim that this would violate (3.7.1). Indeed, this cut cannot only have \(s\) on one side as, if so, the capacity would be exactly \(q_1+q_2\text{.}\) So, at least one of \(s_1\) or \(s_2\) are on the same side of the cut as \(s\text{.}\) Similarly, at least one of \(t_1\) or \(t_2\) is on the same side as \(t\text{.}\) When deleting \(s\) and \(t\text{,}\) either the capacity of the cut
- does not change, if \(s,s_1,s_2\) are all on the same side and so are \(t,t_1,t_2\text{,}\) or
- it changes by precisely \(q_1\) or \(q_2\text{,}\) otherwise.
In either case, it yields a cut in the original graph that violates (3.7.1). So, we assume from here forward that such a flow \(g\) exists. We may also assume that \(g\) is integer valued (this essentially follows from the Integral Flow Theorem; it can also be seen by replacing each edge \(uv\) with \(c(u,v)\) copies and applying Menger’s Theorem).
Now, we repeat the same thing, except that this time we add a vertex \(a\) adjacent to \(s_1\) by an edge of capacity \(q_1\) and \(t_2\) by an edge of capacity \(q_2\) and a vertex \(b\) adjacent to \(t_1\) by an edge of capactiy \(q_1\) and \(s_2\) by an edge of capacity \(q_2\text{.}\) Similarly to above, if there is no \((a,b)\) flow of value \(q_1+q_2\text{,}\) then (3.7.1) would be violated. So, we let \(h\) be such a flow and, as before, assume that it is integer valued.
Now, define
\begin{equation*}
f_1:=\frac{1}{2}(g+h),
\end{equation*}
\begin{equation*}
f_2:=\frac{1}{2}(g-h).
\end{equation*}
It is clear that each of \(f_1\) and \(f_2\) are half-integer-valued. We claim that \((f_1,f_2)\) is a 2-commodity flow which respects the capacity function such that \(f_i\) has value \(q_i\) for \(i\in\{1,2\}\text{.}\) The flow out of \(s_1\) or and into \(t_1\) under both flows is \(q_1\) by construction; so, \(f_1\) has this property as well. The flow out of \(s_1\) and into \(t_1\) under \(g\) is \(q_2\) and under \(h\) is \(-q_2\text{;}\) so, they cancel in the definition of \(f_1\text{.}\) Also, for any other vertex \(v\text{,}\) the incoming flow at \(v\) is equal to the outgoing flow at \(v\) in both \(g\) and \(h\) and so this property is shared by \(f_1\text{.}\) Thus, \(f_1\) is an \((s_1,t_1)\)-flow of value \(q_1\text{;}\) a similar argument shows that \(f_2\) is an \((s_2,t_2)\)-flow of value \(q_2\text{.}\)
So, all that remains is to verify the edge capacities are respected. For any edge \(uv\in E(G)\text{,}\) we have
\begin{equation*}
|f_1(u,v)|+|f_2(u,v)| =\frac{1}{2}|g(u,v)+h(u,v)| + \frac{1}{2}|g(u,v)-h(u,v)| = \max\{|g(u,v)|,|h(u,v)|\} \leq c(u,v)
\end{equation*}
by construction of \(g\) and \(h\text{.}\) Here, we used the fact that \(\frac{1}{2}|x+y| + \frac{1}{2}|x-y|=\max\{|x|,|y|\}\) for any real numbers \(x,y\text{.}\) Since each of \(g\) and \(h\) can be found in polynomial time, so can \((f_1,f_2)\text{.}\) This completes the proof.
As it turns out, we can actually achieve an integer-valued 2-commodity flow if we additionally assume that the capacity function \(c\) satisfies
\begin{equation*}
\sum_{v\in V(G)}c(u,v) = \begin{cases} q_1 \amp \text{if }u\in \{s_1,t_1\}, \\ q_2 \amp \text{if }u\in \{s_2,t_2\},\\ 0\bmod 2 \amp\text{ otherwise}.
\end{cases}
\end{equation*}
If we think of each edge \(uv\) being replaced by \(c(u,v)\) copies, then this is precisely the condition that characterizes the connected graphs which have Eulerian tours. So, let us say that a capacity function with this property is Eulerian.
Theorem 3.7.3. Rothschild and Whinston.
For an instance of the 2-commodity flow problem with Eulerian capacity function and integer-valued capacities and quotas, there exists an integer-valued multicommodity flow \((f_1,f_2)\) if and only if (3.7.1) is satisfied. Moreover, such a multicommodity flow can be found in polynomial time.Proof.
Find the flows \(g\) and \(h\) as in the proof of Theorem 3.7.2. We claim that we can always find \(g\) and \(h\) so that they additionally satisfy \(g(u,v)\equiv h(u,v)\equiv c(u,v)\bmod 2\) for all \(uv\in E(G)\text{.}\) If we can do this, then, by defining \(f_1\) and \(f_2\) as in Theorem 3.7.2, we will actually obtain integer-valued flows.
To this end, let \(X\) be the set of all edges \(uv\) of \(G\) such that \(g(u,v)\not\equiv c(u,v)\bmod 2\text{.}\) For each vertex \(u\text{,}\) let \(d_X(u)\) be the number of edges of \(X\) incident with \(u\text{.}\) Then \(d_X(u)\) is the sum of \(g(u,v)-c(u,v)\) reduced modulo \(2\) over all \(v\in V(G)\text{.}\) Thus,
\begin{equation*}
d_X(u)\equiv\sum_{v\in V(G)}\left(g(u,v)-c(u,v)\right)\bmod 2.
\end{equation*}
If \(u\in\{s_1,s_2,t_1,t_2\}\text{,}\) then the right side is zero by the fact that \(g\) came from a flow of value \(q_1+q_2\) from \(s\) to \(t\) and the fact that the sum of capacities of arcs incident with \(u\) is \(q_1\) or \(q_2\) (whichever is appropriate). For other vertices \(u\text{,}\) the right side is \(0\bmod 2\) due to the fact that \(g\) satisfies the flow condition and \(c\) is Eulerian. So, \(d_X(u)\) is even for every vertex \(u\text{.}\) If \(X\neq \emptyset\text{,}\) then there exists a cycle in \((V(G),X)\text{.}\) We can then follow along this cycle and increase the flow value on each edge by \(1\text{.}\) Since \(g\) originally respected the capacity function and \(g(u,v)\neq c(u,v)\) for every edge on this cycle, the new flow respects the capacity function. We can repeat this until \(X=\emptyset\text{.}\) The function \(h\) can be dealt with similarly.
