Ford Fulkerson

Network

A network consists of the following

A finite directed graph $N = (V, E)$
A source $s \in V$ and a sink $t \in V$
A capacity function which is a mapping $c : E \to ℝ^{+}$ which represents the maximum amount of flow that can pass through an edge.

In Neighbor Function

We define the function

in-nhbs (u) : = {x : (x, u) \in E}

Out Neighbor Function

We define the function

out-nhbs (u) = {x : (u, x) \in E}

Flow

A flow through a network is a mapping

f : E \to ℝ^{+}

such that the following hold true:

Capacity Constraint: For every edge $(u, v) \in E$ we have that $f (u, v) \leq c (u, v)$
Conservation of Flow: For each vertex $v$ apart from $s$ and $t$ we have the following

\sum_{x \in in-nhbs (v)} f (x, v) = \sum_{y \in out-nhbs (v)} f (v, y)

Flow out of the Source is the Same as Flow Entering the Sink

\sum_{y \in out-nbhs (s)} f (s, y) = \sum_{x \in in-nhbs (t)} f (x, t)

This follows from the conservation axiom for flows.

Flow Value

Given a network, and a flow, then it's flow value is defined as :

| f | : = \sum_{y \in out-nbhs (s)} f (s, y) = \sum_{x \in in-nhbs (t)} f (x, t)

Maximum Flow Problem

Given any network, maximize

| f |

s-t Cut

s - t

cut is a partition

{S, T}

V

such that

s \in S

and

t \in T

Cut Set

Suppose that

S, T

is an s-t cut, then we define

X_{C} : = {(u, v) \in E : u \in S, v \in T}

Max-Flow Min-Cut

The maximum value of an s-t flow is equal to the minimum capacity over all s-t cuts.

Residual Edge

Given a regular directed graph, with edge capacities and flow values assigned to them, then given an edge

e

going from vertex

x

y

, with capacity

c

and having flow value

f

then its residual edge is defined as a new edge that goes from

y

x

and having flow equal to

c - f

Residual Graph

The residual graph of a directed graph with edge capacities and flow values assigned to them is the graph resulting after adding the residual edge of every edge in the original graph.

Here's an overview of the Ford Fulkerson algorithm:

Initialization: Start with initializing the flow on each edge to zero.
Find augmenting paths: Repeat the following steps until no augmenting paths can be found:
- Use a path-finding algorithm (commonly DFS - Depth First Search) to find an augmenting path from the source to the sink in the residual graph. An augmenting path is a simple path (no repeated vertices) from the source to the sink where each edge has residual capacity greater than zero.
- Residual capacity of an edge is the difference between its capacity and its current flow. If an edge has a flow of 3 out of a capacity of 5, then its residual capacity is 2.
- If an augmenting path is found, determine the maximum additional flow that can be sent along this path. This is usually the minimum residual capacity of the edges in the path.
Update flow: Once an augmenting path is found, update the flow along that path by adding the maximum additional flow found in step 2. This process increases the total flow from the source to the sink.
Repeat: Repeat steps 2 and 3 until no augmenting paths can be found.
Termination: When no augmenting paths can be found, the algorithm terminates, and the maximum flow is the sum of flows leaving the source.

Sum of Capacities Runtime

Show that the maximum number of updates to the flow in the residual graph needed before Ford-Fulkerson terminates is in

𝒪 (C)

where

C

is the sum of the capacities of all directed edges incident to the sink vertex

t

Recall that the flow value of a network is equal to the of the flow entering the terminal node. On each iteration if it is not the final one then an augmenting path is found which starts from $s$ and goes to $t$ , and the flow of this path is increased by at least one, which increases the amount of of flowing going into the terminal node, which reversely means that one of the edges going into the terminal node has a flow value that increased by at least one.

In the worst case each time when we augment a path we increase by one, and we will not stop until all the edges going into the terminal node are fully saturated, and thus will take at most $C$ iterations.