Maximum Flow and Matching¶
We became familiar with the maximum flow problem in the previous chapter. Here, we will learn about another application of this problem: solving matching problems and their generalizations.
Solving the Maximum Matching Problem in Bipartite Graphs¶
This problem can be solved using the maximum flow problem. To do this, add two nodes—a source and a sink—to the bipartite graph. Connect the source node to all nodes in the upper partition with edges of capacity one, and connect all nodes in the lower partition to the sink node with edges of weight 1. For each edge in the original bipartite graph, draw an edge with weight one from the upper node to the lower node (as shown in the figure).
In this transformed graph, the maximum matching corresponds to the maximum flow.
Maximum Weight Matching¶
In this problem, each edge has a value, and the value of a matching is equal to the sum of the values of its edges. Various problems can be posed for weighted matching, such as matching with the maximum value, maximum size matching with the maximum value, or matching with a specific size and maximum value. These problems can be solved using a generalization of the maximum flow problem, which we will examine below. It is advisable that while reading, you try to think about this problem yourself and attempt to solve it before reaching the solution section.
Flow with Minimum Cost¶
In this problem, the goal is to find a flow that has the minimum cost. The cost of each flow is equal to the sum of the flow passing through each edge multiplied by the cost of that edge, over all edges. We want to obtain the minimum cost for all integer flow values (from 0 to the maximum flow).
Solution¶
We use a method similar to the Ford-Fulkerson method learned in the previous chapter, with the difference that instead of choosing an arbitrary path, we select the path with the least cost and then pass one unit of flow through it. We repeat this process until no more flow can be passed. At each step, the obtained cost represents the minimum possible cost for that amount of flow. According to the correctness of Ford's algorithm, this algorithm achieves the solution up to the maximum flow.
Proof of Optimality¶
Similar to the proof of correctness of Ford's algorithm, it can be shown that at each stage, if f is the target flow value and c is its cost, and the shortest path from the source to the destination is x, then in the constructed graph, if f-1 is the target flow value, the minimum cost with which this amount of flow can be transmitted is c-x.
Complexity Analysis¶
To obtain the shortest path, the SPFA algorithm can be used (since there are negative edges, Dijkstra's algorithm cannot be used), which has a time complexity of \(O(E)\). Therefore, the total time complexity is \(O(fE)\).
Maximum Weight Matching Solution¶
We construct a graph similar to the one above with this difference: we set source and destination edges with infinite capacity, and middle edges with capacity one while assigning their cost equal to the edge's weight. Then using the minimum cost flow algorithm, we can solve all the aforementioned problems.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
