Network Flow Algorithms and the Ford-Fulkerson Method

Course Overview and Historical Context

• Course Identification: COSC248 Algorithms and Complexity.
• Focus: Network Flow Algorithms.
• Core References: Algorithm Design Manual 3rd Ed (Chapters 8.5, 8.6, 18.8, and 18.9).
• Historical Foundation: The Soviet Rail Network (1955). This is cited in the literature as a foundational reference for the history of transportation and maximum flow problems, specifically referencing Alexander Schrijver in Math Programming, 91: 3, 2002.

Applications of Maximum Flow and Minimum Cut

• Physical Network Abstractions:
  • Railroads transporting trains.
  • Road systems and vehicular traffic.
  • Fluid mechanics in pipes and water systems.
  • Electrical current flowing through wires.
• Advanced Reductions and Non-trivial Applications:
  • Data mining and image segmentation.
  • Open-pit mining and project selection.
  • Airline scheduling and distributed computing.
  • Network connectivity, reliability, and intrusion detection.
  • Bipartite matching and egalitarian stable matching.
  • Sports administration (e.g., Baseball elimination).
  • Security of statistical data.
  • Multi-camera scene reconstruction.

Flow Network Fundamentals

• Graph Abstraction: A flow network is represented as a directed graph $G = (V, E)$ with no parallel edges.
• Distinguished Nodes:
  • $s$: The source node, from which flow originates.
  • $t$: The sink node, where flow terminates.
• Edge Capacity ($c(e)$): Every edge $e$ has a non-negative capacity representing the maximum material that can flow through it.
• Structural Constraints: The source node typically has an infinite input available to push through the network.

The Minimum-Cut Problem

• Definition of an s-t Cut: An s-t cut is a partition $(A, B)$ of the set of vertices $V$ such that $s \in A$ and $t \in B$.
• Capacity of a Cut: The capacity of a cut $(A, B)$ is defined as the sum of the capacities of all edges directed from partition $A$ to partition $B$. Mathematically: $\text{Capacity}(A, B) = \sum_{e \text{ out of } A} c(e)$.
• Problem Goal: To find a cut with the minimum total capacity among all possible s-t cuts.
• Calculations from Examples:
  • In a network with specific edge weights, a cut partition might yield a capacity of $10 + 5 + 15 = 30$.
  • Another cut partition in the same network might yield $9 + 15 + 8 + 30 = 62$.
  • A third partition shown yields $10 + 8 + 10 = 28$. If this is the lowest possible capacity, it is the minimum cut.

The Maximum-Flow Problem

• Definition of s-t Flow: A function $f$ that satisfies Two main constraints:
  1. Capacity Constraint: For each edge $e \in E$, the flow must be non-negative and less than or equal to the capacity: $0 \le f(e) \le c(e)$.
  2. Conservation Constraint: For each node $v$ except the source ($s$) and sink ($t$), the total flow entering the node must equal the total flow exiting the node: $\sum_{e \text{ in to } v} f(e) = \sum_{e \text{ out of } v} f(e)$.
• Value of Flow: The value of a flow $f$, denoted $|f|$, is the net flow leaving the source $s$: $|f| = \sum_{e \text{ out of } s} f(e)$.
• Problem Goal: To push the maximum possible amount of flow through the network from source to sink without violating capacity or conservation constraints.
• Interactive Question Example: For a graph with specified edge loads (flow/capacity), the value might be calculated as $|f| = 24$ or $|f| = 28$.

Relationship Between Flows and Cuts

• Net Flow Across Cuts: For any flow $f$ and any s-t cut $(A, B)$, the net flow sent across the cut is equal to the amount leaving the source $s$. Calculations from slides demonstrate this:
  • Example 1: $|f| = 6 + 0 + 8 - 1 + 11 = 24$.
  • Example 2: $|f| = 10 - 4 + 8 - 0 + 10 = 24$.
• Flow-Cut Inequality: For any flow $f$ and any s-t cut $(A, B)$, the value of the flow is at most the capacity of the cut: $\text{Value}(f) \le \text{Capacity}(A, B)$.
• Implication: If a cut capacity is $30$, then no flow value can ever exceed $30$.

Residual Graphs and Augmenting Paths

• Greedy Strategy Limitation: A simple greedy algorithm (finding paths until full) does not work for max-flow because local optimality does not lead to global optimality; there is no way to "undo" a bad decision in traditional greedy approaches.
• Residual Edge: For an original edge $e = (u, v)$ with capacity $c(e)$ and flow $f(e)$, a residual edge $e^R = (v, u)$ is created in the residual graph to represent the potential to "undo" flow (send flow back).
• Residual Graph ($G_f$): A graph $G_f = (V, E_f)$ consisting of:
  • Forward edges: edges with residual capacity $c(e) - f(e) > 0$.
  • Backward edges: edges with positive flow $f(e) > 0$, allowing us to subtract/redirect flow.
• Augmenting Path: A path from $s$ to $t$ in the residual graph $G_f$. It consists of non-full forward edges or non-empty backward edges.
• Bottleneck Capacity: The minimum residual capacity among all edges in an augmenting path.

The Ford-Fulkerson Algorithm

• Initialization: Set initial flow $f(e) = 0$ for all edges and construct the initial residual graph $G_f$.
• Algorithm Steps:
  1. Find Path: Identify an augmenting path $P$ in the residual graph $G_f$.
  2. Compute Bottleneck: Determine the bottleneck capacity $b$ of path $P$.
  3. Augment: Increase flow on forward edges by $b$ and decrease flow on reverse edges by $b$.
  4. Update: Re-calculate the residual graph $G_f$ based on the new flow values.
  5. Repeat: Continue until no augmenting path exists from $s$ to $t$.
• Pseudo-code (Augment Function):
  • b = bottleneck(P)
  • foreach edge e in P:
  • if (e is forward) f(e) = f(e) + b
  • else (e is backward) f(eR) = f(e) - b
• Pseudo-code (Main Algorithm):
  • while (augmenting path P exists): f = Augment(f, c, P); update Gf

Max-Flow Min-Cut Theorem

• Augmenting Path Theorem: A flow $f$ is at its maximum value if and only if there are no augmenting paths in the residual graph $G_f$.
• Max-Flow Min-Cut Theorem (Ford-Fulkerson, 1956): The value of the maximum s-t flow is exactly equal to the capacity of the minimum s-t cut.

Time Complexity

• Path Finding: Finding a single augmenting path (e.g., using DFS or BFS) takes $O(m + n)$, which can be simplified to $O(m)$ where $m$ is the number of edges.
• Iteration Count: The maximum number of iterations the algorithm can perform is bounded by the total flow value $f$. In integer-capacity networks, this is at most $C$, where $C$ is the maximum capacity.
• Total Runtime: The overall time complexity is $O(m \times C)$.

Rules for Identifying Paths (Practical Summary)

1. Going Forward: Can only move in the edge's direction if flow is less than capacity (there is "flow to add"). Example: $8/10$ can move forward, but $4/4$ is capped.
2. Going Backward: Can only move opposite to the edge's direction if flow is greater than zero (there is "flow to give"). Example: $6/8$ can go backward, but $0/4$ cannot because there is no flow to subtract.

Practice Exercises

• Exercise 1 (Greedy Check): In a specific small graph with edges from $s$ to nodes $1, 2$ and then to $t$, the optimal (Max Flow) solution was determined to be $30$, while a poor greedy choice might only yield $20$.
• Exercise 2 (Complex Graph): In a multi-node graph (nodes $A, B, C, D$ between $S$ and $T$), the solution for maximum flow is provided as $19$.