Max-Flow Problems

Assumptions

For convenience, without loss of generality:

1. In all variations below, all numbers are integral: real numbers may be approximated by uniformly distant numbers with a negligible loss of precision.
2. There are no parallel arcs in directed graphs [math]\displaystyle{ G=(V,A) }[/math]: if there are parallel arcs, they may be replaced by one of them, with their upper bounds, lower bounds, and flow values summed up, respectively. In particular, an arc may be identified with the ordered pair [math]\displaystyle{ (v,w) }[/math]consisting of the arc's tail [math]\displaystyle{ v\in V }[/math] and head [math]\displaystyle{ w\in V }[/math].
3. For each arc [math]\displaystyle{ (v,w)\in A }[/math], there is also a reverse arc [math]\displaystyle{ (w,v)\in A }[/math]: if not, just add one with upper (and lower) bound zero.

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:

1. The flow is feasible 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].

2. Among all feasible flows, [math]\displaystyle{ f }[/math] has maximum flow value, which is defined as

   [math]\displaystyle{ v(f):=\sum_{(s,v)\in A}f(s,v)-\sum_{(v,s)\in A}f(v,s)=\sum_{(v,t)\in A}f(v,t)-\sum_{(t,v)\in A}f(t,v) }[/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\ell(a) }[/math] is additionally required. The lower bounds need not be nonnegative, so the flow values need not be nonnegative, either. This version is often called maximum flow with edge demands. It may be reduced to solving two instances of the standard version as follows:
   1. First, we construct a new graph [math]\displaystyle{ G'=(V',A') }[/math] as follows: We add a super-source [math]\displaystyle{ s' }[/math] and a super-target [math]\displaystyle{ t' }[/math] to [math]\displaystyle{ V }[/math]. Next, for every node [math]\displaystyle{ v\in V }[/math], we add an arc [math]\displaystyle{ (s,v) }[/math] and an arc [math]\displaystyle{ (v,t) }[/math] to [math]\displaystyle{ A }[/math]. Finally we add an arc [math]\displaystyle{ (t,s) }[/math] to [math]\displaystyle{ A }[/math], if not in [math]\displaystyle{ A }[/math] yet.
   2. For all arcs [math]\displaystyle{ a\in A }[/math], we set [math]\displaystyle{ \ell'(a):=0 }[/math]. For each node [math]\displaystyle{ v\in V }[/math], we set

      [math]\displaystyle{ u'(s,v):=\sum_{(w,v)\in A}\ell(w,v) }[/math] and [math]\displaystyle{ u'(v,t):=\sum_{(v,w)\in A} \ell(v,w) }[/math].

      For all arcs [math]\displaystyle{ a\in A }[/math], we set [math]\displaystyle{ u'(a):=u(a)-\ell(a) }[/math]. Finally, we set [math]\displaystyle{ u'(t,s):=+\infty }[/math].

   3. It is easy to see that there is a feasible [math]\displaystyle{ (s,t) }[/math]-flow [math]\displaystyle{ f }[/math] in [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ \ell }[/math] and [math]\displaystyle{ u }[/math] if, and only if, all arcs [math]\displaystyle{ (s',\cdot) }[/math] and [math]\displaystyle{ (\cdot,t') }[/math] are saturated. This the case if, and only if, the maximum flow [math]\displaystyle{ f' }[/math] in [math]\displaystyle{ G }[/math] from [math]\displaystyle{ s' }[/math] to [math]\displaystyle{ t' }[/math] with respect to [math]\displaystyle{ \ell' }[/math] and [math]\displaystyle{ u' }[/math] yields a flow of value [math]\displaystyle{ \sum_{a\in A}\ell(a) }[/math].
   4. More specifically, for [math]\displaystyle{ (v,w)\in A }[/math], we set [math]\displaystyle{ f(v,w):=f'(v,w)+\ell(v,w) }[/math].
2. More than one source and more than one target can be reduced to the standard version by adding a super-source node [math]\displaystyle{ s }[/math], a super-target node [math]\displaystyle{ t }[/math], an arc [math]\displaystyle{ (s,v) }[/math] with "infinite" capacity for each source [math]\displaystyle{ v }[/math], and an arc [math]\displaystyle{ (v,t) }[/math] with "infinite" capacity for each target [math]\displaystyle{ v }[/math].
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).
4. The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be send as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Basic definitions

1. Consider an instance