Maximum Flow

• Chapter 26 of Introduction to Algorithms (3rd Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Maximum Flow

• We can use a directed graph to model a flow network
  • A material is produced. It goes from a source to a sink
  • The source produces the material to a fix rate
  • At the sink, the material is consumed at the same rate
  • The flow of the material at any point of the system is the rate at which that material moves

Maximum Flow

• When can we use flow networks
  • Flow networks can be used to model
    • Liquids moving through tubes
    • Parts of ensemble lines
    • Electricity through power lines
    • Information through communication networks, etc.

Maximum Flow

• Directed edges in the flow network lead the material
• Each duct has a capacity
  • The maximum rate to which the material flows
    • i.e. 200 galons of liquid per hour in a tube
    • i.e. 20 amps of electric current in a cable

Maximum Flow

• Vertices are the joints in the duct, different from the source and sink
  • Vertices do not collect material

Maximum Flow

• The material input rate is equal to the material output rate
  • Flow conservation property
  • Equivalent to the Kirchhoff current law, when the material is electric current

Maximum Flow

• Compute the highest rate to which the material can be moved
  • From a source to a sink
  • Without breaking any capacity restriction
• One of the simplest problems related to flow networks
• Can be solved with efficient algorithms

Modeling the Problem

• Graph-based definition for flow networks
• Flow network
  • \(G = (V, E)\) is a directed graph in which each edge \((u, v) \in E\) has a non-negative capacity \(c(u, v) \geq 0\).
  • If \((u, v) \notin E\), we assume that \(c(u, v) = 0\).
  • We distinghish two types of vertices
    • a source s
    • a sink t
  • We assume that each vertex is in some path from the source to the sink
    • \(\forall v \in V\), there exists a path \(s \rightarrow v \rightarrow t\)
    • The graph is connected and \(|E| \geq |V| - 1\)

Flow Network

Flow

• Given \(G = (V, E)\) we can represent a flow network with capacity function \(c\)
• Let \(s\) be the source of the network and let \(t\) be the sink
• A flow in \(G\) is a function with real values \(f: V x V \rightarrow R\) that satisfies the following three properties
  • 1- Capacity restriction: \(\forall u, v \in V\), we require \(0 \leq f(u, v) \leq c(u, v)\)
  • 2- Bias simmetry: \(\forall u, v \in V\), we require \(f(u, v) = -f(v, u)\)

Flow

• The third property…

  • 3- Flow conservation: \(\forall u \in V - \{s, t\}\), we require:

    • \(\sum\limits_{v \in V} f(v, u) = \sum\limits_{v \in V} f(u, v)\)
  • The quantity \(f(u, v)\), which can be positive, cero, or negative, is called the flow from vertex \(u\) to vertex \(v\)

  • If \((u, v) \notin E\), there can’t be flow from \(u\) to \(v\), then \(f(u, v) = 0\).

Flow

• The value of a flow is defined as:
  • \(|f| = \sum\limits_{v \in V} f(s, v)\)
  • The total flow that comes from the source
  • \(| |\) denotes the value of flow, NOT absolute value, nor cardinality
• The Problem of Maximum Flow
  • We are given a flow network \(G\) with source \(s\) and sink \(t\) and we want to find a maximum flow value

Capacity Restriction

• The flow from a vertex to another should not exceed the given capacity

Bias Simmetry

• The notation says that:
  • The flow from a vertex \(u\) to a vertex \(v\) is the non negative of the flow in opposite direction

Flow Conservation

• The total flow comming from a vertex, different from the source or sink, is 0

Example of Flow

Networks with Multiple Sources and Sinks

• There can be several sources and sinks
  • \({s_1, s_2, \dots, s_m}\)
  • \({t_1, t_2, \dots, t_n}\)
• This problem is not more difficult than the previous one
  • Can be reduced to an ordinal maximum flow problem
  • Super-source
  • Super-sink

Networks with Multiple Sources and Sinks

Working with Flows

• Summation notation is implicit
  • \(\sum\limits_{x \in X}\sum\limits_{y \in Y} f(x, y)\)
• Conservation flow can be expressed as
  • \(f(u, V) = 0\) for all \(u \in V - \{s, t\}\)
• In \(f(s, V - s) = f(s, V)\), the term \(V - s\) refers to the set \(V - \{s\}\)

The Ford-Fulkerson Method

• Three important ideas, relevant for many flow algorithms and problems
  • Residual networks
  • Augmenting paths
  • Cuts
• Different implementations of the algorithm with different execution times

The Ford-Fulkerson Method

• Iterative method
  • Starts with \(f(u, v) = 0\) for all \(u, v \in V\), with an initial flow value of 0
  • At each iteration, we increment the flow value when we find an “augmenting path”: a path from the source \(s\) to the sink \(t\) that we can use to send flow
  • We repeat this process until we cannot find any augmenting path
• The theorem of maximum-flow minimum-cut shows that, at the end, the process takes a maximum flow

The Ford-Fulkerson Method

Residual Networks

• Intuitivelly
  • Given a flow network and a flow, the residual network consists of edges that can admit more flow

Residual Networks

• Formally
  • Given a flow network \(G = (V, E)\) with source \(s\) and sink \(t\)
  • Let \(f\) be a flow in \(G\), and considering a pair of vertices \(u, v \in V\)
  • The amount of additional flow that we can take from \(u\) to \(v\) without exceding capacity \(c(u, v)\) is the residual capacity of \((u, v)\) given by \(c_f(u, v) = c(u, v) - f(u, v)\)
• Given a flow network \(G = (V, E)\) and a flow \(f\), the residual network of \(G\) induced by \(f\) is \(G_f = (V, E_f)\), where
  • \(E_f = \{(u, v) \in V x V : c_f(u, v) > 0\}\)

Example of Residual Network

Augmenting Paths

• Given a flow network \(G = (V, E)\) and a flow \(f\)
  • An augmenting path \(p\) is a path from \(s\) to \(t\) in the residual network \(G_f\)
  • Figure 26.4b
  • We can increase the flow in 4 units, \(c_f(v_2, v_3) = 4\)
    • The residual capacity of the path is 4 without violating the capacity restriction, the lowest residual capacity is 4: \(c_f(p) = min\{c_f(u, v) : (u, v) \in p\}\)

Lemma 26.3: Augmenting Paths

• Given \(G = (V, E)\), a flow network
• Let \(f\) be a flow in \(G\)
• Given \(p\) an augmenting path in \(G_f\)
• Define a flow \(f_p\) in \(G_f\) as the function \(f_p : V x V \rightarrow R\) by:

\(f_p(u, v) = \begin{cases} c_f(p) &\mbox{if } (u, v) \in p\\ -c_f(p) &\mbox {if } (v, u) \in p\\ 0 &\mbox{any other way}\\ \end{cases}\)

• Then \(f_p\) is a flow in \(G_f\) with value \(|f_p| = c_f(p) > 0\)

Corolary 26.4

• Corolary 26.4 tells us that, if we add \(f_p\) to \(f\), we obtain another flow in \(G\) with a value closer to the maximum
  • Let \(G = (V, E)\) be a flow network
  • Let \(f\) be a flow in \(G\)
  • Let \(p\) be an augmenting path in \(G_f\)
  • Let \(f_p\) be defined as previous (previous page)
  • We define a function \(f': V x V \rightarrow R\) by \(f'=f + f_p\)
  • Then, \(f'\) is a flow in \(G\) with value \(|f'| = |f| + |f_p| > |f|\)

Cuts in Flow Networks

• The flow is maximum iff its residual network does not contain an augmenting path
• To show this we need the cut notion
• A cut \((S, T)\) of a flow network \(G = (V, E)\) is a partition of \(V\) in \(S\) and \(T = V - S\) such that \(s \in S\) and \(t \in T\)
• The Net Flow through the \(cut(S, T)\) is defined as \(f(S, T)\)
• The Capacity of \(cut(S, T)\) is \(c(S, T)\)
• A minimum cut of a network is a cut with minimum capacity over all cuts in the network

Example of Cut

• Net flow
  \(f(v_1,V_3) + f(v_2,v_4) - f(v_3,v_2) = 12 + 11 - 4\)
  \(= 19\)
• Capacity
  \(c(v_1,v_3) + c(v_2,v_4) = 12 + 14\)
  \(=26\)

Lemma 26.5

• The net flow through any cut is the same and equal to the value of the flow
• Given \(f\), the flow in a flow network \(G\) with source \(s\) and sink \(t\), and let \((S, T)\) be a cut of \(G\)
  • Then the net flow through \((S, T)\) is \(f(S, T) = |f|\)

Corolary 26.6

• The value of any flow \(f\) in a flow network \(G\) is bounded from above by the capacity of any cut of \(G\)

Theorem of the Maximum-Flow Minimum-Cut

• The value of a maximum flow is equal to the capacity of a minimum cut
• If \(f\) is a flow in a network flow \(G = (V, E)\) with source \(s\) and sink \(t\), then the following conditions are equivalent:
  • \(f\) is a maximum flow in \(G\)
  • The residual network \(G_f\) does not contain augmenting paths
  • \(|f| = c(S, T)\) for any cut \((S, T)\) of \(G\)

Basic Ford-Fulkerson Algorithm

Example

Example

Analysis of Ford-Fulkerson

• Depends on a method to find the augmenting path
• Use breadth First Search
  • Edmonds-Karp algorithm
  • The augmenting path is the shortest one from \(s\) to \(t\)
• Theorem 26.9
  • The total number of augmentings is \(O(VE)\), \(O(E)\) per augmenting. Then, the algorithm has an execution time of \(O(VE^2)\)
• Other methods to compute maximum flow
  • Generic-Push-Relabel takes \(O(V^2E)\)
  • Relabel-to-Front takes \(O(V^3)\)