Chapter 7: Network Flow

This section discusses modeling networks involving capacities, source nodes, sink nodes, and the direction of transmission. This transmission is considered flow, from the source nodes through the edges to the sink nodes. A flow network must have a non-negative capacity at each edge, a source node (s), and a sink node (t). All other nodes are considered internal nodes. A flow must have two conditions. First, it can only carry up to and including as much capacity as it has. Second, the flow out of the node must equal the flow into the node. A goal here is to find the flow with the maximum value. We do so by analyzing various “cuts” of the graph. The minimum cut is where the maximum flow value equals the minimum capacity.

Finding a maximum flow using a greedy algorithm won't necessarily work. Instead, we want to find our flow by pushing forward on edges with leftover capacity and backward on edges already carrying flow. This becomes a residual graph, a way to perform these operations. We can then augment paths in the residual graph to find the maximum capacity flow. This is done by identifying the bottleneck in each push of flow.

This methodology is known as the Ford-Fulkerson Algorithm. Through analyzing the algorithm, we can determine that it runs in O(mC) time where m is the number of edges in the graph and C is the sum of the capacities of the flow out of an edge.

This section discusses an analysis of the Ford-Fulkerson Algorithm. This analysis is performed in terms of flows and cuts. We can begin this analysis by dividing the nodes of the graph into two sets, A and B. The division places an upper bound on the maximum possible flow, since all flow crosses from A to B at some location. Cuts gives us a natural upper bound on the values of flows. We can actually measure the flow value by keeping track of the amount of flow sent across a cut. We can probe this through manipulation of sums.

We can see that the value of every flow is upper-bounded by the capacity of every cut. The Ford-Fulkerson Algorithm ends when the flow has no s-t patch in the residual graph, which proves its maximality. With a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time.

Overall this section was a little bit difficult to read. It reminded me of what we had done in class, but I still feel as if I need another review of this topic. Out of 10, I would score this section a 5 for readability.

We can now use the concept of maximizing flows to solve the bipartite matching problem. First, we create a flow network from the bipartite graph. We then find the maximum s-t flow of this network. If there is a matching of k edges, and the flow among those edges is f, one can see that the capacity and conservation conditions are met and f is an s-t flow with value k.

Considering a set M' where edges of the form (x,y) have a flow value of 1, M' contains k edges, each node in X is the trail of at most one edge in M', and each node in Y is the head of at most one edge in M'. This allows us to see that the maximum matching in G is equal to the value of the maximum flow in G', which carries from from X to Y in G'. We can perform this matching in O(mn) time.

Because not all bipartite graphs have perfect matchings, it is easy to wonder how to handle this situation. We can determine whether or not a graph, G, has a perfect matching by checking if the maximum flow in G' has a value of at least n. According to the Max-Flow Min-Cut Theorem, there will be an s-t cut of capacity less than n if the maximum-flow of G' is also less than n.

This section somewhat reminded me of discussing the pigeon hole principle. If we have too many x nodes to match to y nodes, then there must be an x node that is not matched and therefore a perfect matching does not exist. We can apply Hall's Theorem to this situation to find the solution in O(nm) time.

There are numerous extensions to the Maximum-Flow Problem involving search components that can be solved in polynomial time. One of these extensions is Circulations with Demands. If we have multiple sources and sinks, it becomes complicated to determine where to look to solve a maximization problem. Instead of maximizing flow values, here we would look at fixed supply values for sources and fixed demand values for sinks. We still want to send flow from the sources to the demands. We now associate each node with a demand. A circulation with demands is a function of f that satisfies capacity and demand conditions.

We can design an algorithm for circulation and demands to find a maximum s-t flow. However, we can only find a feasible circulation with demands in G if and only if the maximum s-t flow in G' has a value of D. We can enforce this by placing lower bounds on edges and upper bounds on edge capacities.