Chapter 7 - Network Flow

Summary & Motivations: Section 7.1 is The Maximum-Flow Problem and the Ford-Fulkerson Algorithm. This subsection addresses network models, and the key pieces for any such problem are capacities on edges, a source node, a sink node, and the traffic that flows on the network. For simplicity, we assume the capacities are integers. While defining flow, we assert two conditions: the capacity condition and the conservation condition. The capacity condition says that every edge has a flow between 0 and its capacity; the conservation condition says that for each node other than the source and the sink, the flows going into the node equal the flows going out of the node. We also say that the value of a flow is the flow coming out of the source. Given such a flow network, we want to find a maximum flow.

About the Algorithms: We see that dynamic and greedy approaches to this problem do not give the optimal solution. The key insight to the algorithm we'll develop is that “we can push forward on edges with leftover capacity, and we can push backward on edges that are already carrying flow, to divert it in a different direction” (p 341). To characterize this setup, we create a residual graph. This residual graph has all the same nodes as G, but the original edges map to leftover capacity, and there are new edges in the reverse direction to represent the flow that we can undo. Before we get to the Max-Flow algorithm, we need a mini-algorithm, augment(f,P), which takes the flow in G and an s-t path P, finds the bottleneck (minimum residual capacity) in P, pushes that amount of flow through P by subtracting flow if there is a residual or reversing flow if not, and returns the augmented flow. The runtime of the augment algorithm is O(m), where m is the number of edges in G. This is what we need in order to push flow back and forth, so we can move on to the real algorithm, Max-Flow. This is the Ford-Fulkerson Algorithm, and here are its specifics: we set all edge flows to 0 initially. Then, while there is an s-t path in the residual graph G_f, we let P be a simple s-t path in G_f, let f' = augment(f,P), update f to f', and update G_f to G_{f'}. The runtime for this algorithm is O(Cm) where C is the maximum possible flow if all edges out of the source are saturated. Upon each iteration, the flow value strictly increases until the Max-Flow is found.

My Questions: How exactly are the lines “Let b = bottleneck(P,f)” in augment and “Let P be a simple s-t path in G_f” in Max-Flow implemented?

Second Time Around: The process for reversing flow made more sense after reading.

Note to Self: Sometimes you have to add to a data structure in order to solve a problem, as is the case here when we create the residual graph.

Readability: 7 - not bad. Even the sums were digestible.

Summary: Section 7.2 is Maximum Flows and Minimum Cuts in a Network. This subsection is concerned with further analyzing the Ford-Fulkerson algorithm. Recall that in section 7.1 we upper-bounded the maximum s-t flow as the sum of all edges out of s. We expand that idea and define an s-t cut to be “a partition (A,B) of the vertex set V, so that s is in A and t is in B. The capacity of a cut (A,B), which we will denote c(A,B), is simply the sum of the capacities of all edges out of A” (p 346). In the cut we originally mentioned, A consists of only s and B consists of the rest of the nodes in V. Armed with this definition, we know that we could have also defined the value of a flow as the sum of all edges going into the sink. Further, we conclude that the value of the flow is less than or equal to the capacity of an A,B cut of G. This means that “the value of every flow is upper-bounded by the capacity of every cut” (p 348). We take these notions a step further and say that the maximum flow corresponds to a minimum cut. This observation implies that we can extend the Ford-Fulkerson algorithm to give the minimum s-t cut (A*, B*), and we can do so in O(m) time.

My Questions: The page about integer vs real numbers was difficult to read. Are we ok with non-integer values, or not?

Second Time Around: The idea of a minimum cut makes more sense after reading.

Note to Self: Cuts in graphs have returned. You cannot escape them. (I don't like cuts.)

Readability: 6 - it was smooth sailing until the page about loosening the constraint that values are integers, or not.

Summary & Motivations: Section 7.5 is A First Application: The Bipartite Matching Problem. This subsection begins the discussion on applications of maximum flows and minimum cuts in graphs. The application for this subsection is the Bipartite Matching Problem. Recall that “a matching M in G is a subset of the edges M subset E such that each node appears in at most one edge in M” (p 368). This problem involves finding a matching in G that is as large as possible. We want an algorithm to get the value of the maximum matching and to recover that matching.

About the Algorithms: All we must do to get what we want is add to the Ford-Fulkerson algorithm. We start with the graph G in an instance of the Bipartite Matching Problem, add the source, add edges from the source to all nodes in X, add the sink, and add edges to the sink from all edges in Y. After some proofs, we conclude that “the size of the maximum matching in G is equal to the value of the maximum flow in G'; and the edges in such a matching in G are the edges that carry flow from X to Y in G' ” (p 369). The runtime for this algorithm is O(mn), where n is the number of nodes in X/Y. The subsection closes with a discussion on graphs that have no perfect matching.

My Questions: What again is Gamma(A)?

Second Time Around: Technically, this was the “first time around,” since we did not have class 4/2, so I cannot say that anything made sense the second time I saw it.

Note to Self: This is another example of an old problem seeing new light (Bipartite Matching).

Readability: 6 - Because the extension part was really hard to follow.

Summary & Motivations: Section 7.7 is Extensions to the Maximum-Flow Problem. This subsection deals with extensions to the Max-Flow problem, as the title suggests. This sentence sums up the power of the Max-Flow problem pretty well: “The power of the Maximum-Flow Problem lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph” (p 379). We explore two related problems here: Circulations with Demands, first without and then with Lower Bounds. Here we allow more than one source and more than one sink. Now instead of deciding which source or sink to use, we'll image that sources have supplies and sinks have demands, of flow. We have the same capacity condition for this problem, but there is no conservation condition anymore. It is more or less replaced by the demand condition: for each node in V, the flow into v minus the flow out of v is equal to v's demand. Further, this problem is no longer about maximization. Rather, it's about feasibility. We want to know if it's possible to satisfy all demands. The only difference between no lower bounds and having lower bounds is that when there are lower bounds on the edges it means that the minimum flow for that edge is its lower bound, not zero.

About the Algorithms: We solve the problem that has no lower bound by adding a “super source” that supplies everything in S and a “super sink” that siphons from everything in T. Then the problem reduces to the Max-Flow algorithm, and the runtime is O(Cm). We solve the problem with lower bounds by reducing it to a problem with no lower bounds. We simply push flow down edges at a value equal to their lower bound and adjust the upper bound on that edge and the demands at its two ends accordingly.

My Questions: What examples are there for when lower bounds would occur? The book didn't give any.

Second Time Around: Technically, this was the “first time around,” since we did not have class 4/2, so I cannot say that anything made sense the second time I saw it.

Note to Self: Figure 7.14 reminds me of things we did in CSCI 313.

Readability: 8 - pretty straightforward.