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.

1. For [math]\displaystyle{ a\in A }[/math], there is a nonnegative upper bound [math]\displaystyle{ u(a) }[/math].
2. In some flow problems, there is a lower bound [math]\displaystyle{ \ell(a) }[/math] as well, which need not be nonnegative.
3. In some flow problems, each node [math]\displaystyle{ v\in V }[/math] has a required balance (or balance for short) [math]\displaystyle{ b(v) }[/math]. We also speak of the node balance.
4. 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 occur in specific flow problems.

Neutral values of attributes: When a node or arc is added to a graph, it is sometimes appropriate to set its attributes to neutral values. The neutral values for upper and lower bounds are [math]\displaystyle{ +\infty }[/math] and [math]\displaystyle{ -\infty }[/math], respectively. For cost factors and node balances, the neutral value is zero.

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]\displaystyle{ 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], transfer the attribute values of [math]\displaystyle{ a_1 }[/math] to [math]\displaystyle{ (v,u) }[/math] and set all attributes of [math]\displaystyle{ u }[/math] and of [math]\displaystyle{ (u,w) }[/math] to their neutral values.
2. 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], and set the attribute values analogously to the case of parallel arcs.
3. 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 and lower 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.

Feasible flow and flow value

Capacity constraints: Let [math]\displaystyle{ f }[/math] be an arc weighting, that is, a value [math]\displaystyle{ f(a) }[/math] is given for each arc [math]\displaystyle{ a\in A }[/math].

1. We say that [math]\displaystyle{ f }[/math] fulfills the capacity constraints if [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
2. If lower bounds [math]\displaystyle{ \ell }[/math] are given, the condition [math]\displaystyle{ f(a)\geq 0 }[/math] is to be replaced by [math]\displaystyle{ f(a)\geq\ell(a) }[/math]. In particular, [math]\displaystyle{ f(a) }[/math] may be negative if [math]\displaystyle{ \ell(a) }[/math] is so.

Flow conservation condition: Let [math]\displaystyle{ W\subseteq V }[/math].

1. An arc weighting fulfills the flow conservation condition with respect to [math]\displaystyle{ W }[/math] if for all nodes [math]\displaystyle{ v\in V }[/math]: [math]\displaystyle{ \sum_{w\in V\atop(v,w)\in A}f(v,w)-\sum_{w\in V\atop(w,v)\in A}f(w,v)=0 }[/math].
2. If there are balance values [math]\displaystyle{ b(v) }[/math] for all nodes [math]\displaystyle{ v\in V\setminus W }[/math], the right-hand side of this condition is not zero but [math]\displaystyle{ b(v) }[/math].

A feasible flow (or flow for short) with respect to [math]\displaystyle{ W\subseteq V }[/math] is an arc weighting that satisfies the capacity constraints and the flow conservation condition.

Preflow

1. Preflows generalize feasible flows as follows: Instead of an equation, the following inequality is to be fulfilled for each [math]\displaystyle{ v\in V\setminus W }[/math]: [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\geq 0 }[/math] (resp., [math]\displaystyle{ \geq b(v) }[/math], if node balances are given).
2. The excess of [math]\displaystyle{ v\in V\setminus W }[/math] is the value of the left-hand side of that inequality.

Flow value

Let [math]\displaystyle{ S,T\in V }[/math] such that [math]\displaystyle{ S\cap T=\emptyset }[/math], and let [math]\displaystyle{ f }[/math] be a flow with respect to [math]\displaystyle{ S\cup T }[/math]. The flow value [math]\displaystyle{ v(f) }[/math] of [math]\displaystyle{ f }[/math] is defined by

[math]\displaystyle{ v(f):=\sum_{s\in S,v\in V\setminus S\atop(s,v)\in A}f(s,v)-\sum_{s\in S,v\in V\setminus S\atop(v,s)\in A}f(v,s) }[/math].

Remark: A straightforward induction on [math]\displaystyle{ k\geq|S| }[/math] shows that for all partitions [math]\displaystyle{ (V_S,V_T) }[/math] of [math]\displaystyle{ V }[/math] with [math]\displaystyle{ |V_S|=k }[/math], it is

[math]\displaystyle{ v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_T,w\in V_S\atop(v,w)\in A}f(v,w) }[/math].

In particular, mirror-symmetrically to the definition of [math]\displaystyle{ v(f) }[/math], it is

[math]\displaystyle{ v(f)=\sum_{v\in V\setminus T,t\in T\atop(v,t)\in A}f(v,t)-\sum_{v\in V\setminus T,t\in T\atop(t,v)\in A}f(t,v) }[/math].

Residual network

The residual network of [math]\displaystyle{ (G,u) }[/math] with respect to an arc weighting [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.

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].