Max Flow

1. Foundations

• What we do in Max flow: Given a flow network G with source s s s and sink t t t, to find a flow of maximum value

• What is a valid flow: must satisfy both: 1. flow constraint; 2. flow conservation

2. Define a max-flow problem

• G = ( V , E ) ; ( u , v ) ∈ E ; c ( u , v ) ≥ 0 G=(V,E);(u,v)\in E;c(u,v)\ge0 G=(V,E);(u,v)∈E;c(u,v)≥0
• Capacity constraint: 0 ≤ f ( u , v ) ≤ c ( u , v ) 0\le f(u,v) \le c(u,v) 0≤f(u,v)≤c(u,v)
• Flow conservation: for all v ∈ V v\in V v∈V{(s,t)}: ∑ v ∈ V f ( v , u ) = ∑ v ∈ V f ( u , v ) \sum_{v\in V}f(v,u)=\sum_{v\in V}f(u,v) ∑v∈V​f(v,u)=∑v∈V​f(u,v) the amount of flow going into u u u must be equal to flow going out of u u u
• The value of a flow(graph): ∣ f ∣ = ∑ v ∈ V f ( s , v ) − ∑ v ∈ V f ( v , s ) |f|=\sum_{v\in V}f(s,v)-\sum_{v\in V}f(v,s) ∣f∣=∑v∈V​f(s,v)−∑v∈V​f(v,s) the value of a graph equals to the absolute value of source s s s
• How to handle networks with multiple sources ad sinks: supersource and supersink
• Modeling problems with antiparallel: add a new vertex
• Skew Symmetry: F < x , y > = − F < y , x > F<x,y>=-F<y,x> F<x,y>=−F<y,x>

Residual network

• Residual network: the residual network G f G_f Gf​ consists of edges with capacities that represent how we can change the flow on edges of G G G

• Residual capacity: c f ( u , v ) = c ( u , v ) − f ( u , v ) = f ( v , u ) c_f(u,v)=c(u,v)-f(u,v)=f(v,u) cf​(u,v)=c(u,v)−f(u,v)=f(v,u), if ( u , v ) , ( v , u ) ∈ E {(u,v),(v,u)\in E} (u,v),(v,u)∈E

• Cancellation: push flow on the reverse edge in the residual networks

• Augmenting path:

• Notation :

  • f ′ f' f′: a flow in the corresponding residual network G f G_f Gf​
  • f ↑ f ′ f\uparrow f' f↑f′: the augmentation of flow f f f by f ′ f' f′

  ​

3. Min cut

• Separate source(s) and sink(t) in to A and B part

• The minimum flow from A to B equals to the maximum flow of the graph

  Net flow across cut

  • Given a cut (S,T), we define the net flow across ( S , T ) ′ (S,T)' (S,T)′ as: f ( S , T ) = ∑ u ∈ S ∑ v ∈ T ( f ( u , v ) − f ( v , u ) ) f(S,T)=\sum_{u\in S}\sum_{v\in T}(f(u,v)-f(v,u)) f(S,T)=∑u∈S​∑v∈T​(f(u,v)−f(v,u))

  • Capacity: c ( S , T ) = f ( S , T ) = ∑ u ∈ S ∑ v ∈ T c ( u , v ) c(S,T)= f(S,T)=\sum_{u\in S}\sum_{v\in T} c(u,v) c(S,T)=f(S,T)=∑u∈S​∑v∈T​c(u,v), and ∣ f ∣ ≤ c ( S , T ) |f|\le c(S,T) ∣f∣≤c(S,T)

4.Ford-Fulkerson method

• Augmenting path:

  • in the residual graph with unused capacity, greater than zero, from s s s to t t t.

• Ford-Fulkerson algorithm

  • Start with 0 flow
  • Use “bottleneck” to augmenting the flow and original edges
  • update G f G_f Gf​, until there is no augmenting path from s s s to t t t in G f G_f Gf​

• Disadvantages: the longer path, the more likely to stuck in small bottleneck values

  

• Time complexity (worst case): O ( E ∣ f ∗ ∣ ) O(E|f^*|) O(E∣f∗∣), where f ∗ f^* f∗ is a maximum flow. Time to find an augmenting path: O ( E ) O(E) O(E), and the loop can run at most f ∗ f^* f∗ times.

5. Edmonds-Karp algorithm O ( ∣ E ∣ ∣ V ∣ 2 ) O(|E||V|^2) O(∣E∣∣V∣2)

• Turn DFS(depth first search) into BFS(breadth first search), each time we always pick the shortest path

• Time complexity: O ( ∣ E ∣ ∣ V ∣ 2 ) O(|E||V|^2) O(∣E∣∣V∣2) = time taken for 1 iteration * no. of iterations(no. of augmenting paths);

  • Time taken for 1 iteration ∣ E ∣ |E| ∣E∣: the length of an augmenting path must be increasing(first time we find the shortest path), and the upper bound would be the number of edges ∣ E ∣ |E| ∣E∣

  • The number of iterations: V ∗ E V*E V∗E.

    • In the residual network, the distance of any vertex from the source never decreases during the algorithm

• Critical edges: an edge on the augmenting path whose residual capacity equals the residual capacity of the path.

Proof of time complexity

Time per iteration

• In the graph there are ∣ V ∣ |V| ∣V∣ vertices and ∣ E ∣ |E| ∣E∣ edges; then to find a path in BFS: O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣), worst case;

• Assume that every vertex has at least one incident edge, so that: ∣ V ∣ ≤ 2 ∣ E ∣ |V|\le 2|E| ∣V∣≤2∣E∣;

• Then the time to find a path: O ( ∣ E ∣ ) O(|E|) O(∣E∣);

The number of loops

• In the worst case, in the k t h k_{th} kth​ iteration, there path s → t s\to t s→t consists of all vertices v v v such that the path has i i i edges;

• If we look at the residual network, the distance of any vertex from the source never decreases during the algorithm;

• Now, let’s say we’ve found some augmenting path. We push as much flow through it as we can. So obviously there’s at least one edge on this path which gets fully filled. We’ll call such edge critical;

• An edge can become critical at most O ( ∣ V ∣ / 2 − 1 ) = O ( ∣ V ∣ ) O(|V|/2 -1)=O(|V|) O(∣V∣/2−1)=O(∣V∣) times, and there are ∣ E ∣ |E| ∣E∣ edges in total, so there are O ( ∣ V ∣ ∣ E ∣ ) O(|V||E|) O(∣V∣∣E∣) loops;

  • Proof:

    

• Detail answer

6. Proofs

Lemma 26.1: ∣ f ↑ f ′ ∣ = ∣ f ∣ + ∣ f ′ ∣ |f\uparrow f'|=|f|+|f'| ∣f↑f′∣=∣f∣+∣f′∣

• Augmentation of flow f f f by f ′ f' f′: f ↑ f ′ f\uparrow f' f↑f′

( f ↑ f ′ ) = { f ( u , v ) + f ′ ( u , v ) − f ′ ( v , u ) i f    ( u , v ) ∈ E ; 0 o t h e r w i s e . (f\uparrow f')=\left\{ \begin{aligned} &f(u,v)+f'(u,v)-f'(v,u)\quad &if\;(u,v)\in E;\\ &0\quad &otherwise. \end{aligned} \right. (f↑f′)={​f(u,v)+f′(u,v)−f′(v,u)0​if(u,v)∈E;otherwise.​

• proof of lemma 26.1: Let u ∈ V {̸ s , t } u\in V\not\{s,t\} u∈V​{s,t} be given. Then:

KaTeX parse error: No such environment: align at position 7: \begin{̲a̲l̲i̲g̲n̲}̲&\sum_{(u,v)\in…

• 1st line: definition of augmentation
• 2nd line: flow conservation of f f f and re-ordering terms
• 3rd line: flow conservation of f ′ f' f′

Lemma 2 : Given flow f f f in G G G and given any cut ( S , T ) , f ( S , T ) = ∣ f ∣ (S,T), f(S,T)=|f| (S,T),f(S,T)=∣f∣ , where ∣ f ∣ |f| ∣f∣ is the value of the flow, equal to the net flow going out of the source.

KaTeX parse error: No such environment: align at position 7: \begin{̲a̲l̲i̲g̲n̲}̲ f(S,T)&=\sum_{…

• 2nd line: flows inside S are substracted somewhere else in S(they don’t go out of S);

• 3rd line: all going out of u u u is zero, except s s s; all going out of source minus all going into the source: the value of a flow.

• Always remember: ∣ f ∣ = f i n t o    s o u r c e − f o u t    s o u r c e |f|=f_{into\;source}-f_{out\;source} ∣f∣=fintosource​−foutsource​

Corollary: Min cut: for any flow f f f, and any cut ( S , T ) (S,T) (S,T), ∣ f ∣ ≤ c ( S , T ) |f|\le c(S,T) ∣f∣≤c(S,T)

Three equal statements:

• f f f is a maximum flow in G

• The residual network G f G_f Gf​ contains no more augmenting paths

• ∣ f ∣ = c ( S , T ) |f|=c(S,T) ∣f∣=c(S,T) for some cut (S,T) of G.