The shipping problem

Goal: determine the maximum amount of syrup that can be shipped from Montreal to Vancouver in a month.

Flow Network

A flow network is a directed graph $G = (V, E)$ with a source vertex $x$ and target vertex $t$ such that

• each edge $e$ has capacity $c(e)$, which is a non-negative number;
• the source $s$ has no incoming edges;
• the target $t$ has no outgoing edges.

For most of the lectures we will assume capacities are integers between $0$ and $C$ (finite). We want to model the flow of goods through the network.

An $s-t$ is a function $f: E \rightarrow \mathbb{R}_{\geq 0}$ satisfying

1. (capacity constraints) for each $e\in E, 0\leq f(e) \leq c(e)$;
2. (flow conservation constraints) for each $u\in V \setminus \{s, t\}$: $$\begin{aligned} f^{out}(v) = \sum_{(v, u)\in E}f(v, u) == \sum_{(u, v)}f(u, v) = f^{in}(v) \end{aligned}$$

Problem Statement

Input: a flow network $G = (V, E)$ with source $s$, target $t$, and capacities $c: E \rightarrow \mathbb{R}_{\geq 9}$

Goal: Output a flow $f: E \rightarrow \mathbb{R}_{\geq 0}$ satisfying the capacity and flow conservation constraitns, and maximizing flow value.

Ford Fulkerson Method (doesn't quite work?)

Obersvation 1: if flows $f$ and $f'$ flow conservation, so does $f + f'$. Observation 2: for any $s\rightarrow t$ path $p$, the flow

satisfies flow conservation.

Greedy algorithm: push as much flow as possible on some path

for e in E:
    f(e) = 0

while there exists (s->t path) p in G:
    delta = min{c(e) - f(e)} // minimum available capacity
    for e in E
        f'(e) = f(e) + delta
    f = f'
    remove edges e with f(e) = c(e) from E
return f

Counterexample: why the greedy push fails

The shipping network below witnesses that “pick any $s \rightarrow t$ path and saturate it” can get stuck strictly below the true maximum flow.

1. The greedy algorithm might first pick the path $s \rightarrow a \rightarrow b \rightarrow t$. The bottleneck is the $1$-capacity arc $a \rightarrow b$, so it sends one unit of flow and removes that saturated edge from $E$.
2. With $a \rightarrow b$ gone, the remaining graph only allows $9$ units along $s \rightarrow a \rightarrow t$ and $9$ units along $s \rightarrow b \rightarrow t$, for a total flow of $19$.
3. The optimal solution is $10$ units on each of $s \rightarrow a \rightarrow t$ and $s \rightarrow b \rightarrow t$, totalling $20$. The single unlucky greedy choice permanently blocks one unit and prevents us from reaching the optimum.

Residual Network

Idea: allow reversing decision by pushing flow back

For an $s-t$ flow $f$ in $G$, the residual network $G_f = (V, E_f)$ has

• forward edge: $u\rightarrow v$ for each $u \rightarrow v$ in $E$ such that $f(u, v) < c(u, v)$, with capacity $c_f(u, v) = c(u, v) - f(u, v)$ (residual capacity).
• backward edge: $v\rightarrow u$ for each $u \rightarrow v$ in $E$ such that $f(u, v) > 0$, with capacity $c_f(u, v) = f(u, v)$ (residual capacity).

Augmenting flow

def Augment(f, p):
    residual_cap = min{c_f(u, v) : (u, v) in p}
    for edge (u, v) in p:
        if (u, v) is a forward edge:
            f'(u, v) = f(u, v) + residual_cap
        else:
            f'(u, v) = f(u, v) - residual_cap
    return f'

Ford-Fulkerson (Meta-) algorithm

FordFulkerson(G, s, t):
    for e in E:
        f(e) = 0
    G_f = G
    while there is a simple path p from s to t in G_f:
        f' = Augment(f, p)
        f = f'
        update G_f
    return f

Validity of argument

f' = Augment(f, p)

Why does $f'$ satify capacity and flow conservation constraints?

capacity: from definition of $c_f(u, v)$

flow conservation: Consider arbitrary vertex $v$

• case 1: $(u, v), (v, w)$ are forward edges
  • $f'(u, v) = f(u, v) + c_f(p)$
  • $f'(v, w) = f(v, w) + c_f(p)$
• case 2: $(u, v)$ is forward, $(v, w)$ is backward
  • $f'(u, v) = f(u, v) + c_f(p)$
  • $f'(v, w) = f(v, w) - c_f(p)$

Running Time Analysis

Reminder: we assume all capacities in $G$ are integers between $1$ and $C$.

Observation: throughout, residual capacities and flow values are integers.

Lemma 1

Lemma 1: For a simple $s\rightarrow t$ path $p$ in $G_f$, and $f' = Augment(f, p), val(f') = val(f) + c_f(p)$.

Since $p$ is simple, there is exactly 1 edge $(s, v)$ in $p$ touching $s$. Also $(s, v)$ is a forward edge, since no edges in $G$ go into $s$. Which means we have $f'^{out}(s) = f^{out}(s) + c_f(p)$

Lemma 2

We want to somehow show that this while loop terminates.

Lemma 2: Suppose $f$ is an $s-t$ flow in $G$. Then $val(f)\leq \sum_{(s, u)\in E}c(s, u) \leq Cn$