Max-Flow Problems

Standard version

Input:

1. A directed graph [math]\displaystyle{ G=(V,A) }[/math].
2. A source node [math]\displaystyle{ s\in V }[/math] and a target (a.k.a. sink) node [math]\displaystyle{ t\in V }[/math].
3. A nonnegative upper bound (a.k.a. capacity) [math]\displaystyle{ u(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math].

Output: A maximum [math]\displaystyle{ (s,t) }[/math]-flow, that is, a nonnegative value [math]\displaystyle{ f(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math] such that the following two conditions are fulfilled:

1. Capacity constraint: For each arc [math]\displaystyle{ a\in A }[/math], it is [math]\displaystyle{ f(a)\leq u(a) }[/math].
2. Flow conservation condition: For each node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math], it is [math]\displaystyle{ \sum_{a=(v,w)\in A}f(a)-\sum_{a=(w,v)\in A}f(a) }[/math].

Generalizations

1. For each arc [math]\displaystyle{ a\in A }[/math], there is a lower bound [math]\displaystyle{ \ell(a) }[/math], and [math]\displaystyle{ f(a)\geq\all(a) }[/math] is additionally required. The lower bounds need not be nonnegative, so the flow values need not be nonnegative, either. This version may be reduced to the standard version by
2. More than one source and more than one target can be reduced to the standard version by adding a super-source node and a super-target node
3. Usually, the term generalized flow' is reserved for the specific generalization in which for each node [math]\displaystyle{ v\in V\setminus\{vs,t\} }[/math], the ratio of the total sum of all incoming flow an the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).

Remarks

In all variations, assuming that all numbers are integral does not reduce generality.