On max-flow min-cut and integral flow properties for multicommodity flows in directed networks (Q1262198)

We study the condition for a class of directed networks, under which the max-flow min-cut property for the multicommodity flow problem implies the integral flow property. Let \({\mathcal N}\) denote the set of all directed networks \(N=(G,P,g,c)\) defined as follows. G(A,V): A finite directed graph, where V is a set of nodes, and A is a set of directed arcs. P: A set of source-sink ordered pairs \((s^ k,t^ k)\), \(k=1,2,...,K\), g: \(\{1,2,...,K\}\to {\mathbb{Z}}^+\) \((=\) the set of nonnegative integers). c: \(A\to {\mathbb{Z}}^+\) is a capacity function of arcs. The multicommodity flow problem in a directed network \(N\in {\mathcal N}\) is feasible if there exists a flow f: \(A\times \{1,2,...,K\}\to {\mathbb{R}}^+\) \((=\) the set of nonnegative real numbers), which satisfies the flow conservation law and the side capacity constraint. A flow f is called an integral flow if \(f(a,k)\to {\mathbb{Z}}^+\) for all \(a\in A\), \(k=1,2,...,K.\) A class of networks \(Q\subseteq {\mathcal N}\) has the integral flow property if there exists an integral flow for any feasible network N in Q. A class of networks \(Q\subseteq {\mathcal N}\) has the max-flow min-cut property if any network N in Q is feasible if and only if the cut condition holds. A class \(Q\subseteq {\mathcal N}\) is called capacity and demand independent if, for any network \(N=(G(V,A),P,g,c)\) in Q, every network \(N'=(G,P,g',c')\) with \(g\geq g'\geq 0\) and \(c\geq c'\geq 0\) (the sign \(\geq\) between two vectors means inequality in every component) also belongs to class Q. Then, we can prove that if a capacity and demand independent class \(Q\subseteq {\mathcal N}\) has the max-flow min-cut property, then Q satisfies the integral flow property.