🧮Combinatorial Optimization Unit 5 – Network Flows and Matchings

Key Concepts and Definitions

• Network flow models the movement of commodities through a network with capacity constraints on edges
• A flow network consists of a directed graph $G = (V, E)$, a source node $s$, a sink node $t$, and a capacity function $c: E \rightarrow \mathbb{R}^+$
• The value of a flow $f$ is the total amount of flow leaving the source node $s$ or entering the sink node $t$, denoted as $|f|$
• The capacity constraint ensures that the flow along any edge does not exceed its capacity, i.e., $0 \leq f(e) \leq c(e)$ for all $e \in E$
• The conservation of flow property states that the total flow entering a node (except $s$ and $t$) must equal the total flow leaving the node
• A cut in a flow network is a partition of the nodes 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 edges from nodes in $S$ to nodes in $T$, i.e., $c(S, T) = \sum_{u \in S, v \in T} c(u, v)$
• The max-flow min-cut theorem states that the maximum value of a flow in a network equals the minimum capacity of a cut

Network Flow Fundamentals

• Network flow problems involve finding a feasible flow that optimizes a certain objective (maximum flow or minimum cost)
• The residual network $G_f$ of a flow network $G$ with respect to a flow $f$ represents the remaining capacity available in the network
• In the residual network, each edge $e = (u, v)$ has a residual capacity $c_f(e) = c(e) - f(e)$
• An augmenting path is a path from the source $s$ to the sink $t$ in the residual network $G_f$
• Augmenting a flow along an augmenting path increases the flow value by the minimum residual capacity along the path
• The Ford-Fulkerson algorithm iteratively finds augmenting paths and updates the flow until no more augmenting paths exist
  • The algorithm terminates when the maximum flow is reached, which equals the minimum cut capacity by the max-flow min-cut theorem
• The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson algorithm that uses breadth-first search to find the shortest augmenting path in each iteration, ensuring a polynomial time complexity of $O(|V| \cdot |E|^2)$

Maximum Flow Problem

• The maximum flow problem aims to find a flow of maximum value from the source $s$ to the sink $t$ in a flow network
• The maximum flow represents the maximum amount of a commodity that can be transported through the network while respecting the capacity constraints
• The Ford-Fulkerson and Edmonds-Karp algorithms can be used to solve the maximum flow problem
• The Dinic's algorithm is another efficient algorithm for the maximum flow problem with a time complexity of $O(|V|^2 \cdot |E|)$
  • It uses the concept of level graphs and blocking flows to find augmenting paths and update the flow
• The push-relabel algorithm is an alternative approach to solve the maximum flow problem with a time complexity of $O(|V|^2 \cdot |E|)$
  • It maintains a height function on the nodes and performs push and relabel operations to update the flow
• Applications of the maximum flow problem include network connectivity, bipartite matching, and resource allocation

Minimum Cost Flow Problem

• The minimum cost flow problem aims to find a flow of minimum total cost that satisfies the demand and supply constraints at each node
• In addition to the capacity function, each edge $e$ has an associated cost $a(e)$ that represents the cost per unit flow along the edge
• The objective is to minimize the total cost of the flow, given by $\sum_{e \in E} a(e) \cdot f(e)$, while satisfying the flow conservation and capacity constraints
• The supply and demand constraints specify the net flow entering or leaving each node, with positive values for supply nodes and negative values for demand nodes
• The minimum cost flow problem can be solved using algorithms such as the cycle-canceling algorithm and the successive shortest path algorithm
  • The cycle-canceling algorithm starts with a feasible flow and iteratively finds and cancels negative cost cycles in the residual network until an optimal flow is reached
  • The successive shortest path algorithm iteratively finds the shortest path from a supply node to a demand node in the residual network and augments the flow along this path until all demands are satisfied
• Applications of the minimum cost flow problem include transportation, resource allocation, and network design optimization

Matching Theory Basics

• Matching theory deals with the problem of assigning elements of one set to elements of another set based on preferences or constraints
• A matching in a graph is a subset of edges such that no two edges share a common vertex
• A maximum matching is a matching with the largest possible number of edges
• A perfect matching is a matching that covers all vertices of the graph, i.e., each vertex is incident to exactly one matched edge
• In a bipartite graph, the vertices can be partitioned into two disjoint sets $U$ and $V$, and all edges connect a vertex in $U$ to a vertex in $V$
• A bipartite matching is a matching in a bipartite graph, where each matched edge connects a vertex from $U$ to a vertex from $V$
• The maximum bipartite matching problem aims to find a matching of maximum cardinality in a bipartite graph
• Stable marriage problem is a classic matching problem where the goal is to find a stable matching between two sets of elements (men and women) based on their preferences
  • A matching is stable if there is no pair of elements who would prefer each other over their current partners

Bipartite Matching Algorithms

• The Hungarian algorithm, also known as the Kuhn-Munkres algorithm, is a polynomial-time algorithm for finding a maximum-weight perfect matching in a bipartite graph
  • It uses the concept of augmenting paths and alternating trees to find and update the matching
• The Hopcroft-Karp algorithm is an efficient algorithm for finding a maximum cardinality matching in a bipartite graph with a time complexity of $O(\sqrt{|V|} \cdot |E|)$
  • It uses the concept of augmenting paths and alternating level graphs to find and update the matching
• The Ford-Fulkerson algorithm can be adapted to find a maximum matching in a bipartite graph by constructing a flow network
  • The bipartite graph is transformed into a flow network by adding a source and a sink, connecting the source to all vertices in $U$, connecting all vertices in $V$ to the sink, and assigning unit capacities to all edges
  • The maximum flow in the constructed network corresponds to a maximum matching in the original bipartite graph
• The Gale-Shapley algorithm solves the stable marriage problem in polynomial time by iteratively proposing and rejecting pairs based on preferences
  • It guarantees a stable matching and has a time complexity of $O(|V|^2)$

Applications in Real-world Scenarios

• Network flow and matching algorithms have numerous real-world applications across various domains
• In transportation networks, maximum flow algorithms can be used to determine the maximum capacity of a road network or the maximum number of vehicles that can be routed between two locations
• Minimum cost flow algorithms can optimize the distribution of goods in supply chain networks, minimizing transportation costs while meeting demand constraints
• Bipartite matching algorithms can be applied in job assignment problems, where workers need to be matched to tasks based on their skills and preferences
• In resource allocation, network flow algorithms can help in efficiently allocating limited resources (bandwidth, processing power) among competing tasks or users
• Matching algorithms are used in online advertising to match advertisers with available ad slots based on targeting criteria and budget constraints
• In social networks, matching algorithms can suggest potential friends or connections based on common interests or compatibility factors
• Stable marriage algorithms are used in college admissions processes to match students to colleges based on their preferences and college rankings

Advanced Topics and Extensions

• Multi-commodity flow problems involve the simultaneous flow of multiple commodities through a network, each with its own source and sink nodes and demand requirements
• The maximum multicommodity flow problem aims to maximize the total flow of all commodities while satisfying capacity constraints and commodity-specific demands
• The minimum cost multicommodity flow problem seeks to minimize the total cost of routing multiple commodities through a network while meeting demand and capacity constraints
• Network design problems involve making decisions about the structure and capacities of a network to optimize performance metrics such as throughput, reliability, or cost
• Stochastic network flow problems consider uncertainties in the network parameters (capacities, costs, demands) and aim to find robust solutions that perform well under various scenarios
• Online matching problems require making irrevocable matching decisions as vertices arrive one by one, without knowledge of future arrivals
• Matching with preferences involves finding matchings that satisfy individual preferences or rankings, such as in the stable marriage problem or the hospitals/residents problem
• Approximation algorithms provide suboptimal but provably good solutions for computationally hard matching and flow problems, often with guaranteed approximation ratios