Flow network

A flow network is a graph $G=(V,E,c,s,t)$ where:

• $V$ is a set of $n$ nodes
• $E$ is a set of $m$ edges (links)
• For each $(u,v)\in E$, $c(u,v)\ge 0$ is the capacity of edge $(u,v)$ If $(u,v)\notin E$, then for convenience we define $c(u,v)=0$
• There are two distinguished nodes: source $s$ and sink $t$ where $s\ne t$

Link to original

Example

Goal of a maximum flow problem

We want to find (design) a maximum flow from the source to the sink:

• flow of the maximum total amount, while flow on each edge is not greater than capacity of the edge
• continuous flow of the maximum total rate, while rate of flow on each edge is not greater than the capacity of this edge

Slide 4-5: problem of representatives and reduction to maximum-flow

Other flow problems

• Flow-feasibility problem: find a feasible flow that satisfies edge capacities and specified supply / demand values at the nodes. This problem is ‘equivalent’ to maximum flow problem.
• Minimum-cost flow & multi-commodity flow problems

Flows

We assume that if $(u,v)\in E$, then $(v,u)\notin E$.

If there are ‘antiparallel’ edges, we can convert the network into an equivalent with no antiparallel edges by adding an additional vertex:

Flow

A flow is a function $f:E\to R$ where $f(u,v)\ge 0$ is the flow on edge $(u,v)$ with properties:

• Capacity constraints: for each edge $(u,v)\in E$, $0\le f(u,v)\le c(u,v)$
• Flow conservation: for each node $v\in V-\{s,t\}$:
  • The total flow into $v$ is equal to total flow out of $v$ $\begin{array}{rl}\text{flow in}& =\text{flow out}\\ a+b+c& =d+e\\ \sum _{(x,v)\in E}f(x,v)& =\sum _{(v,z)\in E}f(v,z)\end{array}$
  • i.e. net flow into $v$ is equal to $0$ $\begin{array}{rl}\text{net flow into }v& =0\\ a+b+c-d-e& =0\\ \sum _{(x,v)\in E}f(x,v)-\sum _{(v,z)\in E}f(v,z)& =0\end{array}$

Link to original

Maximum-flow problem

The value of a flow $f$ is the net flow from the source, (which is equal to the net flow into the sink due to flow conservation).

Value of a flow / flow conservation condition

$\begin{array}{rl}\Vert f\Vert & \stackrel{\text{def}}{=}\sum _{(s,v)\in E}f(s,v)-\sum _{(u,s)\in E}f(u,s)\\ & =\sum _{(x,t)\in E}f(x,t)-\sum _{(t,z)\in E}f(t,z)\end{array}$

Maximum flow problem

The maximum flow problem is where for a given flow network, we find the flow of the maximum possible value (maximises net flow from source).

Link to original

Saturated edge

For a given flow $f$, if $f(u,v)=c(v,u)$ then we say that $f$ saturates edge $(v,u)$ and edge $(v,u)$ is a saturated edge.

Link to original

Flows to paths

A flow $f$ can be ‘decomposed’ into at most $m$ paths from $s$ to $t$ and cycles, where $m$ is the number of edges in $G$.

Example: decompose following flow into paths

The algorithm works by selecting and removing (from current flow) ‘maximal’ $s-t$ path flows. Each path removes all remaining flow from at least one edge, so at most $m$ paths.

The algorithm can be extended to the case where there are flow cycles.

One flow path (or cycle) can be found in $O(n)$ time, and there are at most $m$ paths / cycles selected, so total running time is $O(nm)$. (less than the time needed to find maximum flow)

Flow-feasibility problem

In the Flow-Feasibility problem, we are given an input $G=(V,E,c,d)$ where $V$ and $E$ are sets of nodes and edges; for each $(v,u)\in E,c(v,u\ge 0)$ is the capacity of edge $(v,u)$; for each $v\in V$, $d(v)$ indicates the supply / demand at node $v$.

• $d(v)>0$: supply of $d(v)$ units at $v$
• $d(v)<0$: demand of $|d(v)|$ units at $v$
• $d(v)=0$: ‘transitional’ node; flow only passes through

We assume ${\sum }_{v\in V}d(v)=0$, total supply equals demand.

And hence we want to find a feasible flow $f$ that is a flow within edge capacities and such that for each node $v\in V$, the net flow from $v$ equals $d(v)$ (flow convervation property). ${\sum }_{(v,x)\in E}f(v,x)-{\sum }_{(z,v)\in E}f(z,v)=d(v)$

Reduction from flow-feasibility to maximum-flow problem

For a given input $G=(V,E,c,d)$ of the flow-feasibility problem, we construct the input $G^{\prime }=(V^{\prime },E^{\prime },C^{\prime },s,t)$ where:

• $V^{\prime }=V\cup \{s,t\}$ where $s$ and $t$ are new nodes
• E' = E \cup \{ (s,v): v \in V, d(v) > 0 \} \cup \{ (u,t): u \in V, d(u) < 0 \}$$ Create edges from s$tosupplynodesandfromdemandnodesto$t$.
• $c^{\prime }(v,u)=c(v,u);c^{\prime }(s,v)=d(v);c^{\prime }(u,t)=-d(u)$ Set the capacity of the edges equal to the supply / demand of the respective nodes.

Hence compute a maximum flow $f^{\prime }$ in $G^{\prime }$:

• A maximum flow in $G^{\prime }$ saturates all edges outgoing from $s$ iff there is a feasible flow in $G$.
• If a maximum flow $f^{\prime }$ in $G^{\prime }$ saturates all edges outgoing from $s$, then we can remove added nodes / edges to get a feasible flow in $G$.
• If $f$ is a feasible flow in $G$, then saturate all edges outgoing from $s$ / incoming to $t$ to get a maximum flow in $G^{\prime }$.

Residual capacity & networks

Residual capacity of an edge

Let $f$ be a flow in a flow network $G=(V,E,c,s,t)$. The residual capacity of an edge $(u,v)\in E$ is defined as $c_f(u,v)=c(u,v)-f(u,v)$

Link to original

Residual capacity of a reverse edge

If for an edge $(u,v)\in E$, $f(u,v)>0$, then the residual capacity of a reverse edge $(v,u)$ is defined as $c_f(v,u)=f(u,v)$

The positive residual capacity of reverse edge $(v,u)$ represents possibility of decreasing the current positive flow $f(u,v)$.

Link to original

Residual edge

If $c_f(u,v)>0$, then $(u,v)$ is a residual edge. Let $E_f$ denote the set of all residual edges, $m=|E|\le |E_f|\le 2|E|=2m$.

Link to original

Residual network

The residual network of $G$ induced by flow $f$ is the flow network $G_f=(V,E_f,c_f,s,t)$ where $c_f$ are the residual capacities and $E_f$ is the set of residual edges.

Link to original

A residual path is a simple path in the residual network $G_f$. The augmenting path is a residual path from $s$ to $t$.

The residual capacity of an augmenting path $p$ is the maximum amount of flow that can be sent along path $p$: $c_f(p)=\min \{c_f(u,v)|(u,v)\text{ is an edge on }p\}$

Let $p$ be an augmenting path in $G_f$. The (path) flow $f_p$ in $G_f$ is: $f_p(u,v)=\{\begin{array}{ll}{c}_f(p)& \text{if }(u,v)\text{ is on }p\\ 0& \text{otherwise}\end{array}$ The value of flow $f_p$ is $|f_p|=c_f(p)>0$.

Example: increase flow using residual network

Input network $G$ and flow $f$ of value $7$	Residual network $G_f$	Flow $f^{\prime }$ of value $1$ in residual network $G_f$	Input network $G$ and flow $h=f\uparrow f^{\prime }$ of values $7+1=8$.

Augmenting current flow by flow in residual network

If $f$ is a flow in $G$ and $f^{\prime }$ is a flow in the residual network $G_f$, then we can augment $f$ by $f^{\prime }$ to get a new greater flow $h$ in $G$. The new flow $h=f\uparrow f^{\prime }$ in $G$ is defined in the following way: $h(u,v)=\{\begin{array}{ll}f(u,v)+f^{\prime }(u,v)-f^{\prime }(v,u)& \text{if }(u,v)\in E\\ 0& \text{otherwise}\end{array}$ This definition of $f\uparrow f^{\prime }$ works also if both $f^{\prime }(u,v)$ and $f^{\prime }(v,u)$ are positive. $|f\uparrow f^{\prime }|=|f|+|f^{\prime }|$: the value of flow $f\uparrow f^{\prime }$ (net flow from source) is equal to sum of values of flows $f$ and $f^{\prime }$.

General approach to finding maximum flow

Start with zero flow and keep iteratively increasing flow by flows in residual network:

1. Construct residual network $G_f$
2. Find a non-zero flow $f^{\prime }$ in $G_f$ If there is none, exit
3. $f\leftarrow f\uparrow f^{\prime }$ (augmentation)

Most max-flow algorithms follow this general approach.

Ford-Fulkerson method

Fold-Fulkerson method

def ford_fulkerson(G): # G = (V, E, c, s, t)
	f = zero flow # f(u, v) = 0 for each (u, v) in E
	
	while True:
		G_f = # (1) construct residual network
		P = # (2) find an augmenting path in G_f (DFS)
		if P is None:
			return f
		
		f = f ^ f_p # (3) path augmentation

Running time of Fold-Fulkerson method

Given $n$ is the number of nodes, and $m$ is the number of edges.

The running time of one iteration is $O(m)$:

• construct $G_f$: $\Theta (m)$ or $O(n)$ if incremental
• search $G_f$ to find augmenting path: $O(m)$
• update the flow: $O(n)$

Number of iterations depends on selection strategy in step (2).

Number of iterations in Ford-Fulkerson

The number of iterations in Ford-Fulkerson method depends on strategy of selecting an augmenting path $p$ in each iteration. If the algorithm is run on a network such that all edge capacities are integral:

• Residual capacities are integral throughout the computation, so the value of the current flow in $G$ increases in each iteration by some integer, at least $1$.
• If $f^{\ast }$ denotes a maximum flow, then the number of iterations is at most $|f^{\ast }|$.
• Hence total running time is $O(|f^{\ast }|m)$ (does not depend on selection strategy).

No general bound on number of iterations which would depend only on size of network ($n$ and $m$).

Cuts

A cut $(S,T)$ in a network $G$: $S\subseteq V,T=V-S,s\in S,t\in T$. That is, a cut is a partitioning of the set of nodes $V$ into two disjoint sets $S$ and $T$ such that the source node $s$ is in the set $S$ and the sink node $t$ is in the set $T$.

The capacity of a cut $(S,T)$ is the sum of the capacities of the edges from $S$ to $T$: $c(S,T)={\sum }_{(u,v)\in E:u\in S,v\in T}c(u,v)$

If $f$ is a flow, then the net flow across the cut $(S,T)$ is: $f(S,T)={\sum }_{(u,v)\in E:u\in S,v\in T}f(u,v)-{\sum }_{(u,v)\in E:u\in S,y\in S}f(x,y)$ For each cut $(S,T)$, $f(S,T)=|f|$, that is, the net flow across the cut is equal to the net flow into the sink $t$.

Example of a cut

For this cut $(S,T)$ and flow $f$:

• $c(S,T)=4+7+7+1+6=25$
• $f(S,T)=7+3+1-2=9=|f|$

Theorem 1. Max-flow Min-cut theorem

For any flow $f$ and any cut $(S,T)$: $|f|=f(S,T)\le c(S,T)$ (the net flow across a cut cannot be greater than the capacity of this cut).

Therefore, the value of a maximum flow is not greater than the minimum capacity of a cut. $\max \{|f|:f\text{ is a flow in }G\}\le \min \{c(S,T):(S,T)\text{ is a cut in }G\}$

This cut $(S,T)$ is a minimum capacity cut, $c(S,T)=5+2+2+1=10$, so the maximum value of flow for t his network is not greater than $10$.

Theorem 2.

For a flow $f$ in $G$, the following three conditions are equivalent. a. $f$ is a maximum flow in $G$ b. there is no augmenting path in the residual network $G_f$ c. for some cut $(S,T)$ in $G$, $|f|=c(S,T)$

We can prove this by showing implications $(a)\Rightarrow (b)\Rightarrow (c)\Rightarrow (a)$

• $(a)\Rightarrow (b)$: assume $f$ is a maximum flow in $G$ If there is an augmenting path, then the flow cannot be maximum because we can use such a path to increase the value of the flow.

• $(b)\Rightarrow (c)$: assume no augmenting path in $G_f$ Let $S$ be the set of nodes reachable from $s$ in the residual network $G_f$ $t$ is not in $S$

  All edges from $S$ to $T=V-S$ are saturated. All edges from $T$ to $S$ have zero flow.

  Therefore, $|f|=f(S,T)=c(S,T)$.

• $(c)\Rightarrow (a)$: let $(S,T)$ be a cut as in $(c)$ $|f|=f(S,T)=c(S,T)$ but there is no flow of value greater than $c(S,T)$ so $f$ is a maximum flow

Theorem 1 follows from Theorem 2

$(a)\Rightarrow (c)$, so for a maximum flow $f$, there is a cut $(S,T)$ such that $|f|=f(S,T)=c(S,T)\ge \min \{c(S^{\prime },T^{\prime }):(S^{\prime },T^{\prime })\text{ is a cut in }G\}$