5.1 Maximum flow algorithms

Maximum flow algorithms are crucial in network optimization, finding the most efficient way to send resources through capacity-constrained systems. These techniques solve problems in transportation, communication, and resource allocation by maximizing flow from a source to a sink node.

The chapter covers key algorithms like Ford-Fulkerson, Edmonds-Karp, and Push-Relabel, explaining their mechanics and time complexities. It also explores applications in bipartite matching, image segmentation, and discusses practical implementation considerations for real-world use.

Definition of maximum flow

• Foundational concept in network flow problems within Combinatorial Optimization
• Addresses the challenge of maximizing flow through a network with capacity constraints
• Crucial for understanding and solving various optimization problems in transportation, communication, and resource allocation

Network flow terminology

• Directed graph G = (V, E) represents the network structure
• Source node s initiates flow, sink node t receives flow
• Edge capacities c(u, v) limit flow between connected nodes
• Flow f(u, v) represents amount of flow on each edge
• Flow conservation ensures incoming flow equals outgoing flow at each node (except s and t)

Maximum flow problem statement

• Objective maximizes total flow from source s to sink t
• Subject to capacity constraints: $0 \leq f(u, v) \leq c(u, v)$ for all edges (u, v)
• Flow conservation constraint: $\sum_{v \in V} f(u, v) = \sum_{v \in V} f(v, u)$ for all nodes u except s and t
• Value of flow defined as $|f| = \sum_{v \in V} f(s, v)$, total flow leaving source

Ford-Fulkerson method

• Iterative algorithm for solving maximum flow problems
• Fundamental approach that forms the basis for more advanced algorithms
• Introduces key concepts like augmenting paths and residual graphs

Residual graph concept

• Represents remaining capacity in the network after each iteration
• Constructed by adding reverse edges with capacity equal to current flow
• Forward edges in residual graph have capacity c(u, v) - f(u, v)
• Allows for flow cancellation and rerouting during algorithm execution

Augmenting path algorithm

• Finds path from source to sink in residual graph with available capacity
• Augments flow along the path by the minimum residual capacity
• Updates residual graph after each augmentation
• Continues until no more augmenting paths exist

Analysis of Ford-Fulkerson

• Correctness proven by max-flow min-cut theorem
• Time complexity depends on choice of augmenting path selection method
• Worst-case running time can be poor for arbitrary capacities
• Guaranteed to terminate for integer capacities
• Forms basis for more efficient algorithms like Edmonds-Karp

Edmonds-Karp algorithm

• Specific implementation of Ford-Fulkerson method
• Guarantees polynomial-time complexity for all inputs
• Widely used in practice due to its simplicity and efficiency

Breadth-first search implementation

• Uses BFS to find shortest augmenting path in residual graph
• Ensures path length increases monotonically with each iteration
• Prevents pathological cases that can occur in basic Ford-Fulkerson
• Leads to faster convergence and improved worst-case time complexity

Time complexity analysis

• Overall time complexity: $O(VE^2)$ for a graph with V vertices and E edges
• Number of augmentations bounded by $O(VE)$
• Each BFS takes $O(E)$ time
• Significant improvement over Ford-Fulkerson for dense graphs or large capacities

Push-relabel algorithm

• Different approach to maximum flow problem compared to augmenting path methods
• Maintains a preflow instead of a valid flow during execution
• Generally faster in practice, especially for dense graphs

Push and relabel operations

• Push operation moves excess flow from a node to its neighbor
• Relabel operation increases the height of a node to enable more pushes
• Height function h(v) maintains a valid labeling throughout the algorithm
• Excess e(v) tracks the difference between incoming and outgoing flow at each node

Generic push-relabel algorithm

• Initializes preflow by saturating all edges leaving the source
• Repeatedly applies push and relabel operations to nodes with excess
• Terminates when all excess flow reaches the sink or returns to the source
• Maintains invariants to ensure correctness and progress

FIFO push-relabel variant

• Uses a first-in-first-out queue to manage active nodes
• Improves practical performance over generic algorithm
• Achieves $O(V^3)$ time complexity, independent of edge count
• Performs well on a wide range of problem instances

Dinic's algorithm

• Combines ideas from Ford-Fulkerson and shortest path algorithms
• Achieves better time complexity than Edmonds-Karp
• Particularly efficient for unit capacity networks

Blocking flow concept

• Maximal flow where every path from source to sink contains a saturated edge
• Computed efficiently using depth-first search in level graph
• Each blocking flow computation makes significant progress towards maximum flow

Level graph construction

• Assigns levels to nodes based on their distance from the source
• Only includes edges that lead to nodes at the next level
• Rebuilt after each blocking flow computation
• Ensures augmenting paths have strictly increasing length

Time complexity of Dinic's

• Overall time complexity: $O(V^2E)$ for general networks
• Improves to $O(V^{2/3}E)$ for unit capacity networks
• Number of phases (level graph constructions) bounded by $O(V)$
• Each phase takes $O(VE)$ time to compute blocking flow

Applications of maximum flow

• Demonstrates versatility of network flow techniques in Combinatorial Optimization
• Solves diverse problems by modeling them as flow networks
• Often provides efficient solutions to seemingly unrelated optimization tasks

Bipartite matching problems

• Models matching problems as flow networks with unit capacities
• Maximum flow corresponds to maximum cardinality matching
• Solves assignment problems (job assignments)
• Extends to weighted bipartite matching using min-cost flow

Minimum cut applications

• Finds minimal set of edges whose removal disconnects source from sink
• Used in network reliability analysis (identifying critical links)
• Applies to image segmentation for object recognition
• Solves certain types of clustering problems

Image segmentation

• Constructs flow network from image pixels
• Edge capacities based on similarity between neighboring pixels
• Source and sink represent foreground and background
• Minimum cut provides optimal segmentation of image into regions

Capacity scaling technique

• Improves time complexity of augmenting path algorithms
• Particularly effective for networks with large capacity values
• Gradually refines the solution by considering increasingly finer capacity granularity

Scaling factor introduction

• Starts with large scaling factor Δ, initially the largest power of 2 ≤ maximum capacity
• Only considers edges with residual capacity ≥ Δ in each phase
• Halves Δ after each phase until Δ < 1
• Limits number of augmenting paths found in each phase

Improved time complexity

• Achieves $O(E^2 \log U)$ time complexity, where U is the maximum edge capacity
• Significantly better than Edmonds-Karp for networks with large capacities
• Each scaling phase runs in $O(E^2)$ time
• Number of scaling phases limited to $O(\log U)$

Maximum flow in practice

• Bridges theoretical algorithms with real-world implementation considerations
• Highlights importance of choosing appropriate algorithm for specific problem instances
• Discusses practical aspects of deploying maximum flow solutions

Implementation considerations

• Data structures choice impacts performance (adjacency lists vs. matrices)
• Heuristics can improve average-case running time (e.g., gap heuristic in push-relabel)
• Parallelization opportunities exist for certain algorithms
• Memory usage becomes critical for very large networks

Comparison of algorithms

• Edmonds-Karp performs well for sparse graphs with small capacities
• Push-relabel often outperforms augmenting path methods on dense graphs
• Dinic's algorithm excels on unit capacity networks (bipartite matching)
• Hybrid approaches combine strengths of multiple algorithms

Extensions and variations

• Expands the scope of maximum flow problems to handle more complex scenarios
• Demonstrates how basic flow concepts generalize to solve broader optimization challenges
• Connects maximum flow to other areas of Combinatorial Optimization

Minimum cost flow problem

• Incorporates edge costs in addition to capacities
• Seeks to minimize total cost while satisfying flow demands
• Solved using techniques like successive shortest path or cycle canceling
• Applications include transportation and logistics optimization

Multi-commodity flow

• Extends flow problem to multiple commodities with separate sources and sinks
• Commodities compete for shared edge capacities
• Generally NP-hard, but approximation algorithms exist
• Models complex network routing scenarios (internet traffic)

Maximum flow with vertex capacities

• Adds capacity constraints to nodes in addition to edges
• Can be transformed to standard maximum flow by node splitting
• Useful for modeling problems with processing limitations at network points
• Applications include task scheduling with resource constraints

Duality and max-flow min-cut theorem

• Establishes fundamental relationship between maximum flow and minimum cut
• Connects flow problems to linear programming duality
• Provides powerful theoretical tools for analyzing network flow problems

Theorem statement and proof

• Maximum flow value equals capacity of minimum s-t cut in any flow network
• Proof uses augmenting path method and properties of residual graphs
• Shows equivalence between primal (max flow) and dual (min cut) problems
• Demonstrates strong duality in network flow linear programs

Implications for network design

• Identifies bottlenecks in network capacity (minimum cut)
• Guides network expansion decisions to increase overall flow
• Provides certificates of optimality for maximum flow solutions
• Enables efficient algorithms for related problems (global min cut)