On feasibility conditions of multicommodity flows in networks

Abstract

An alternate derivation of the dual condition (called the severance-value condition in this paper) to feasibility of the multicommodity flow problem is given by graph theoretical arguments. That is, a multicommodity flow of given requirements is feasible if and only if the capacity of every severance is no less than its least capacity consumption for the flow. A severance is a set of the edges with nonnegative integer coefficients. Even when the severance-value condition is satisfied by a certain finite subset of severances, the multicommodity flow is shown to be still feasible if each requirement is allowed to be reduced by an appropriate amount <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\mu</tex> . This truncation allowance <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\mu</tex> is estimated in terms of the network topology and the capacity function.