Ford-Fulkerson

Summary

Find the max flow of a graph by iteratively augmenting the residual graph

Contents

• Problem Setup
• Anti-Parallel Edges
• Toy Example
  • Simple Algorithm
  • Residual Network
• Ford-Fulkerson Algorithm
  • Runtime

Problem Setup

Sending supply from vertex s to t

Goal is to maximize amount sent without exceeding capacity

A flow network is a graph G=(V,E), designated s,t in V, and for each e in E, capacity $c_e > 0$

$f_e =$ flow along edge e

$\forall e \in E, 0 \le f_e \le c_e$

$\forall v \in V - {s \bigcup t},$ flow in must equal flow out (conserved)

$\forall v \in V - {s \bigcup t}, \displaystyle\sum_{\overrightarrow{wv} \in E}f_{wv} = \displaystyle\sum_{\overrightarrow{vz} \in E}f_{vz}$

size of flow is total flow sent

• flow out of s
• flow in to t

size = 12

There’s never a reason to use a cycle

Anti-Parallel Edges

We can simplify the graph by removing anti-parallel edges

Toy Example

Simple Algorithm

Start by initializing the flow to be zero everywhere

Create an available graph based on the input graph and try to find a path from s to t

Send max flow along that path

Repeat until there is no more path from s to t

instead we can create a Residual Graph by adding antiparallel edges to one way edges

Residual Network

For flow network G=(V,E0) with ce for e in E, and fe for e in E.

residual network Gf=(V,Ef)

if $\overrightarrow{vw} \in E &amp; f_{vw} < c_{vw}$ then add $\overrightarrow{vw}$ to Gf with capacity $c_{vw} - f_{vw}$

if $\overrightarrow{vw} \in E &amp; f_{vw} > 0$ then add $\overrightarrow{wv}$ to Gf with capacity $f_{vw}$

Ford-Fulkerson Algorithm

• Set fe = 0 for all e in E
• Build residual network Gf for current flow f
• Check for an s-t path in Gf
  • If no such path, output f
• Given path P, let cP = min capacity along P in Gf
• Augment f by cP units along P
  • For every forward edge, increase flow by this amount
  • For every backward edge, decrease flow by this amount
• Repeat

Runtime

O(mC) where C is size of max flow (assuming integer capacities)