Algorithm Design 10
Chapter 8 Network Flow
8.1 Basic Definitions
Description
Input : directed graph \(G=(V,E)\) , \(e=(u,v,c)\) . Two special vertices : source \(s\in V\) , sink \(t\in V\) .
Goal : Find a feasible/maximum flow
Def [ Flow ] : A function \(f:E\to \mathbb R^*\) satisfying following constraints:
- Capacity constraint : \(\forall e\in E\ ,\ 0\le f(e)\le c_e\)
- Flow conservation : \(\forall v\in V\backslash\{s,t\} , \sum\limits_{e=(x,v)}f(e)=\sum\limits_{e=(v,y)}f(e)\)
Def [ Value of Flow ] : \[ v(f):=\sum_{e=(s,x)}f(e)=\sum_{e=(y,t)}f(e) \] By flow conservation , this definition is complete .
Max-Flow Problem : Find a feasible flow with maximum value .
LP version of Max-Flow Problem: Constraints above are all linear . Goal is also linear .
Def [ \(s\)-\(t\) cut ] : A partition of \(V=V_1+V_2\) , s.t. \(s\in V_1,t\in V_2\) . \[ cut(V_1,V_2):=\{e=(u,v)\in E:u\in V_1,v\in V_2\} \] Capacity of the cut : \(c(V_1,V_2):=\sum\limits_{e\in cut(V_1,V_2)}c_e\)
Observation : \[ \forall f\in \mathtt{FLOW},\forall (V_1,V_2)\in \mathtt{CUT}, v(f)\le c(V_1,V_2) \]
THM [ max-flow min-cut theorem ] : \(\max\limits_{f\in \mathtt{FLOW}}v(f)=\min\limits_{(V_1,V_2)\in \mathtt{CUT}}c(V_1,V_2)\)
8.2 Max-Flow Algorithm
Intuition : Finding Augmenting Path
Each time we find a path from \(s\) to \(t\) such that all edges have rest capacity , then we augment on this path
Difficulty : How to choose path to augment ?
If we firstly choose \(s\to 1\to 2\to t\) , and augment \(20\) , then we cannot augment more flow .
However , we can pretend to choose \(s\to 2\to 1\to t\) path , and "augment" \(10\) to get still-valid , more optimal flow .
Def [ residue graph ] : residue graph \(G_f\) with flow \(f\) is defined as follows :
\(V(G_f)=V(G)\)
\[ E(G_f)=\left\{e_f=(u,v,c-f(e)):e=(u,v,c)\in E\right\}\cup\left\{e_b=(v,u,f(e)):e=(u,v,c)\in E\right\} \]
Ford-Fulkerson Algorithm [1956]
1
2
3
4
5
6
7
8
9
10
11
12// init
for(e in E){
f(e)=0;
}
while(there exists s-t path with all edge capacity positive in G_f){
P=simple s-t path;
c=min(c_e: e in P);
for(e in P){
c(e_f)-=c;
c(e_b)+=c;
}
}Analysis
Lemma : Upon termination of FF , we get a feasible flow
All updates during FF do not violate the constraints .
Lemma : Let \(f\) be an \(s\)-\(t\) flow , \((A,B)\) be an \(s\)-\(t\) cut , then \[ v(f)=f^{out}(A)-f^{in}(A) \] Proof : ( note that \(s\) only has output flow , i.e. \(f^{in}(s)=0\) ) \[ \begin{aligned} v(f)&=f^{out}(s)-f^{in}(s)\\ &=\sum_{v\in A}f^{out}(v)-f^{in}(v)\qquad \forall v\in A\backslash\{s\}, f^{out}(v)=f^{in}(v)\\ &=f^{out}(A)-f^{in}(A) \end{aligned} \] Remark : this is an extended lemma from observation that \(v(f)\le c(A,B)\) , since \(c(A,B)\ge f^{out}(A)\ge f^{out}(A)-f^{in}(A)=v(f)\) .
Proof correctness of FF ( also max-flow min-cut theorem )
Assume FF terminates with flow \(\bar f\) , then in the residue graph , \(s,t\) are disconnected considering only positive-capacity edges .
Let \(A^*=\{v\in V:v\text{ is reachable from }s\text{ in }G_{\bar f}\}\) , so \(t\notin A^*\) .
By the lemma : \(v(\bar f)=\bar f^{out}(A^*)-\bar f^{in}(A^*)\) .
Claim 1 : \(\bar f^{in}(A^*)=0\) . Otherwise , if \(e=(u,v)\) from \(V\backslash A^*\) to \(A^*\) has \(\bar f(e)>0\) , then corresponding \(e_b=(v,u,\bar f(e))\) , so \(u\) is also reachable from \(s\) in \(G_{\bar f}\) .
Claim 2 : \(\bar f^{out}(A^*)=c(A^*,V\backslash A^*)\) . Otherwise , if \(e=(u,v)\) from \(A^*\) to \(V\backslash A^*\) has \(\bar f(e)<c_e\) , then corresponding \(e_f=(u,v,c_e-\bar f(e))\) , so \(v\) is also reachable from \(s\) in \(G_f\) .
Therefore , \(v(\bar f)=c(A^*,V\backslash A^*)\) .
Remarks
If \(c_e\in \mathbb Z^+\) , FF will terminate with time \(\mathcal O(|E|\times \texttt{max flow})\) .
If \(\exists e,c_e\in \mathbb R\backslash \mathbb Q\) , FF will not terminate if path is not chosen carefully .
Regardless of termination of FF , max-flow min-cut theorem always holds .
Other algorithms
[ Edmond-Karp ] Always choose shortest path in \(G_f\) , terminate with time \(\mathcal O(|E|^2 |V|)\) .
Scaling Algorithm : Like FPTAS+discretize , with time \(\mathcal O(|E|^2 \log C)\)
\(\mathcal O(\log C)\) : weak poly-time (still poly-time , different from pseudo-poly time)
push-relabel : \(\mathcal O(|V|^3)\)
Min-cost flow
each edge has a cost \(w_e\) . Given \(v_0\) , find a flow s.t. \(v(f)=v_0\) , and minimize \(\sum\limits_{e\in E}f(e)w_e\) .
8.3 Application of Flow
8.3.1 Bipartite Matching
Description
Input : undirected graph \(G=(L+R,E)\) , \(E\subseteq\{(u,v):u\in L,v\in R\}\)
Output : Matching \(M\) with maximum edges .
Construction
Vertices : \(L,R,s,t\)
Edges :
- \(\forall u\in L\) , \((s,u,1)\)
- \(\forall v\in R\) , \((v,t,1)\)
- \(\forall e=(u,v)\in E\) , \((u,v,1)\)
Hungary Algorithm / Alternating Path Algorithm
Alternating Path : equivalent as a path in residue graph \(G_f\) .
8.3.2 Perfect Matching
Description
undirected graph \(G=(L+R,E)\) , \(|L|=|R|=n\) .
A perfect matching is a matching with \(n\) edges
THM [ Hall's Theorem ] : \(G(L+R,E)\) has a perfect matching \(\iff\) \(\forall A\subseteq L,|N(A)|\ge |A|\) .
Here \(N(A):=\{v:\exists (u,v)\in E,u\in A\}\)
Extension : \(G=(L+R,E)\) has a matching with \(|L|\) edges \(\iff \forall A\subseteq L,|N(A)|\ge |A|\) .
Proof : use max-flow min-cut theorem
8.3.3 Disjoint paths in directed/undirected graph
Description
Input : directed/undirected graph \(G=(V,E)\) , \(s,t\in V\)
Output : maximum \(s\)-\(t\) vertex/edge disjoint path
directed , edge-disjoint :
Vertices : \(V\) ; Edges : \(\forall e=(u,v)\in E\) , \((u,v,1)\)
directed , vertex-disjoint
split vertex into in-vertex and out-vertex
Vertices : \(V_i'=\{v_i:v\in V,v\neq s\},V_o=\{v_o:v\in V,v\neq t\}\)
Edges :
- \(\forall v\in V\backslash \{s,t\}\) , \((v_i,v_o,1)\)
- \(\forall e=(u,v)\in E\) , \((u_o,v_i,1)\)
undirected
split as two directed edges
Both direction used ? no gain in \(v(f)\) .
8.3.4 Circulation with demand and lower bound
Description
Can have many sources and sinks .
Given \(d_v=f^{out}(v)-f^{in}(v)\) . \(d_v>0\) : source , \(d_v<0\) : sink , \(d_v=0\) : ordinary vertex .
bi-bounded capacity constraint : \(\forall e\in E\) , \(l_e\le f(e)\le c_e\) .
Goal : given vertex demand \(d_v\) , find a feasible circulation , satisfying flow conservation and bi-bounded capacity constraint .
Lemma : If \(f\) is a feasible circulation , then \(\sum\limits_{v\in V}d_v=0\) .
Source&Sink constraint without lower-bound
Vertices : \(V,s,t\)
Edges :
- \(\forall u\in V,d_u>0\) , \((s,u,d_u)\)
- \(\forall v\in V,d_v<0\) , \((v,t,-d_v)\)
Find a max \(s\)-\(t\) flow in new graph .
\(\exists\) feasible circulation \(\iff\) \(\max\limits_{f\in \mathtt{FLOW}}v(f)=\sum\limits_{d_v>0}d_v\) .
Capacity lower-bound
\(\forall e=(u,v,l,c)\) , let \(d_u'\gets d_u+l\) , \(d_v'\gets d_v-l\) , \(e'=(u,v,0,c-l)\) .
new graph \(G'\) : \(\forall e=(u,v,l_e,c_e)\in E,e'=(u,v,c_e-l_e)\) . \[ d_v'\gets d_v-\left(\sum_{(x,v,l_e,c_e)\in E}l_e-\sum_{(v,y,l_e,c_e)\in E}l_e\right) \] Reduce capacity lower-bound to source&sink constraint
8.3.5 Airline Scheduling Problem
Description
Input : Flight set \(\{(i,j):j\text{ is reachable from }i\}\) . This forms a directed graph .
Goal : Determine whether it is possible to serve all flights using \(K\) planes .
a.k.a. 最小路径覆盖问题
Equivalently , whether the graph can be decomposed into at most \(K\) vertex-disjoint paths .
Algorithm
using circulation problem
Vertices : \(s,t,V_i,V_o\) ( split each vertex into in-vertex and out-vertex )
Demand : \(d_s=K,d_t=-K,d_{v_i}=d_{v_o}=0\) .
Edges :
- \(\forall v\in V,(v_i,v_o,1,1)\)
- \(\forall e=(u,v)\in E,(u_o,v_i,0,1)\)
- \((s,t,0,K)\) ( in case we use planes less than \(K\) )
8.3.6 Parametric Flow
Description
Each edge has capacity being a linear function of \(\lambda\) .
\(c_{\lambda}(s,u)\) non-decreasing , \(c_{\lambda}(v,t)\) non-increasing .
\(\mathtt{maxflow}(\lambda)\) - \(\lambda\) diagram
piecewise linear concave : consider min-cut , cut is linear on \(\lambda\) .
[Gallo , Grigoriadiso , Tarjan ] : draw the diagram in time \(\mathcal O(nm\log \left(\frac{n^2}{m}\right))\)
At most \(n-2\) breakpoints : considering cut set , monotone .