Algorithm Design 10

Chapter 8 Network Flow

8.1 Basic Definitions

  1. 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

  2. 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)\)
  3. 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 .

  4. 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) \]

  5. 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 .

  1. 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\} \]

  2. 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;
    }
    }
  3. Analysis

    1. Lemma : Upon termination of FF , we get a feasible flow

      All updates during FF do not violate the constraints .

    2. 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)\) .

    3. 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^*)\) .

  4. 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

  1. Description

    Input : undirected graph \(G=(L+R,E)\) , \(E\subseteq\{(u,v):u\in L,v\in R\}\)

    Output : Matching \(M\) with maximum edges .

  2. 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)\)
  3. Hungary Algorithm / Alternating Path Algorithm

    Alternating Path : equivalent as a path in residue graph \(G_f\) .

8.3.2 Perfect Matching

  1. Description

    undirected graph \(G=(L+R,E)\) , \(|L|=|R|=n\) .

    A perfect matching is a matching with \(n\) edges

  2. 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

  1. Description

    Input : directed/undirected graph \(G=(V,E)\) , \(s,t\in V\)

    Output : maximum \(s\)-\(t\) vertex/edge disjoint path

  2. directed , edge-disjoint :

    Vertices : \(V\) ; Edges : \(\forall e=(u,v)\in E\) , \((u,v,1)\)

  3. 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)\)
  4. undirected

    split as two directed edges

    Both direction used ? no gain in \(v(f)\) .

8.3.4 Circulation with demand and lower bound

  1. 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 .

  2. Lemma : If \(f\) is a feasible circulation , then \(\sum\limits_{v\in V}d_v=0\) .

  3. 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\) .

  4. 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

  1. 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 .

  2. 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

  1. Description

    Each edge has capacity being a linear function of \(\lambda\) .

    \(c_{\lambda}(s,u)\) non-decreasing , \(c_{\lambda}(v,t)\) non-increasing .

  2. \(\mathtt{maxflow}(\lambda)\) - \(\lambda\) diagram

    piecewise linear concave : consider min-cut , cut is linear on \(\lambda\) .

  3. [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 .