Network Flow

Definition:

Max-flow problem:

Definition

• Only an amount of $c(u,v)$ crates per day can go from city $u$ to city $v$
• What is the maximum crates can be transported per day?
  • the number of each directed edge denotes the capacity
  • 
• Formally defined:
  • a tuple $(G,c,s,t)$ with two nodes called source and sink
  • a flow that map $f:V\times V\to R_{+}:(u,v)\to f(u,v)$ satisfying the two constraints:
    • capacity: $f(u,v)\le c(u,v),\forall (u,v)$
    • flow conservation: $f^{in}(u)=f^{out}(u)$ for all nodes except start and sink

Minimum-cut problem:

• This can be solved with defining minimum-cut problem:
• Say all nodes are splitted to 2 groups with group A includes start node and group B includes sink
• Therefore, need to find cut such that flow from 1 group to the other is minimum, which means it is the max flow that satisfy the capacity
• Net flow across cut is sum of flow from A to B and B to A
• formally:
  1. An st-cut is a partition (A, B) of the nodes with $s\in A$ and $t\in B$
  2. Its capacity is the sum of the capacities of the edges from A to B
• Using greedy will fail because once it increase a flow on an edge, it will never decrease
• This can be expensive to compute

Residual Network:

• For an edge with flow/capacity $f(e)/c(e)$:
  • define the flow as an independent edge with weight $c(e)-f(e)$
  • define a new residual edge $e^{\text{reverse}}$ with reverse direction and with weight $f(e)$
• A flow on a reverse edge negates flow on corresponding forward edge
• Formally: $G_f(V,E_f,s,t,c_f)$
  • with $E_f=\{e:f(e)<c(e)\}\cup \{e:f(e^{inverse})>0\}$, new set of edges
  • key property: $f^{\prime }$ is a flow in $G$ iff $f+f^{\prime }$ is a flow in $G$
  • an augmenting path is a simple $s⇝t$ path in the residual network $G_f$
  • The bottleneck capacity of an augmenting path $P$ is the minimum residual capacity of any edge in $P$
    • think of it like the amount of flow that cant be passed due to other nodes, minimize that is to maximize the flow
  • Key property: Let $f$ be a flow and let $P$ be an augmenting path in $G_f$. Then, after calling $f^{\prime }=AUGMENT(f,c,P)$, the resulting $f^{\prime }$ is a flow and $val(f^{\prime })=val(f)+bottleneck(G_f,P)$
• AUGMENT(f,c,P):
  • $\delta$ = bottleneck capacity of augmenting path $P$
  • FOREACH edge $e\in P$:
    • IF $e\in E$: $f(e)=f(e)+\delta$
    • Else; $f(e^{inverse})=f(e^{inverse})-\delta$
  • return f

Ford-fulkerson Algorithm:

• Start with $f(e)=0$ for each edge $e\in E$
• Find an $s⇝t$ path $P$ in the residual network $G_f$
• Augment flow along path $P$
• Repeat until get stuck
• Input: Network G
• Pseudocode:
  • Foreach edge $e\in E:f(e)=0$
  • $G_f=$ residuel network of $G$ with respect to flow $f$
  • WHILE: there exists an $s⇝t$ path $P$ in $G_f$
    • $f=$ Augment(f,c,P)
    • update $G_f$
  • Return f

Flow and cut relationship

• Let f be any flow and let $(A,B)$ be any cut.
  • Lemma: then, the value of the flow f equals the net flow across the cut $(A,B)$. $val(f)={\sum }_{\text{e out of A}}f(e)-{\sum }_{\text{e in to A}}f(e)$
  • Weak duality: $val(f)\le cap(A,B)$
  • Corollary: if $val(f)=cap(A,B)$ then f is the max flow and $(A,B)$ is a min cut
• Theorem: Value of a max flow = capacity of a min cut