2.5 Maximum flow problems

Maximum flow problems optimize network capacity utilization in Combinatorial Optimization. They determine the maximum amount of flow that can pass through a network from source to sink, balancing distribution across edges while respecting capacity constraints.

The Ford-Fulkerson algorithm iteratively improves flow by finding augmenting paths until reaching maximum flow. Edmonds-Karp and Dinic's algorithms offer polynomial-time solutions, while push-relabel methods provide an alternative approach. These techniques have diverse applications in network analysis and optimization.

Definition of maximum flow

• Maximum flow problems optimize network capacity utilization in Combinatorial Optimization
• Determines the maximum amount of flow that can pass through a network from source to sink
• Balances flow distribution across edges while respecting capacity constraints

Network flow terminology

• Directed graph G = (V, E) represents the network structure
• Source node s initiates flow into the network
• Sink node t receives flow from the network
• Edges (u, v) ∈ E have associated capacities c(u, v)
• Flow f(u, v) denotes the amount of flow on edge (u, v)

Capacity constraints

• Flow on each edge must not exceed its capacity: $0 ≤ f(u, v) ≤ c(u, v)$
• Ensures network limitations are respected
• Prevents overloading of individual edges or nodes
• Capacity constraints apply to all edges in the network

Conservation of flow

• Total incoming flow equals total outgoing flow for all nodes except source and sink
• Mathematically expressed as: $\sum_{(u,v) \in E} f(u,v) - \sum_{(v,u) \in E} f(v,u) = 0$ for all v ∈ V \ {s, t}
• Ensures flow is neither created nor destroyed within the network
• Maintains balance and consistency of flow throughout the system

Ford-Fulkerson algorithm

• Iterative approach to solving maximum flow problems in Combinatorial Optimization
• Incrementally improves flow by finding augmenting paths
• Continues until no more augmenting paths exist, reaching the maximum flow

Residual networks

• Represent remaining capacity in the network after each iteration
• Include forward edges with residual capacity c(u,v) - f(u,v)
• Incorporate backward edges with capacity equal to current flow f(u,v)
• Allow for flow cancellation and rerouting during algorithm execution

Augmenting paths

• Paths from source to sink in the residual network with available capacity
• Increase flow along the path by the minimum residual capacity
• Update residual network after each augmentation
• Can be found using depth-first search or breadth-first search

Termination conditions

• Algorithm terminates when no more augmenting paths exist
• Indicates maximum flow has been achieved
• Convergence guaranteed for integer capacities
• May not terminate for irrational capacities (rare in practice)

Edmonds-Karp algorithm

• Specific implementation of Ford-Fulkerson algorithm in Combinatorial Optimization
• Guarantees polynomial time complexity for maximum flow problems
• Uses breadth-first search to find augmenting paths efficiently

Breadth-first search implementation

• Finds shortest augmenting paths in terms of number of edges
• Explores nodes in order of their distance from the source
• Maintains a queue of nodes to visit during the search process
• Ensures paths with fewer edges are considered before longer ones

Time complexity analysis

• Overall time complexity: O(VE^2)
• V represents the number of vertices in the network
• E represents the number of edges in the network
• Significant improvement over generic Ford-Fulkerson implementation

Comparison with Ford-Fulkerson

• Edmonds-Karp guarantees termination for all input graphs
• Provides better worst-case time complexity than basic Ford-Fulkerson
• Easier to implement and analyze due to systematic path selection
• May require more memory due to breadth-first search queue management

Max-flow min-cut theorem

• Fundamental result in network flow theory and Combinatorial Optimization
• Establishes relationship between maximum flow and minimum cut in a network
• Provides theoretical basis for many flow algorithms and applications

Statement of theorem

• Maximum flow value equals the capacity of the minimum cut in a network
• Minimum cut separates source and sink with minimum total capacity
• Mathematically expressed as: max_flow(G, s, t) = min_cut(G, s, t)
• Implies that flow is limited by the "bottleneck" in the network

Proof outline

• Weak duality: max flow ≤ min cut (always true)
• Strong duality: max flow ≥ min cut (proved by contradiction)
• Augmenting path algorithm terminates at max flow
• Residual graph at termination defines a minimum cut

Applications in optimization

• Network reliability analysis (identifying critical edges)
• Image segmentation in computer vision
• Bipartite matching problems
• Maximum closure problems in data mining

Dinic's algorithm

• Advanced maximum flow algorithm in Combinatorial Optimization
• Improves upon Edmonds-Karp by using level graphs and blocking flows
• Achieves better time complexity for certain network structures

Blocking flows

• Flows that saturate at least one edge on every path from source to sink
• Computed iteratively on level graphs
• Ensure significant progress in each phase of the algorithm
• Can be found using depth-first search or multiple shortest path computations

Level graphs

• Directed acyclic graphs representing shortest paths from source to sink
• Constructed using breadth-first search on the residual network
• Edges connect vertices with consecutive level numbers
• Simplify the process of finding augmenting paths

Complexity improvements

• Overall time complexity: O(V^2E) for general networks
• Improves to O(VE log V) for unit capacity networks
• Further improvements possible for specific graph structures (bipartite graphs)
• Efficient in practice due to quick termination in many real-world scenarios

Push-relabel algorithm

• Alternative approach to maximum flow problems in Combinatorial Optimization
• Maintains a preflow instead of a valid flow during execution
• Locally pushes excess flow and relabels vertices to create valid paths

Generic push-relabel method

• Initializes preflow by saturating all edges leaving the source
• Maintains height function h(v) for each vertex v
• Iteratively applies push and relabel operations to move flow towards sink
• Terminates when no more operations are possible, yielding maximum flow

Discharge operation

• Pushes excess flow from a vertex to its neighbors
• Requires the receiving vertex to have lower height
• Moves flow along edges with available capacity
• Creates new excesses at receiving vertices

Relabel operation

• Increases the height of a vertex when no valid push is possible
• Ensures progress by creating new opportunities for push operations
• Maintains invariant that h(u) ≤ h(v) + 1 for every edge (u, v)
• Critical for algorithm correctness and termination

Applications of maximum flow

• Maximum flow algorithms solve diverse problems in Combinatorial Optimization
• Demonstrate versatility of network flow techniques
• Often serve as building blocks for more complex optimization problems

Bipartite matching

• Models assignment problems between two disjoint sets
• Constructs flow network with source connected to one set, sink to the other
• Maximum flow corresponds to maximum cardinality matching
• Applications include job assignments and resource allocation

Image segmentation

• Separates foreground from background in digital images
• Constructs graph where pixels are vertices and edges represent similarity
• Minimum cut provides optimal segmentation boundary
• Used in medical imaging, object recognition, and video processing

Network capacity planning

• Analyzes and optimizes transportation or communication networks
• Identifies bottlenecks and potential improvements in network infrastructure
• Helps determine optimal routing strategies for data or goods
• Supports decision-making in network expansion and upgrade projects

Variations of maximum flow

• Extensions of basic maximum flow problem in Combinatorial Optimization
• Address more complex scenarios and constraints
• Require specialized algorithms and techniques for efficient solutions

Minimum cost flow

• Finds maximum flow with minimum total cost
• Assigns costs to edges in addition to capacities
• Uses techniques like successive shortest path or cycle canceling
• Applications include transportation logistics and supply chain optimization

Multi-commodity flow

• Considers multiple types of flow simultaneously in a network
• Each commodity has its own source-sink pairs and flow requirements
• More challenging than single-commodity flow problems
• Solved using linear programming or approximation algorithms

Maximum flow over time

• Incorporates time dimension into flow problems
• Edges have both capacities and transit times
• Optimizes flow rate and timing of flow units
• Applications include evacuation planning and dynamic network routing

Duality in maximum flow

• Explores relationship between primal and dual problems in Combinatorial Optimization
• Provides alternative perspective on maximum flow problems
• Facilitates development of efficient algorithms and theoretical insights

Linear programming formulation

• Expresses maximum flow as a linear program
• Objective: Maximize total flow from source to sink
• Constraints: Capacity limits and flow conservation
• Variables represent flow on each edge

Dual problem interpretation

• Corresponds to minimum cut problem
• Variables represent cut values for each vertex
• Objective: Minimize total capacity of cut edges
• Constraints ensure valid s-t cut

Complementary slackness

• Relates optimal solutions of primal and dual problems
• Edge saturated in primal ⇔ Tight constraint in dual
• Provides optimality conditions for maximum flow
• Useful for developing and analyzing algorithms

Computational complexity

• Analyzes efficiency of maximum flow algorithms in Combinatorial Optimization
• Considers time and space requirements for different problem instances
• Guides algorithm selection and implementation choices

Polynomial-time algorithms

• Solve maximum flow problems in time polynomial in input size
• Include Edmonds-Karp, Dinic's, and Push-relabel algorithms
• Guarantee efficient solutions for large-scale networks
• Typically have complexity of form O(V^c E^d) for some constants c, d

Strongly polynomial algorithms

• Runtime independent of numeric values in the input
• Depend only on the number of vertices and edges
• Examples include some variants of push-relabel algorithm
• Important for networks with large capacity values

Approximation algorithms

• Trade exact optimality for improved running time
• Provide solutions within a guaranteed factor of optimal
• Useful for very large networks or time-sensitive applications
• Often based on randomized or sampling techniques

Advanced techniques

• Sophisticated methods for solving complex flow problems in Combinatorial Optimization
• Extend basic maximum flow algorithms to handle specialized scenarios
• Often combine multiple algorithmic ideas for improved performance

Parametric maximum flow

• Solves series of related maximum flow problems
• Efficiently updates flow as network parameters change
• Applications include sensitivity analysis and optimization over time
• Algorithms exploit similarity between consecutive problem instances

Gomory-Hu trees

• Compact representation of all minimum s-t cuts in a network
• Allows quick queries for maximum flow between any two vertices
• Constructed using n-1 maximum flow computations
• Useful for network analysis and cut-based clustering

Preflow push algorithms

• Generalization of push-relabel method
• Maintain preflow satisfying relaxed flow conservation
• Include variants like FIFO push-relabel and highest-label push-relabel
• Often perform well in practice due to good locality of memory access