# Lecture 7 - Some Max-Flow and Min-Cut Algorithms

###### tags: `Algorithm`

## Max-Flow Min-Cut Problem
### Network
$G=(V,E,s,t,u)$
+ $(V,E)$: directed graph, no parallel edges
+ Two distinguished nodes, $s$: source, $t$: sink
+ $u(e)$: capacity of edge $e$
#### Flow
+ An $s$-$t$ flow is a function $f:E\to \Bbb R$ that satisfies
+ For each $e\in E$: $0\leq f(e)\leq u(e)$ (capacity)
+ For each $v\in V\setminus\{s,t\}$: $\sum_{e=(u,v)}f(e)=\sum_{e=(v,w)}f(e)$ (conservation)
+ $|f|=\sum_{e=(s,v)}f(e)$
+ $e$ is **saturated** if $f(e)=u(e)$
+ Max-Flow: find $s$-$t$ flow that maximizes net flow out of the source
#### Cut
+ An **$s$-$t$ cut** is a node partition $(S, T)$ such that $s\in S$, $t\in T$
+ The **capacity** of an $s$-$t$ cut $(S,T)$ is: $\sum_{e=(u\in S,v\in T)}u(e)$
+ Min $s$-$t$ cut: find an $s$-$t$ cut of minimum capacity
### Max-Flow Min-Cut Theorem (*Ford-Fulkerson, 1956*): The value of the max flow is equal to the value of the min $s$-$t$ cut
+ Find an $s$-$t$ path where each edge has $f(e)<u(e)$ and **augment** flow along the path
+ Repeat until you get stuck
+ Greedy algorithm fails
#### Residual Edge and Augmenting Path
+ Original graph $G=(V,E)$
+ Flow $f(e)$
+ Edge $e=(v,w)\in E$
+ Residual graph $G_f=(V,E_f)$
+ Residual edges $e=(v,w)$ and $e^R=(w,v)$
+ **Undo** flow sent
+ $E_f=\{e|f(e)<u(e)\}\cup \{e^R|f(e)>0\}$
+ $$u_f(e)=\begin{cases}u(e)-f(e), & \text{if $e\in E$}\\ f(e), & \text{if $e^R\in E$}\end{cases}$$
+ Augmenting path: the path in residual graph
+ Claim: Max-flow $\iff$ No augmenting path
#### Lemma 1: Let $f$ be a $s$-$t$ flow, and let $(S, T)$ be a cut s.t. $s\in S$, $t\in T$. Then, the net flow sent across the cut is equal to the amount reaching $t$
+ $\sum_{e=(u\in S,v\in T)}f(e)-\sum_{e=(u\in T, v\in S)}f(e)=\sum_{e=(s,v)}f(e)=|f|$
#### Lemma 2: Let $f$ be a flow, and let $(S, T)$ be a cut. Then, $|f|\leq cap(S, T)$
+ $|f|=\sum_{e=(u\in S,v\in T)}f(e)-\sum_{e=(u\in T, v\in S)}f(e)\leq\sum_{e=(u\in S,v\in T)}f(e)\leq\sum_{e=(u\in S,v\in T)}u(e)=cap(S,T)$
#### Corollary: Let $f$ be a flow, and let $(S, T)$ be a cut. If $|f|=cap(S, T)$, then $f$ is a max-flow and $(S,T)$ is a min-cut
#### Main Theorem: The followings are all equivalent (i) $f$ is max-flow (ii) There is no augmenting path relative to $f$ (iii) There exists a cut $(S, T)$ such that $|f| = cap(S, T)$
+ (i)$\to$(ii)
+ Show by contradiction
+ Let $f$ be a flow. If there exists an augmenting path, then we can improve $f$ by sending flow along path
+ (ii)$\to$(iii)
+ Let $f$ be a flow with no augmenting paths
+ Let $S$ be the set of vertices reachable from $s$ in residual graph
+ Clearly $s\in S$, and $t\notin S$ by definition of $f$
+ $|f|=\sum_{e=(u\in S,v\in T)}f(e)-\sum_{e=(u\in T, v\in S)}f(e)=\sum_{e=(u\in S,v\in T)}f(e)=cap(S,T)$
+ (iii)$\to$(i)
+ By Corollary
## Maximum Flow Algorithm
### *Ford-Fulkerson*'s Algorithm (*1956*)

Initially f=0 everywhere
while there is a s-t path in G_f
    let P be a simple path in G_f
    augment f along P
    update f and G_f
End while

#### Correctness
+ It is indeed an $s$-$t$ flow after augmentation
+ When the algorithm stops (**no more augmenting path in the residual graph**), $f$ is a maximum flow
#### Running Time
+ Choosing good augment paths
+ Use care when selecting augmenting paths
+ Assumption: All capacities are integers between $0$ and $U$
+ Invariant: Every flow value $f(e)$ and every residual capacities $u_f(e)$ remains an integer throughout the algorithm
+ **Theorem**: The algorithm terminates in at most $|f^*|\leq nU$ iterations
+ **Not really polynomial**
+ **Corollary**: If $U = 1$, then algorithm runs in $O(mn)$ time
+ **Integrality theorem**: If all edge capacities are integers, then there exists a max flow $f$ for which every flow value $f(e)$ is an integer
+ Note: Algorithm may not terminate on some pathological instances (with irrational capacities)
### Shortest Augmenting Path (*Edmonds-Karp*)
+ Intuition: Choosing path via breadth first search
+ Easy to implement
+ Finds augmenting path with fewest number of arcs
#### Admissible graph of $G_f$
+ Every edge $e$ has length $1$ in $G_f$
+ For each vertex $v$, define **$d(v)$** to be the length of **shortest path from $v$ to $t$**
+ $L$ is subgraph of the residual graph $G_f$ that contains only those edges $(v,w)\in E$ with $d(v)=d(w)+1$
+ That is, $(v,w)$ is on some shortest path from $s$ to $t$
+ Compute in $O(m+n)$ time using BFS, deleting back and side arcs
+ $P$ is a shortest $s$-$v$ path in $G_f$ if and only if it is an $s$-$v$ path in $L$
#### Lemma 1: Throughout the algorithm, the length of the shortest path never decreases
+ Let $f$ and $f'$ be flow before and after a shortest path augmentation
+ Let $L$ and $L'$ be admissible graphs of $G_f$ and $G_{f'}$
+ Only back edges are added to $G_{f'}$
+ Path with back edge has length greater than previous length
#### Lemma 2: After at most $m$ shortest path augmentations, the length of the shortest augmenting path strictly increases
+ At least one edge (the bottleneck edge) is deleted from $L$ after each augmentation, when distance from $s$ to $t$ stay the same
+ No new edges added to $L$ until distance from $s$ to $t$ strictly increases
#### Theorem: The shortest augmenting path algorithm runs in $O(m^2n)$ time
+ $O(m+n)$ time to find shortest augmenting path via BFS
+ $O(m)$ augmentations for paths of exactly $k$ edges
+ $O(mn)$ augmentations
### Shortest Augmenting Path: Improved Version (*Dinic*)
+ Two types of augmentations
+ Normal augmentation: length of shortest path doesn't change
+ Special augmentation: length of shortest path strictly increases
+ Ideas
+ Find a **blocking flow** in the current admissible graph (level graph)
+ Then $s$-$t$ distance in the residual graph will increase
#### Lemma 3: Group of normal augmentations takes $O(mn)$ time
+ Explicitly maintain **admissible graph**
+ Start at $s$, advance along an edge in $L$ until reach $t$ or get stuck
+ If reach $t$, augment and delete at least one edge
+ If get stuck, delete node (and its edges)
+ DFS procedure
+ A **blocking flow** is a flow in the **admissible graph** if every $s$-$t$ path contains a saturated edge
+ Run DFS from $s$ each time
+ If a vertex cannot go to the next level, delete it and backtrack
+ Takes $O(mn)$ time
#### Theorem: Algorithm runs in $O(mn^2)$ time
+ $O(mn)$ time for a blocking flow
+ At most $n$ increases for $s$-$t$ distance
### Max-Flow in Unit-Capacity Graph
+ Input: a simple graph $G=(V,E)$, such that $u(e)=1$ for all $e\in E$
+ Directed and undirected cases
#### Residual Graph
+ For **directed** unit-capacity version
+ No flow
+ With flow
+ For **undirected** unit-capacity version
+ No flow
+ With flow
#### Blocking Flow Algorithm
+ For the residual graph $G_f$, find the admissible graph by the distance to $t$
+ $dist(s,t)=D$
+ A **blocking flow** is a flow in the admissible graph if every $s$-$t$ path contains a saturated edge
+ It can be easily found by repeatly augmenting along $s$-$t$ path of length $dist(s,t)$
+ Until there is no $s$-$t$ path any more
+ Run DFS from $s$ each time
+ If a vertex cannot go to the next level, delete it and backtrack
+ **Unit-capacity graphs: blocking flow can be found in $O(m)$ time**
+ After augmenting along the blocking flow, the directions of the edges will be reversed
+ Any path overlaps the blocking flow must have a longer length
+ Now all augmenting path will have length $\geq D+1$
+ **The searching for blocking flow takes $O(m)$ time**
+ In $n^{2/3}$ steps the path will have length $>n^{2/3}$
+ The number of vertices in each level: $n_1,n_2,…,n_D$, where $D>n^{2/3}$
+ There exists $n_i$ and $n_{i+1}$ such that $n_i+n_{i+1}\leq 2n^{1/3}$ by pigeonhole principle
+ Then the remaining flow is bounded by $O(n^{2/3})$, so we will have an $O(mn^{2/3})$ time algorithm
+ Now all augmenting path will have length $\geq D+1$
+ **The searching for blocking flow takes $O(m)$ time**
+ In $m^{1/2}$ steps the path will have length $>m^{1/2}$
+ The number of edges between adjacent levels: $m_1,m_2,…,m_D$, where $D>m^{1/2}$
+ There exists $m_i$ such that $m_i\leq m^{1/2}$ by pigeonhole principle
+ Then the remaining flow is bounded by $O(m^{1/2})$, so we will have an $O(m^{3/2})$ time algorithm
+ Thus, the time complexity is $O(m\times \min\{m^{1/2},n^{2/3}\})$
### A Simple Algorithm for Undirected Unit-Capacity Graph (*Karger and Levine*)
#### Theorem: Any acyclic flow takes $O(n^{3/2})$ edges
+ Intuition: there are at most $\min\{n,O((n/k)^2)\}$ flows of length $k$
+ For unit-capacity graphs,any flow can be decomposed into paths
+ If the max-flow of the current residual graph $G_f$ is $v$, the distance between $s$ and $t$ in $G_f$ is $O(n/\sqrt{v})$
+ Because if the $s$-$t$ distance in $G_f$ is $>D$, the max-flow in $G_f$ is $O((n/D)^2)$
+ Then for any acyclic flow $f$, in the set $E_f$ of edges of $f$, it is the only maximum flow
+ We obtain $f$ in $E_f$ as if we augmented along the shortest augmenting path each time
+ Total number of edges: $O(\frac{n}{\sqrt{n}}+\frac{n}{\sqrt{n-1}}+...+n)=O(n\int_1^n\frac{1}{\sqrt{x}}dx)=O(n^{3/2})$
#### Algorithm
+ In **undirected unit-capacity** graph
+ In the residual graph, only edges carrying flow have directions
+ **Any acyclic flow takes $O(n^{3/2})$ edges**
+ Thus, when looking for an augmenting path, in the residual graph there are at most $O(n^{3/2})$ directed edges
+ For residual graph
+ Dynamic spanning forest structure with edge update
+ *Holm, Lichtenberg, and Thorup*: amortized $O(\log^2n)$ update time
+ In the residual graph, we construct the dynamic spanning forest structure by all the undirected edges, then treat every spanning tree as one vertex
:::info
+ Insert all edges of $G$ that not carrying flow into a dynamic connectivity structure, which maintains a spanning forest $T$
+ Repeat
+ Look for augmenting path in $E_f\cup T$
+ If no such path exists, return $f$
+ Else
+ Augment $f$ by that path
+ $f = decycle(f)$
+ Update the connectivity structure
:::
+ Retrieve path from the dynamic connectivity structure takes $\tilde O(n)$ time
+ Run BFS on directed edges $E_f$
+ Decycle after augmentation
+ Takes $O(n^{3/2})$ time for every augmenting path
+ In total: $O(m+n\times n^{3/2})=O(n^{5/2})$
### Summary
#### General Graph
| Algorithm | Running Time |
|:--------------------------------------------------- | ------------------------------------------------- |
| *Ford-Fulkerson* | $O(mv)$ |
| *Edmonds-Karp* | $O(m^2n)$ |
| *Dinic* | $O(mn^2)$ |
| *Dinitz* blocking flow algorithm with dynamic trees | $O(mn\log n)$ |
| Binary blocking flow algorithm | $O(m\times \min\{n^{2/3},m^{1/2}\}\log(n^2/m)\log U)$ |
| *Jim Orlin*'s+KRT(*King, Rao, Tarjan*)'s algorithm | $O(mn)$ |
$m$: number of edges
$n$: number of vertices
$v$: the amount of max-flow
$U$: maximum integer capacity
#### Algebraic Algorithm
+ $(1-\epsilon)$-Approximate (undirected)
+ $\tilde O(mn^{1/3}ε^{-11/3})$ by *Christiano, Kelner, Madry, Spielman, and Teng, 2011*
+ $\tilde O(m^{1+o(1)}ε^{-2})$ by *Sherman, 2013, and by Kelner, Lee, Orecchia and Sidford, 2013*
+ Exact algorithm (directed)
+ $\tilde O(mn^{1/2}\log^2U)$ by *Lee and Sidford*, (FOCS 2014 best paper)
#### Directed Graph
| Algorithm | Running Time | Capacity | Deterministic |
| ----------------------- | --------------------------- | -------- | ------------- |
| *Karger '97* | $\tilde O(m^{2/3}n^{1/3}v)$ | N | Randomized |
| *Karger and Levine '98* | $O(nm^{2/3}v^{1/6})$ | N | Deterministic |
| *Karger and Levine '98* | $\tilde O(m+nv^{3/2})$ | Y | Deterministic |
| *Karger and Levine '02* | $\tilde O(m+nv)$ | Y | Randomized |
Note that the maximum flow value $v\leq n-1$ for unit-capacity graph
## Min-Cut for Undirected Graph
Given an undirected graph, a global min-cut is a cut $(S,V\setminus S)$ minimizing the number of crossing edges, where a crossing edge is an edge $(u,v)$ s.t. $u\in S$ and $v\in V\setminus S$
### Intermediate Solution
+ Recall **Max-Flow Min-Cut Theorem**
+ For every pair of nodes $s$, $t$
+ Find the min-cut $M_{s,t}$
+ Choose the pair $(s,t)$ with the smallest $M_{s,t}$
+ Time: $O(n^2T)$, $T$: running time for max-flow algorithm
#### Improvement
+ We don’t need all pairs
+ Every node is in one side of a cut
+ Therefore, fix node $s$, try all other $n-1$ options as node $t$
+ Time: $O(nT)$
### Randomized Solution
#### Basic Idea
+ Repeat Until 2 nodes left
+ Choose edge at random
+ **Contract** edge
+ When only 2 node left
+ Take all edges between them as the min-cut
+ Time: $O(|E|)=O(n^2)$
#### Meaning of Contraction
+ Make edge $(a,b)$ with its two adjacent nodes $a$, $b$ into a single node $ab$
+ All edges of $a$ and $b$ will now be edges from $ab$ (creating a multigraph)
#### Probability of Output is Min-Cut
+ The output is a cut but not neccesary a min-cut
+ It it a min-cut when **none** of the edges in the **min-cut** $C^*=\{e_1,…,e_c\}$ are chosen to be contracted
+ We can assume that degree of every node in graph throughout contraction process $\geq c$
+ Otherwise, cut node and get cut of size $<c$
+ So the number of edges $m\geq nc/2$
+ Probability that one of the $C$ edges is chosen at first stage: $\frac{c}{E}\leq\frac{c}{nc/2}=\frac{2}{n}$
+ Probability that one of the $C$ edges is chosen after stage $i$ $\leq\frac{c}{(n-i)c/2}=\frac{2}{n-i}$
+ Probability of **not** choosing an edge of $C$ at stage $i$: $\geq 1-\frac{2}{n-i}=\frac{n-i-2}{n-i}$
+ The algorithm has $n-2$ stages (at that point $2$ nodes are left)
+ Probability of not choosing an edge from $C$ at **any** stage $$\geq(1-\frac{2}{n})(1-\frac{2}{n-1})...(1-\frac{2}{n-(n-4)})(1-\frac{2}{n-(n-3)})\\=(\frac{n-2}{n})(\frac{n-3}{n-1})(\frac{n-4}{n-2})...(\frac{3}{5})(\frac{2}{4})(\frac{1}{3})\\=\frac{2}{(n-1)(n-2)}=O(\frac{1}{n^2})$$
+ Run the algorithm $O(n^2)$ times and expect to get $C$ with constant probability
+ Total time: $O(n^4)$, no better than *Ford-Fulkerson*'s algorithm
### *Karger*’s algorithm
#### Idea
+ The probability of not hitting $C$ at stage $1$ is $1-\frac{2}{n}$ (almost $1$), it grows as we run more and more stages
+ The probability that $C$ not touched in the first $i$ steps $\geq\frac{(n-i)(n-i-1)}{n(n-1)}\approx\frac{(n-i)^2}{n^2}$
+ When $i=n-\frac{n}{\sqrt{2}}$, then the probability is approximate $\frac{(n-i)^2}{n^2}=\frac{1}{2}$
+ If we run two times until $\frac{n}{\sqrt{2}}$ nodes are left, **we expect that one of them still did not contract edges in $C$**
+ So, for each of these runs, when $\frac{n}{\sqrt{2}}$ nodes are left, **recurse on this smaller graph**
+ $n^2$ results, one of which is expected to be good
+ $n^2$ results, one of which is expected to be good
#### Main Algotithm

function Contract(G=(V,E), t) 
    while (|V|>t) 
        Choose e in G uniformly at random; 
        G:=G/e; 
    return G;
    
procedure Fastmincut(G=(V,E)) 
    if |V|<6 
        find min-cut by traditional way; 
    else 
        t:= |V|/sqrt(2); 
        G1:=contract(G, t); 
        G2:=contract(G, t); 
        return min{Fastmincut(G1), Fastmincut(G2)}; 

+ Running Time: $T(n)=2T(\frac{n}{\sqrt{2}})+O(n^2)\to T(n)=O(n^2\log n)$