This chapter focuses on algorithms that expand on the Bipartite Matching problem. It creates a polynomial-time algorithm for a general problem, which is the Maximum-Flow Problem, and shows that this is an efficient algorithm for the Bipartite Matching as well.
In this, we want to find the flow that gives us the maximum possible value. The maximum value will equal the bottleneck rate, or minimum cut, which is the minimum capacity of the path. We push flow over the paths at the maximum amount of value that we can, going back and forth until we reach the maximum-flow for the path over all of the nodes.
This will terminate with no value greater than C, which is the sum of flow. Its runtime will be O(m) because if each node n has at least one edge, we will iterate over all of them, leaving us with this runtime. This section was overly convoluted for the problem at hand, so I give it a 2/10.
This just went deeper into the Ford-Fulkerson Algorithm.
First, it started with analyzing the “flows and cuts.” Simplified, it said that if we have a cut (A, B), then we can determine that for any flow between two nodes, v(f) = fout(A) - fin(A), which is the maximum flow.
The next part was about analyzing the max-flow equals min-cut algorithm. The gist was that if we have “f that is an s-t-flow, where no s-t path is in our residual graph, then there is a cut (A*, B*) in the graph for which v(f) = c(A*, B*).” This tells us that f has a max value of flow in our graph and that (A*, B*) is the minimum capacity of any cut in the graph.
In this section, we looked back at the Bipartite Matching Problem. In order to find the maximum matching in the graph more efficiently, we can use the Ford-Fulkerson Algorithm. This allows us to find it in O(mn) time, which is because in the Bipartite Matching Problem, C = n, so we see this from the previous bound we had found for the Ford-Fulkerson Alg. of O(mC).
If we have a graph with two distinct sides where the sides are equal, then this graph either has a perfect matching or there will be a subset where the adjacent set is less than the subset. Whether it is a perfect matching or the described subset, it can be found in O(mn) time.
This section was interesting enough, but again the examples and talking through everything was drawn out and over complicated it seemed a lot, so 5/10.
This section focused on how the maximum-flow problem can be put to use. The first was with circulations, where we have a set of sources and a set of sinks. Here, each node has a fixed value (supply for source, demand for sink). In summary, there can be a circulation with a set of demands in a graph if and only if the flow has a value of D, which is the capacity of the cut of our source nodes.
The next problem was the same as above, but introduced lower bounds. In this, it works the same way, but the catch is that the flow value must be at least a certain value for the flow to go through. In this, we can only have a feasible circulation if there is a feasible circulation in an identical graph that excludes the lower bounds.
Overall, this section was interesting, as it applied what we had learned in the previous sections. It was also shorter and not as convoluted, as well as the last one of these, so I'd give it a 7/10.