📊Graph Theory Unit 9 – Network Flows and Cuts

Key Concepts and Definitions

• Network flow models the movement of a commodity through a network with capacity constraints on the edges
• A flow network is a directed graph $G = (V, E)$ with a source vertex $s$, a sink vertex $t$, and a capacity function $c: E \rightarrow \mathbb{R}^+$
  • The capacity function $c(u, v)$ represents the maximum amount of flow that can pass through an edge $(u, v)$
• A flow is a function $f: E \rightarrow \mathbb{R}^+$ that satisfies the capacity constraint $f(u, v) \leq c(u, v)$ for all edges $(u, v) \in E$
  • The flow also satisfies the conservation of flow property: for all vertices $v \in V \setminus \{s, t\}$, the sum of the flow entering $v$ equals the sum of the flow leaving $v$
• The value of a flow $|f|$ is the total amount of flow passing from the source to the sink
• A maximum flow is a flow of maximum value in a given network
• A cut in a flow network is a partition of the vertices into two disjoint subsets $S$ and $T$, where $s \in S$ and $t \in T$
  • The capacity of a cut $(S, T)$ is the sum of the capacities of the edges from $S$ to $T$

Network Flow Basics

• The goal of network flow problems is to find the maximum amount of flow that can be sent from the source to the sink while respecting the capacity constraints
• The flow conservation property ensures that the amount of flow entering a vertex equals the amount of flow leaving the vertex, except for the source and sink
• The residual network $G_f$ of a flow network $G$ with respect to a flow $f$ is a directed graph that represents the remaining capacity in the network
  • The residual capacity $c_f(u, v)$ of an edge $(u, v)$ in the residual network is the original capacity minus the flow: $c_f(u, v) = c(u, v) - f(u, v)$
  • If the flow along an edge is positive, a backward edge with the same flow value is added to the residual network
• An augmenting path is a path from the source to the sink in the residual network along which more flow can be sent
• The Ford-Fulkerson algorithm finds a maximum flow by repeatedly finding augmenting paths and updating the flow until no more augmenting paths exist

Types of Network Flow Problems

• Maximum flow problem finds the maximum amount of flow that can be sent from the source to the sink
• Minimum cost flow problem assigns costs to the edges and seeks to find a flow of a given value with minimum total cost
• Multi-commodity flow problem involves multiple commodities (flow types) with separate source-sink pairs and shared edge capacities
• Circulation problem is a flow problem without a source or sink, where the goal is to find a feasible flow that satisfies lower and upper bounds on edge flows
• Minimum cut problem aims to find a cut with the minimum capacity among all possible cuts in the network
  • The max-flow min-cut theorem states that the value of the maximum flow equals the capacity of the minimum cut

Flow Algorithms

• Ford-Fulkerson algorithm is a general method for solving the maximum flow problem
  • It repeatedly finds augmenting paths and updates the flow until no more augmenting paths exist
  • The time complexity depends on the choice of augmenting paths (Edmonds-Karp, capacity scaling)
• Edmonds-Karp algorithm is an implementation of Ford-Fulkerson that uses breadth-first search to find the shortest augmenting path
  • It has a time complexity of $O(VE^2)$
• Dinic's algorithm is another maximum flow algorithm that uses level graphs and blocking flows to find augmenting paths efficiently
  • It has a time complexity of $O(V^2E)$
• Push-relabel algorithm maintains a preflow and a labeling function to push excess flow towards the sink
  • It has a time complexity of $O(V^2E)$ or $O(V^3)$ with the highest-label selection rule
• Capacity scaling algorithms (Edmonds-Karp, Orlin) improve the running time by considering augmenting paths with sufficiently large residual capacities
  • They have a time complexity of $O(E^2 \log U)$, where $U$ is the maximum edge capacity

Cuts in Networks

• A cut $(S, T)$ partitions the vertices into two disjoint subsets $S$ and $T$, where $s \in S$ and $t \in T$
• The capacity of a cut is the sum of the capacities of the edges from $S$ to $T$
• A minimum cut is a cut with the minimum capacity among all possible cuts in the network
• The max-flow min-cut theorem establishes a strong relationship between maximum flows and minimum cuts
  • It states that the value of the maximum flow equals the capacity of the minimum cut
• Minimum cuts can be found by computing a maximum flow and identifying the saturated edges from the source side of the cut to the sink side
• The Karger's algorithm is a randomized algorithm for finding a minimum cut in an undirected graph
  • It repeatedly contracts randomly chosen edges until only two vertices remain, representing a cut

Applications of Network Flows

• Transportation networks model the flow of goods or vehicles between locations with capacity constraints on the roads or routes
• Bipartite matching problems can be solved using network flow techniques by constructing a flow network with source and sink nodes
  • Examples include assigning workers to jobs, students to projects, or matching organ donors to recipients
• Image segmentation can be formulated as a minimum cut problem to partition an image into foreground and background regions
• Network reliability and connectivity problems involve finding the maximum flow or minimum cut to determine the robustness of a network
• Scheduling and resource allocation problems can be modeled as network flow problems to optimize the utilization of limited resources over time

Advanced Topics and Extensions

• Multi-source multi-sink flow problems have multiple sources and sinks with specified supply and demand values
• Flow with vertex capacities extends the network flow model to include capacity constraints on the vertices in addition to the edges
• Minimum cost circulation problem seeks a circulation that satisfies lower and upper bounds on edge flows while minimizing the total cost
• Maximum dynamic flow problem considers the flow over time, where the flow takes time to traverse the edges and the goal is to maximize the total flow arriving at the sink by a given time horizon
• Network flow interdiction and network security problems involve identifying critical edges or vertices to disrupt or protect the flow in a network
• Stochastic network flow problems incorporate uncertainty in the network parameters (capacities, costs) and require robust optimization techniques

Problem-Solving Strategies

• Identify the type of network flow problem based on the given constraints and objectives
• Construct the flow network by defining the source, sink, vertices, edges, and capacities
• Choose an appropriate algorithm based on the problem type and network size (Ford-Fulkerson, Edmonds-Karp, Dinic's, push-relabel)
• Implement the algorithm and solve the problem to find the maximum flow or minimum cut
• Analyze the solution and interpret the results in the context of the original problem
• Consider using reductions to transform related problems into network flow problems
  • For example, reduce bipartite matching to maximum flow or minimum cut to maximum flow
• Exploit the problem structure and properties to simplify the solution process
  • For example, use the max-flow min-cut theorem to find minimum cuts by solving maximum flow
• Verify the correctness of the solution by checking the flow conservation property and capacity constraints
• Optimize the implementation by using efficient data structures (adjacency lists, priority queues) and algorithms (breadth-first search, depth-first search)