A new min-cut max-flow ratio for multicommodity flows

Abstract

In this paper we present a new bound on the min-cut max-flow ratio for multicommodity flow problems with specified demands. For multicommodity flows, this is a generalization of the well-known relationship between the capacity of a minimum cut and the value of the maximum flow of a single commodity flow problem. For multicommodity flows, capacity of a cut is scaled by the demand that has to cross the cut to obtain the numerator of this ratio. In the denominator, the maximum concurrent flow value is used. Currently, the best known bound for this ratio is proportional to log(k), where k is the number of origin-destination pairs with positive demand. Our new bound is proportional to log(k*), where k* is the cardinality of the minimum cardinality vertex cover of the demand graph. To obtain this bound, we start with a so-called aggregated commodity formulation of the maximum concurrent flow problem with k* commodities. We also show a similar bound for the maximum multicommodity flow problem. The new bound is proportional to min{log(k*), k**}, where k** denotes the size of the minimum cardinality complete bipartite subgraph cover of the demand graph. © 2007 Society for Industrial and Applied Mathematics.