Basic flow definitions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(83 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Definition ==
== Basic definitions ==
On this page and all dependent pages, <math>G=(V,A)</math> is a [[Basic graph definitions#Directed and undirected graphs|symmetric, simple directed graph]], unless said otherwise. For <math>a\in A</math>, there are real values <math>u(a)</math> and <math>f(a)</math> such that <math>0\leq f(a)\leq u(a)</math>. The value <math>u(a)</math> is the '''upper bound''' of <math>a</math>.
 
# [[Basic graph definitions]]
 
== Basic setting ==
On this page and all dependent pages, <math>G=(V,A)</math> is an [[Basic graph definitions#Directed and undirected graphs|anti-symmetric, simple directed graph]], unless stated otherwise.  
# For <math>a\in A</math>, there is a nonnegative '''upper bound''' <math>u(a)</math>.
# In some flow problems, there is a '''lower bound''' <math>\ell(a)</math> as well, which need not be nonnegative.
# In some flow problems, each node <math>v\in V</math> has a '''required balance''' (or '''balance''' for short) <math>b(v)</math>. We also speak of the '''node balance'''.
# In some flow problems, there is a real-valued (not necessarily nonnegative) '''cost factor''' <math>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>+\infty</math> and <math>-\infty</math>, respectively. For cost factors and node balances, the neutral value is zero.


'''Remark:'''
'''Remark:'''
Simplicity and symmetry do not reduce generality. In fact, parallel arcs can be united with the upper bounds summed up. And if <math>(w,v)\not\in A</math> for some <math>(v,w)\in A</math>, we may add <math>(w,v)</math> with zero upper bound.
[[Basic graph definitions#Directed and undirected graphs|Simplicity and anti-symmetry]] do not reduce generality in the context of flow problems:
# If there are two arcs <math>a_1</math> and <math>a_2</math>, say, from <math>v</math> to <math>w</math>, add a new node <math>u</math> to <math>V</math>, replace <math>a_1</math> by new arcs <math>(v,u)</math> and <math>(u,w)</math>, transfer the attribute values of <math>a_1</math> to <math>(v,u)</math> and set all attributes of <math>u</math> and of <math>(u,w)</math> to their neutral values.
# If there is a loop <math>(v,v)</math>, add a new node <math>w</math> to <math>V</math>, replace <math>(v,v)</math> by <math>(v,w)</math> and <math>(w,v)</math>, and set the attribute values analogously to the case of parallel arcs.
# If <math>(v,w),(w,v)\in A</math>, add a new node <math>u</math> to <math>V</math>, replace  <math>(v,w)</math> by new arcs <math>(v,u)</math> and <math>(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.


== Residual network ==
In the context of flow problems, this assumption usually does not reduce generality, either: Choosing a sufficiently small <math>\delta>0</math> and replacing each attribute value by the nearest integral multiple of <math>\delta</math> has a negligible impact on the output, at least in the classical types of flow problems.


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


'''Remarks:'''
Let <math>f</math> be an arc weighting, that is, a value <math>f(a)</math> is given for each arc <math>a\in A</math>.
# Roughly speaking, the residual capacity of an arc <math>(v,w)\in A</math> is the amount by which the net flow from <math>v</math> to <math>w</math> could be increased within the capacity constraints solely by increasing the flow value of <math>(v,w)</math> and decreasing the flow value of <math>(w,v)</math>.
# Changes of <math>f</math> in <math>G</math> and changes of <math>u_f</math> in <math>G_f</math> are equivalent in a one-to-one correspondence. So, the view on <math>G</math> and <math>f</math> is exchangeable with the view on <math>G_f</math> and <math>u_f</math>. We will adopt both views in the discussion of the individual algorithms.


== Flow-augmenting path ==
'''Capacity constraints:'''
# We say that <math>f</math> fulfills the '''capacity constraints''' if <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# If lower bounds <math>\ell</math> are given, the condition <math>f(a)\geq 0</math> is to be replaced by <math>f(a)\geq\ell(a)</math>. In particular, <math>f(a)</math> may be negative if <math>\ell(a)</math> is so.


A '''flow-augmenting path''' from some node <math>s\in V</math> to some node <math>t\in V</math> is an [[Basic graph definitions#Paths|ordinary path]] in <math>G_f</math>. Equivalently, a flow-augmenting path is a [[Basic graph definitions#Paths|generalized path]] such that:
'''Flow conservation condition:'''
# <math>f(a)<u(a)</math> if <math>a\in A</math> is a forward arc;
Let <math>W\subseteq V</math>.
# <math>f(a)>0</math> if <math>a\in A</math> is a backward arc.
# An arc weighting fulfills the flow conservation condition with respect to <math>W</math> if for all nodes <math>v\in V\setminus W</math>: <math>\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>.
# If there are balance values <math>b(v)</math> for all nodes <math>v\in V\setminus W</math>, the right-hand side of this condition is not zero but <math>b(v)</math>.


Augmenting
'''Feasibility:'''
# Let <math>p</math> denote the current path of the traversal (which is an <math>(s,t)</math>-path in this case).
# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
# Let <math>x</math> denote the minimum of the values <math>c(a)-f(a)</math> on all forward arcs of <math>p</math>.
# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
# Let <math>y</math> denote the minimum of the values <math>f(a)</math> on all backward arcs of <math>p</math>.
# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{s,t\}</math>.
# For each arc <math>a \in A</math> on <math>p</math>, increase the flow value by <math>\min \{x,y \}</math> if <math>a</math> is a forward arc on <math>p</math>, otherwise, decrease the flow value by <math>\min \{x,y \}</math>.


== Preflow ==


By definition of <math>x</math> and <math>y</math>, the capacity constraints are preserved. To see that the flow conservation conditions are preserved as well, only the internal nodes of <math>p</math> are relevant. Let <math>v</math> be such an internal node, and let <math>u</math> and <math>w</math> denote the immediate predecessor and successor of <math>v</math> on <math>p</math>, respectively. Basically, there are four cases:
# Preflows generalize feasible flows as follows: Instead of an equation, the following inequality is to be fulfilled for each <math>v\in V\setminus W</math>: <math>\sum_{w:(w,v)\in A}f(w,v)-\sum_{w:(v,w)\in A}f(v,w)\geq 0</math> (resp., <math>\geq b(v)</math>, if node balances are given).
*Either <math>(u,v)</math> is on <math>p</math> as a forward arc or <math>(v,u)</math> is on <math>p</math>  as a backward arc.
# The '''excess''' of <math>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.
*Either <math>(v,w)</math> is on <math>p</math> as a forward arc or <math>(w,v)</math> is on <math>p</math> as a backward arc.
It is easy to check preservation of the flow conservation conditions for each of these four cases.


== Preflow ==
== Flow value ==


Preflows generalize ordinary flows as follows: Instead of an equation, the following inequality is to be fulfilled:
Let <math>S,T\subseteq V</math> such that <math>S\cap T=\emptyset</math>, and let <math>f</math> be a flow with respect to <math>S\cup T</math>. The '''flow value''' <math>v(f)</math> of <math>f</math> is defined by
: <math>\sum_{w:(v,w)\in A}f(v,w)\leq\sum_{w:(w,v)\in A}f(w,v)</math>.
:<math>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>.


The '''excess''' of <math>v\in V</math> is the difference between the right-hand side and the left-hand side of that inequality.
'''Remark:'''
A straightforward induction on <math>k\geq|V_S|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>S\subseteq V_S</math>, <math>T\subseteq V_T</math> and <math>|V_S|=k</math>, it is
:<math>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>v(f)</math>, it is
:<math>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>.


== Pseudoflow ==
== Residual network ==


The '''residual network''' <math>(G_f,u_f)</math> of <math>(G,u)</math> with respect to an arc weighting <math>f</math> is defined as follows: It is <math>G_f=(V,A_f)</math>, and for each arc <math>(v,w)\in A</math>, we have:
# <math>(v,w)\in A_f</math> with <math>u_f(v,w)=u(v,w)-f(v,w)</math> if <math>u(v,w)-f(v,w)>0</math>.
# <math>(w,v)\in A_f</math> with <math>u_f(w,v)=f(v,w)</math> if <math>f(v,w)>0</math>.
The value <math>u_f(a)</math> of an arc <math>a\in A_f</math>is called the '''residual capacity''' of <math>a\in A</math> with respect to <math>f</math>.


'''Remark:'''
Changes of <math>f</math> in <math>G</math> and changes of <math>u_f</math> in <math>G_f</math> are equivalent in an obvious way. Since <math>G</math> is anti-symmetric, this equivalence is one-to-one. So, the view on <math>G</math> and <math>f</math> is exchangeable with the view on <math>G_f</math> and <math>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>(G,f)</math> or on <math>(G_f,u_f)</math> or even on both representations simultaneously.


== Valid distance labeling ==
== Flow-augmenting paths and saturated arcs ==


'''Definition:'''
A '''flow-augmenting path''' (or '''augmenting path''' for short) from some node <math>s\in V</math> to some node <math>t\in V</math> is an [[Basic graph definitions#Paths|ordinary path]] in the residual network <math>G_f</math>. Equivalently, a flow-augmenting path is a [[Basic graph definitions#Paths|generalized path]] in <math>G</math> such that:
# Let <math>G=(V,A))</math> be a directed graph, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be defined such that <math>0\leq f(a)\leq u(a)</math>. An assignment of a value <math>d(v)</math> to each node <math>v\in V</math> is a '''valid distance labeling''' if the following two conditions ar fulfilled:
# <math>f(a)<u(a)</math> if <math>a\in A</math> is a forward arc;
## It is <math>d(t)=0</math>.
# <math>f(a)>0</math> if <math>a\in A</math> is a backward arc.
## For each arc <math>(v,w)\in A</math> in the residual network, it is <math>d(v)\leq d(w)+1</math>.
An arc <math>a\in A</math> is '''saturated'''
# If even <math>d(v)=d(w)+1</math>, <math>(v,w)</math> is called an '''admissible arc'''.
# in forward direction if <math>f(a)=u(a)</math>.
# in backward direction if <math>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.


== Blocking flow ==
== Augmenting along a path ==


'''Definition:'''
Let <math>p</math> denote some flow-augmenting path in <math>G</math>, and let <math>\varepsilon>0</math> such that
Let <math>G=(V,A)</math> be a directed graph, let <math>s,t\in V</math>, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math>. We say that <math>f</math> is a '''blocking flow''' if every flow augmenting <math>(s,t)</math>-path contains at least one backward arc.
# <math>f(a)+\varepsilon\leq u(a)</math> if <math>a\in A</math> is a forward arc;
# <math>f(a)-\varepsilon\geq 0</math> if <math>a\in A</math> is a backward arc.
In the residual network <math>(G_f,u_f)</math>, '''augmenting''' <math>f</math> by <math>\varepsilon</math> along the [[Basic graph definitions#Paths|ordinary path]] induced by <math>p</math> means reducing all residual capacities by <math>\varepsilon</math>. Equivalently, for each arc <math>a \in A</math> on <math>p</math> in <math>G</math>, this means: 
# Increase the flow value by <math>\varepsilon</math> if <math>a</math> is a forward arc on <math>p</math>.
# Decrease the flow value by <math>\varepsilon</math> if <math>a</math> is a backward arc on <math>p</math>.
Obviously, the capacity constraints are preserved. The flow conservation conditions are preserved at every [[Basic graph definitions#Paths|internal node]] of <math>p</math>. To see that, let <math>v</math> be such an internal node, and let <math>u</math> and <math>w</math> denote the immediate predecessor and successor of <math>v</math> on <math>p</math>, respectively. Basically, there are four cases:
*Either <math>(u,v)</math> is on <math>p</math> as a forward arc or <math>(v,u)</math> is on <math>p</math>  as a backward arc.
*Either <math>(v,w)</math> is on <math>p</math> as a forward arc or <math>(w,v)</math> is on <math>p</math> as a backward arc.
It is easy to check preservation of the flow conservation conditions at <math>v</math> for each of these four cases.


'''Remarks:'''
'''Augmenting up to saturation:'''
# The name refers to an alternative, equivalent definition: Every ordinary <math>(s,t)</math>-path contains at least one saturated arc, which "blocks" the augmentation.
Again, let <math>p</math> denote some flow-augmenting path.
# Obviously, maximum flows are blocking flows, but not vice versa.
# Let <math>\varepsilon_1>0</math> denote the minimum of the values <math>u(a)-f(a)</math> on all forward arcs of <math>p</math>.
# Let <math>\varepsilon_2>0</math> denote the minimum of the values <math>f(a)</math> on all backward arcs of <math>p</math>.
# Let <math>\varepsilon</math> denote the minimum of <math>\varepsilon</math> and <math>\varepsilon_2</math>.
Augmenting the flow <math>f</math> along <math>p</math> by <math>\varepsilon</math> yields at least one saturated arc.


== Cuts and saturated cuts ==
== Cuts and saturated cuts ==
Line 65: Line 105:
## <math>f(v,w)=u(v,w)</math> for every arc <math>(v,w)\in A</math> such that <math>v\in S</math> and <math>w\in T</math>.
## <math>f(v,w)=u(v,w)</math> for every arc <math>(v,w)\in A</math> such that <math>v\in S</math> and <math>w\in T</math>.
## <math>f(v,w)=0</math> for every arc <math>(v,w)\in A</math> such that <math>v\in T</math> and <math>w\in S</math>.
## <math>f(v,w)=0</math> for every arc <math>(v,w)\in A</math> such that <math>v\in T</math> and <math>w\in S</math>.
== Valid distance labeling ==
'''Definition:'''
# Let <math>G=(V,A)</math> be a directed graph, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be defined such that <math>0\leq f(a)\leq u(a)</math>. An assignment of a value <math>d(v)</math> to each node <math>v\in V</math> is a '''valid distance labeling''' if the following two conditions ar fulfilled:
## It is <math>d(t)=0</math>.
## For each arc <math>(v,w)\in A</math> in the residual network, it is <math>d(v)\leq d(w)+1</math>.
# If even <math>d(v)=d(w)+1</math>, <math>(v,w)</math> is called an '''admissible arc'''.

Latest revision as of 13:42, 17 November 2015

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.