On max-flow min-cut and integral flow properties for multocommodity flows in directed networks

The multicommodity flow problem can represent many important problems encountered in a wide variety of applications. If the flow of each commodity can take any nonnegative real value, it can be formulated as a linear programming (LP) problem; hence it can be solved in polynomial time or more precisely in strongly polynomial time. However, it is sometimes required to obtain integral flows, and the resulting problem becomes NP-hard for general graphs. For some restricted classes of networks, however, it is known that the LP formulation without adding the integrality constraint always provides an integral solution. This is called the integral flow property. For these classes, therefore, the problem can be solved in polynomial time. So far, some classes of the multicommodity flow problem are known to have the max-flow min-cut property. It is interesting to see that most of these classes have the integral flow property, suggesting strong correlation between these two properties. This paper presents a 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.