Chapter 7: Network Flow

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) = f^out(A) - fⁱⁿ(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.