Max-flow Part I

PDF of Eric’s handwritten notes are here.

Max-flow problem

Sending supply (e.g., internet traffic, products) from vertex s to vertex t without exceeding edge capacities.

Flow network

directed graph G=(V,E) with designated source s\in V and sink t\in V; a capacity c_e>0 for each e\in E.

f_e is the flow along the edge e. We want to maximize the flow from s to t.

Constraints:

  1. for all e\in E, 0\le f_e\le c_e (capability constraint)
  2. for all v\in V\backslash\{s\cup t\}, flow-in v = flow-out v: \sum_{\overrightarrow{wv}\in E}f_{wv}=\sum_{\overrightarrow{vz}\in E}f_{vz} (flow is conserved)

\text{size}(f) = total flow sent = flow-out s = \sum_{\overrightarrow{sv}\in E}f_{sv} = flow-in t = \sum_{\overrightarrow{zt}\in E}f_{zt}.

Simple algorithm idea

(see handwritten notes for an example)

  • start with f_e=0 for all e\in E
  • find an s-t path p with available capacity
  • increase the flow along p until some edge hits its capacity
  • repeat until no such s-t path exists

Residual network

For a flow network on G=(V,E) with capacities c_e and flow f_e, residual network G^f=(V,E^f) has edges:

  • if \overrightarrow{vw}\in E and f_{vw}<c_{vw}, then add \overrightarrow{vw} to G^f with capacity c_{vw}-f_{vw}
  • if \overrightarrow{vw}\in E and f_{vw}>0, then add \overrightarrow{wv} to G^f with capacity f_{vw}

Ford-Fulkerson algorithm

  1. set f_e=0 for all e\in E
  2. build the residual network G^f for the current for f
  3. check for a s-t path P in G^f, if there is no such path, return f as the output
  4. let c(P) be the minimum capacity along P in G^f
  5. augment f along P by c(p):
    • for a forward edge e\in P, increases f_e by c(P)
    • for a backward edge \overrightarrow{vw}\in P, decrease f_{wv} by c(P)
  6. repeat from 2.

Runtime

If capacities are integers, then the flow increases by \ge 1 unit each iteration. So if C = size of max-flow, it requires \le C iterations.

Each iteration involves a DFS or BFS, so takes O(|V|+|E|)=O(|E|) time (assuming G is connected). So the runtime is O(|E|C). This is pseudo-polynomial since it depends on the numbers in the input.

Better algorithm: [Edmonds-Karp ’72] takes the shortest augmenting path in G^f, which results in O(|V||E|) rounds, O(|V||E|^2) total time.


For a graph G=(V,E), a cut is a partition V=S\cup\overline{S}. For a directed G=(V,E) with two vertices s,t\in V, s-t cut is a partition V=L\cup R where s\in L, t\in R, L\cap R=\emptyset.

The capacity of a s-t cut is \text{capacity}(L,R)=\sum_{\overrightarrow{vw}\in E: v\in L, w\in R}c_{vw}=\text{total capacity from }L\rightarrow R.

Fact: for every flow f and every s-t cut (L,R), \text{size}(f)\le\text{capacity}(L,R).

Max-flow min-cut theorem

\max_{\text{flow} f} \text{size}(f)=\min_{(L,R)}\text{capacity}(L,R).

We”ll show this theorem by proving that for a flow f, if there is no augmenting path in the residual network, then there is a s-t cut (L,R) where \text{size}(f)=\text{capacity}(L,R). Hence \max_{\text{flow} f} \text{size}(f)\ge\min_{(L,R)}\text{capacity}(L,R). This also shows that Ford-Fulkerson finds a max-flow.

 

Advertisements