Network Flow I

Max-Flow and Min-Cut Problems

Flow Network

A flow network is a tuple $G = (V,E,s,t,c)$

• Digraph $(V,E)$ with source $s \in V$ (assume all nodes are reachable from $s$) and sink $t \in V$
• Capacity $c(e) \geq 0$ for each $e \in E$. (integer)

Intuition: material flowing through a transportation network; material originates at source and is sent to sink.

Maximum-Flow Problem

A $st$-flow (flow) $f$ is a function that satisfies:

• for each $e \in E$, $0 \leq f(e) \leq c(e)$ (capacity)
• for each $v \in V-\{s,t\}$: $\sum_{e \text{ in to } v} f(e) = \sum_{e \text{ out of } v} f(e)$ (flow conservation, meaning for every node not inclouding the source and the sink, the inflow must equal outflow)

Capacity is how much the edge can support and flow is how much is used.

The value of a flow $f$ is $val(f) = \sum_{e \text{ out of } s} f(e) - \sum_{e \text{ in to } s} f(e)$

• $\sum_{e \text{ in to } s} f(e)$ is always zero because there is no flow going into the source.
• this is the number you want to maximize.

Maximum-flow problem is to find a flow of maximum value

Minimum-Cut Problem

An $st$-cut (cut) is a partition $(A,B)$ of the nodes with $s \in A$ and $t \in B$.

Its capacity is the sum of the capacities of the edges from $A$ to $B$. $cap(A,B) = \sum_{e \text{ out of } A} c(e)$

Ford-Fulkerson

Greedy algorithm:

• start with $f(e) = 0$ for each edge
• Find an $s \rightsquigarrow t$ path $P$ where each edge has $f(e) < c(e)$.
• Augment flow along path $P$
• Repeat until you get stuck

However, this algorithm may fail. Why?

• Once greedy algorithm increases flow on an edge, it never decreases it.
• We need some mechanism to "undo" a bad decision.

Residue Netowrk

Defining residue network

When ever you send some flow across a pipe, you create a back pipe that has the same flow in the opposite direction.

The original edge $e = (u,v) \in E$

• flow would be $f(e)$
• capacity $c(e)$.

The reverse edge $e^{reverse} = (v,u)$

• "undos" the flow sent

The residue capacity:

$$c_f(e) = \left\{ \begin{array}{lr} c(e) - f(e), & \text{if } e \in E\\ f(e^{reverse}), & \text{if } e^{reverse} \in E \end{array} \right.$$

Residual network: $G_f=(V,E_f,s,t,c_f)$

• $E_f = {e:f(e) < c(e)} \cup {e: f(e^{reverse}) > 0}

Defining augmenting path, a simple $s \rightsquigarrow t$ path in the residual network $G_f$.

The bottleneck capacity of an augmenting path $P$ is the minimum residual capacity of any edge in $P$.

Key property: let $f$ be the flow and let $P$ be an augmenting path in $G_f$. Then, after calling $f' \leftarrow Augment(f,c,P)$ the resulting $f'$ is a flow and $val(f') = val(f) + bottleneck(G_f,P)$.

Augment($f,c,P$)

• $\delta \gets$ bottleneck capacity of augmenting path $P$
• For each edge $e \in P$
  • If ($e \in E$) $f(e) \gets f(e) + \delta$
  • Else $f(e^{reverse}) \gets f(e^{reverse}) - \delta$
• Return $f$.

Ford-Fulkerson Algorithm

Ford-fulkerson augmenting path algorithm:

• start with $f(e)=0$ for each edge $e \in E$.
• find an $s \rightsquigarrow t$ path $P$ in the residual network $G_f$.
• augment flow along path $P$
• repeat until you get stuck

Ford-Fulkerson($G$)

• For each edge $e \in E$ : $f(e) \gets 0$
• $G_f \gets$ residual network of $G$ with respect to flow $f$.
• While (there exists an $s \rightsquigarrow t$ path $P$ in $G_f$)
  • $f \gets$ Augment($f,c,P$).
  • Update $G_f$
• Return $f$.

Max-flow min-cut theorem

Flow value lemma: Let $f$ be any flow and let $(A,B)$ be any cut, then the value of the flow $f$ equals the netflow across the cut $(A,B)$.

$val(f) = \sum_{e \text{ out of } A} f(e) - \sum_{e \text{ in to } A} f(e)$

Weak duality says that let $f$ be any flow and $(A,B)$ be any cut. Then, $val(f) \leq cap(A,B)$. Proof using the flow value lemma: \begin{align} val(f) &= \sum_{e \text{ out of } A} f(e) - \sum_{e \text{ in to } A} f(e) \\ &\leq \sum_{e \text{ out of } A} f(e) \\ &\leq \sum_{e \text{ out of } A} c(e) \\ &= cap(A,B) \end{align}

In other words, the value of the flow is always less than or equal to the capacity of the cut

Certificate of optimality The collorary: let $f$ be a flow and let $(A,B)$ be a min cut. If $val(f) = cap(A,B)$ then $f$ is a max flow and $(A,B)$ is a min cut.

Proof:

• for any flow $f'$: $val(f') \leq cap (A,B) = val(f)$. (this comes from weak duality). Essentially, $val(f') \leq val(f)$.
• for any cut $(A', B')$: $cap(A', B') \geq val (f) = cap(A,B)$ This implies that $(A,B)$ is the min cut.

The max-flow min-cut theorem says that the value of the max flow = capacity of a min cut (with strong duality).

Augmenting path thoerem: a flow $f$ is a max flow iff no augmenting paths. Proof: the following three conditions are equivalent for any flow $f$:

1. there exists a cut $(A,B)$ such taht $cap(A,B) = val(f)$
2. $f$ is a max flow
3. there is no augmenting path with respect to $f$ (if ford-fulkerson terminates, then $f$ is max flow)

$i \implies ii$ because this is the weak duality corollary. $ii \implies iii$ because we prove the contrapositive $\neg iii \implies \neg ii$

• suppose that there is an augmenting path with repsect to $f$
• can improve flow $f$ by sending flow along this path
• thus, $f$ is not max flow. $iii \implies i$
• let $f$ be a flow with no augmenting paths
• let $A =$ set of nodes reachable from $s$ in residual network $G_f$.
• by definition of $A$: $s \in A$
• by definition of flow $f$: $t \notin A$.

$val(f) = \sum_{e \text{ out of } A} f(e) - \sum_{e \text{ in to } A} f(e) = \sum_{e \text{ out of } A} c(e) - 0 = cap(A,B)$

Baseball Eliminations

Figure out which teams have a chance of finishing the season with the most wins. We can observe that some teams are mathematically eliminated. Their maximum wins is still less than another team's minimum wins.

• the answer depends not only on how many games they already won and left to play, but on whom they're against.