Basic flow definitions

Basic setting

On this page and all dependent pages, [math]\displaystyle{ G=(V,A) }[/math] is a symmetric, simple directed graph, unless stated otherwise. For [math]\displaystyle{ a\in A }[/math], there is a nonnegative upper bound [math]\displaystyle{ u(a) }[/math]. In some flow problems, there is a lower bound [math]\displaystyle{ \ell(a) }[/math] as well, which need not be nonnegative. It is then required [math]\displaystyle{ \ell(a)\leq f(a)\leq u(a) }[/math], so [math]\displaystyle{ f(a) }[/math] may be negative if [math]\displaystyle{ \ell(a) }[/math] is so. In some flow problems, there is a real-valued (not necessarily nonnegative) cost factor [math]\displaystyle{ c(a) }[/math]. Other node and arc attributes may be occur in specific flow problems.

Remark: Simplicity and symmetry do not reduce generality in the context of flow problems:

1. If there are two arcs [math]\displaystyle{ a_1 }[/math] and [math]\displaystyle{ a_2 }[/math], say, from [math]\displaystyle{ v }[/math] to </math>w</math>, add a new node [math]\displaystyle{ u }[/math] to [math]\displaystyle{ V }[/math], replace [math]\displaystyle{ a_1 }[/math] by new arcs [math]\displaystyle{ (v,u) }[/math] and [math]\displaystyle{ (u,w) }[/math], take the upper bound, the
2. Analogously, if there is a loop [math]\displaystyle{ (v,v) }[/math], add a new node [math]\displaystyle{ w }[/math] to [math]\displaystyle{ V }[/math], replace [math]\displaystyle{ (v,v) }[/math] by [math]\displaystyle{ (v,w) }[/math] and [math]\displaystyle{ (w,v) }[/math],

If [math]\displaystyle{ (w,v)\not\in A }[/math] for some [math]\displaystyle{ (v,w)\in A }[/math], we may add [math]\displaystyle{ (w,v) }[/math] with zero upper bound.

Integrality assumption: All numerical node and arc attributes are integral.

In the context of flow problems, this assumption does not reduce generality, either: Choosing a sufficiently small [math]\displaystyle{ \delta\gt 0 }[/math] and replacing each attribute value by the nearest integral multiple of [math]\displaystyle{ \delta }[/math] has a negligible impact on the output.

Residual network

The residual network of [math]\displaystyle{ (G,u) }[/math] with respect to [math]\displaystyle{ f }[/math] is the pair [math]\displaystyle{ (G_f,u_f) }[/math], where [math]\displaystyle{ u_f }[/math] is defined by [math]\displaystyle{ u_f(v,w):=u(v,w)-f(v,w)+f(w,v) }[/math] for all [math]\displaystyle{ (v,w)\in A' }[/math]. The value [math]\displaystyle{ u_f(a) }[/math] is called the residual capacity of [math]\displaystyle{ a\in A }[/math] with respect to [math]\displaystyle{ f }[/math]. The graph [math]\displaystyle{ G_f }[/math] consists of all nodes of [math]\displaystyle{ G }[/math] and, specifically, of all arcs of [math]\displaystyle{ G }[/math] with positive residual capacities.

Remarks:

1. Roughly speaking, the residual capacity of an arc [math]\displaystyle{ (v,w)\in A }[/math] is the amount by which the net flow from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] could be increased within the capacity constraints solely by increasing the flow value of [math]\displaystyle{ (v,w) }[/math] and decreasing the flow value of [math]\displaystyle{ (w,v) }[/math].
2. Changes of [math]\displaystyle{ f }[/math] in [math]\displaystyle{ G }[/math] and changes of [math]\displaystyle{ u_f }[/math] in [math]\displaystyle{ G_f }[/math] are equivalent in a one-to-one correspondence. So, the view on [math]\displaystyle{ G }[/math] and [math]\displaystyle{ f }[/math] is exchangeable with the view on [math]\displaystyle{ G_f }[/math] and [math]\displaystyle{ u_f }[/math]. We will adopt both views in the discussion of the individual algorithms.

Flow-augmenting paths and saturated arcs

A flow-augmenting path (or augmenting path for short) from some node [math]\displaystyle{ s\in V }[/math] to some node [math]\displaystyle{ t\in V }[/math] is an ordinary path in the residual network [math]\displaystyle{ G_f }[/math]. Equivalently, a flow-augmenting path is a generalized path in [math]\displaystyle{ G }[/math] such that:

1. [math]\displaystyle{ f(a)\lt u(a) }[/math] if [math]\displaystyle{ a\in A }[/math] is a forward arc;
2. [math]\displaystyle{ f(a)\gt 0 }[/math] if [math]\displaystyle{ a\in A }[/math] is a backward arc.

An arc [math]\displaystyle{ a\in A }[/math] is saturated

1. in forward direction if [math]\displaystyle{ f(a)=u(a) }[/math].
2. in backward direction if [math]\displaystyle{ f(a)=0 }[/math].

We say that an arc of a path is saturated if it is saturated in the direction of this path. Clearly, a path is augmenting if, and only if, it contains no saturated arc in its direction.

Augmenting along a path

Let [math]\displaystyle{ p }[/math] denote some flow-augmenting path, and let [math]\displaystyle{ \varepsilon\gt 0 }[/math] such that

1. [math]\displaystyle{ f(a)+\varepsilon\leq u(a) }[/math] if [math]\displaystyle{ a\in A }[/math] is a forward arc;
2. [math]\displaystyle{ f(a)-\varepsilon\geq 0 }[/math] if [math]\displaystyle{ a\in A }[/math] is a backward arc.

In the residual network, augmenting [math]\displaystyle{ f }[/math] by [math]\displaystyle{ \varepsilon }[/math] along [math]\displaystyle{ p }[/math] means reducing all residual capacities by [math]\displaystyle{ \varepsilon }[/math]. Equivalently, for each arc [math]\displaystyle{ a \in A }[/math] on [math]\displaystyle{ p }[/math] in [math]\displaystyle{ G }[/math], this means:

1. Increase the flow value by [math]\displaystyle{ \varepsilon }[/math] if [math]\displaystyle{ a }[/math] is a forward arc on [math]\displaystyle{ p }[/math].
2. Decrease the flow value by [math]\displaystyle{ \min \{x,y \} }[/math] if [math]\displaystyle{ a }[/math] is a backward arc on [math]\displaystyle{ p }[/math].

Obviously, the capacity constraints are preserved. The flow conservation conditions are preserved at every internal node of [math]\displaystyle{ p }[/math]. To see that, let [math]\displaystyle{ v }[/math] be such an internal node, and let [math]\displaystyle{ u }[/math] and [math]\displaystyle{ w }[/math] denote the immediate predecessor and successor of [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math], respectively. Basically, there are four cases:

• Either [math]\displaystyle{ (u,v) }[/math] is on [math]\displaystyle{ p }[/math] as a forward arc or [math]\displaystyle{ (v,u) }[/math] is on [math]\displaystyle{ p }[/math] as a backward arc.
• Either [math]\displaystyle{ (v,w) }[/math] is on [math]\displaystyle{ p }[/math] as a forward arc or [math]\displaystyle{ (w,v) }[/math] is on [math]\displaystyle{ p }[/math] as a backward arc.

It is easy to check preservation of the flow conservation conditions at [math]\displaystyle{ v }[/math] for each of these four cases.

Augmenting up to saturation: Again, let [math]\displaystyle{ p }[/math] denote some flow-augmenting path.

1. Let [math]\displaystyle{ \varepsilon_1\gt 0 }[/math] denote the minimum of the values [math]\displaystyle{ c(a)-f(a) }[/math] on all forward arcs of [math]\displaystyle{ p }[/math].
2. Let [math]\displaystyle{ \varepsilon_2\gt 0 }[/math] denote the minimum of the values [math]\displaystyle{ f(a) }[/math] on all backward arcs of [math]\displaystyle{ p }[/math].
3. Let [math]\displaystyle{ \varepsilon }[/math] denote the minimum of [math]\displaystyle{ \varepsilon }[/math] and [math]\displaystyle{ \varepsilon_2 }[/math].

Augmenting the flow [math]\displaystyle{ f }[/math] along [math]\displaystyle{ p }[/math] by [math]\displaystyle{ \varepsilon }[/math] yields at least one saturated arc.

Preflow

Preflows generalize ordinary flows as follows: Instead of an equation, the following inequality is to be fulfilled:

[math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)\leq\sum_{w:(w,v)\in A}f(w,v) }[/math].

The excess of [math]\displaystyle{ v\in V }[/math] is the difference between the right-hand side and the left-hand side of that inequality.

Valid distance labeling

Definition:

1. Let [math]\displaystyle{ G=(V,A)) }[/math] be a directed graph, and for each arc [math]\displaystyle{ a\in A }[/math] let [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be defined such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math]. An assignment of a value [math]\displaystyle{ d(v) }[/math] to each node [math]\displaystyle{ v\in V }[/math] is a valid distance labeling if the following two conditions ar fulfilled:
   1. It is [math]\displaystyle{ d(t)=0 }[/math].
   2. For each arc [math]\displaystyle{ (v,w)\in A }[/math] in the residual network, it is [math]\displaystyle{ d(v)\leq d(w)+1 }[/math].
2. If even [math]\displaystyle{ d(v)=d(w)+1 }[/math], [math]\displaystyle{ (v,w) }[/math] is called an admissible arc.

Blocking flow

Definition: Let [math]\displaystyle{ G=(V,A) }[/math] be a directed graph, let [math]\displaystyle{ s,t\in V }[/math], and for each arc [math]\displaystyle{ a\in A }[/math] let [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be real values such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math]. We say that [math]\displaystyle{ f }[/math] is a blocking flow if every flow augmenting [math]\displaystyle{ (s,t) }[/math]-path contains at least one backward arc.

Remarks:

1. The name refers to an alternative, equivalent definition: Every ordinary [math]\displaystyle{ (s,t) }[/math]-path contains at least one saturated arc, which "blocks" the augmentation.
2. Obviously, maximum flows are blocking flows, but not vice versa.

Cuts and saturated cuts

1. Let [math]\displaystyle{ G=(V,A) }[/math] be a directed graph and [math]\displaystyle{ s,t\in V }[/math]. An [math]\displaystyle{ (s,t) }[/math]-cut (or cut for short) is a bipartition [math]\displaystyle{ (S,T) }[/math] of [math]\displaystyle{ V }[/math] such that [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\in T }[/math].
2. For [math]\displaystyle{ a\in A }[/math], let [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be real values such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] ([math]\displaystyle{ f }[/math] need not be a flow here). A cut [math]\displaystyle{ (S,T) }[/math] is saturated if:
   1. [math]\displaystyle{ f(v,w)=u(v,w) }[/math] for every arc [math]\displaystyle{ (v,w)\in A }[/math] such that [math]\displaystyle{ v\in S }[/math] and [math]\displaystyle{ w\in T }[/math].
   2. [math]\displaystyle{ f(v,w)=0 }[/math] for every arc [math]\displaystyle{ (v,w)\in A }[/math] such that [math]\displaystyle{ v\in T }[/math] and [math]\displaystyle{ w\in S }[/math].