Basic flow definitions

Basic definitions

1. Basic graph definitions

Basic setting

On this page and all dependent pages, [math]\displaystyle{ G=(V,A) }[/math] is an anti-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. Unless stated otherwise, there are no node or arc attributes except for the upper bounds on arcs.

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 anti-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{ (v,w),(w,v)\in A }[/math], add a new node [math]\displaystyle{ u }[/math] to [math]\displaystyle{ V }[/math], replace [math]\displaystyle{ (v,w) }[/math] by new arcs [math]\displaystyle{ (v,u) }[/math] and [math]\displaystyle{ (u,w) }[/math], and set the attribute values analogously to the case of parallel arcs.

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

In the context of flow problems, this assumption usually 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, at least in the classical types of flow problems.

Feasible flow

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

Capacity constraints:

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\setminus W }[/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].

Feasibility:

1. 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.
2. For [math]\displaystyle{ S,T\subseteq V }[/math], a feasible [math]\displaystyle{ (S,T) }[/math]-flow is a feasible flow with respect to [math]\displaystyle{ W=S\cup T }[/math].
3. For [math]\displaystyle{ s,t\in V }[/math], a feasible [math]\displaystyle{ (s,t) }[/math]-flow is a feasible flow with respect to [math]\displaystyle{ W=\{s,t\} }[/math].

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:(w,v)\in A}f(w,v)-\sum_{w:(v,w)\in A}f(v,w)\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. A node is active if its excess is strictly positive.

Flow value

Let [math]\displaystyle{ S,T\subseteq 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|V_S| }[/math] shows that for all partitions [math]\displaystyle{ (V_S,V_T) }[/math] of [math]\displaystyle{ V }[/math] with [math]\displaystyle{ S\subseteq V_S }[/math], [math]\displaystyle{ T\subseteq V_T }[/math] and [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_S,w\in V_T\atop(w,v)\in A}f(w,v) }[/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 [math]\displaystyle{ (G_f,u_f) }[/math] of [math]\displaystyle{ (G,u) }[/math] with respect to an arc weighting [math]\displaystyle{ f }[/math] is defined as follows: It is [math]\displaystyle{ G_f=(V,A_f) }[/math], and for each arc [math]\displaystyle{ (v,w)\in A }[/math], we have:

1. [math]\displaystyle{ (v,w)\in A_f }[/math] with [math]\displaystyle{ u_f(v,w)=u(v,w)-f(v,w) }[/math] if [math]\displaystyle{ u(v,w)-f(v,w)\gt 0 }[/math].
2. [math]\displaystyle{ (w,v)\in A_f }[/math] with [math]\displaystyle{ u_f(w,v)=f(v,w) }[/math] if [math]\displaystyle{ f(v,w)\gt 0 }[/math].

The value [math]\displaystyle{ u_f(a) }[/math] of an arc [math]\displaystyle{ a\in A_f }[/math]is called the residual capacity of [math]\displaystyle{ a\in A }[/math] with respect to [math]\displaystyle{ f }[/math].

Remark: 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 an obvious way. Since [math]\displaystyle{ G }[/math] is anti-symmetric, this equivalence is one-to-one. 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 simultaneously in the presentation and discussion of the individual algorithms. An implementation of an algorithm may be based on [math]\displaystyle{ (G,f) }[/math] or on [math]\displaystyle{ (G_f,u_f) }[/math] or even on both representations simultaneously.

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 in [math]\displaystyle{ G }[/math], 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 [math]\displaystyle{ (G_f,u_f) }[/math], augmenting [math]\displaystyle{ f }[/math] by [math]\displaystyle{ \varepsilon }[/math] along the ordinary path induced by [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{ \varepsilon }[/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{ u(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.

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

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.