a bit of graph: A little note on Maximum Flow

This is a scrap note for Maximum Flow - Minimum Cut Algorithm for KIV purposes...

Terminology:
1. Capacity of an edge: \(c(u,v)\)
2. Flow : \(f\)
3. Residual Graph : \(G_f\)
4. Residual capacity : \(c_f(u,v) = c(u,v) - f(u,v)\)
5. Backedge : \(c_f(v,u) = f(u,v)\)
6. Flow Conservation: \(\sum_{u \in V} f(v,u) = \sum_{u\in V} f(u,v)\)
7. Max Flow - Min Cut Theorem: Finding maximum flow is equivalent to finding the minimum cut of the flow network.

Ford-Fulkerson Algorithm
Let \(P\) be a simple \(s-t\) path on the residual graph called the augmenting path. Let bottleneck(P) be the lowest valued edge in path \(P\) on the residual graph.

augment(f, P):
    set b = bottleneck(P)
    for (u,v) in P:
        if u,v \(\in E\):  \(f(u,v) = f(u,v) + b\)
        else \(f(u,v) = f(u,v) - b\)
    return b

Ford-Fulkerson(G,E):
    Initialize \(G_f\), f = 0
    while exist augmenting path \(P\):
        f = f + augment(f, P)
    return f

Bound: \(O(C|E|)\)
Using Edmonds-Karp Algorithm (BFS Implementation of Ford-Fulkerson), running time is pseudo-polynomial

Push-Relabel Algorithm:
Terminology:
1. height-function \(h(v)\)
2. preflow
3. excess flow (on overflowing vertex) \(e(v)\)
4. preflow property: on every vertex, in flow must be at least equals to out flow: \(\sum f(v,u) - \sum f(u,v) \geq 0\)
5. If \((u,v) \in E_f\), then \(h(u) \leq h(v) + 1\)

Push:
6. Can only push downhill: in particular, can only push on edge (u,v) if \(e(u) > 0\) (i.e. u is overflowing vertex) and \(h(u) = h(v)+1\)

push(u,v):
    e = \(min \{ c_f(u,v), e(u) \} \)
    if u,v \(\in E\):  f(u,v) = f(u,v) + e
    else f(v,u) = f(v,u) - e
    e(u) = e(u) - e
    e(v) = e(v) + e

7. Push is saturating iff (u,v) disappear from \(G_f\), otherwise unsaturating.
8. If saturating push, then \(u\) is no longer overflowing vertex.

Relabel:
9. Can only be performed on overflowing vertex, and only if push cannot be performed: for all \(u,v \in E_f\), \(h(u) < h(v) + 1\)
10. Since \(u\) is overflowing, it is always true that there is at least an edge \((u,v) \in E_f\).

relabel(u):
    d = \(min_{(u,v) \in E_f} \{ h(v) \} \)
    h(u) = d + 1

Push-Relabel(G,E):
    Initialize \(f, h, e, G_f\) such that:
        for all v, h(v) = 0, except source: h(s) = \(|V|\)
        for all v, e(v) = 0.
        for all (s,v) \in E:
            f(s,v) = c(s,v)
            e(v) = c(s,v)
            e(s) = e(s) - c(s,v)
    while can push or relabel:
        push or relabel accordingly!
    return the max flow f

Correctness: hinges on a lot of lemmas, a few important ones:
1. There is no s-t path in \(G_f\). Proof: by contradiction using height function property and a fact about a simple path.
2. Invariant: preflow property is always conserved. Hence if the algorithm terminates, that means we cannot push or relabel, hence there is no overflowing vertex anymore, which means the preflow is indeed the flow, and since no s-t path in \(G_f\), by Max Flow - Min Cut theorem the flow is max flow.
Run-time: \(O(V^2E)\), the proof is very elaborate.