Chapter 7

• Matching in bipartite graphs can model situations in which objects are being assigned to other objects
  • Nodes in X represent jobs, and the nodes in Y represent machines, and an edge (xi,yj) indicates that machine yj is capable of processing job xi.
• Perfect Matching: a way of assigning each job to a machine that can process it
  • Property that each machine is assigned exactly one job
• One of the oldest problems in combinatorial algorithms: determining the size of the largest matching in a bipartite graph G
  • Network Flow Problems: includes the Bipartite Matching Problem as a special case

The Problem

• Transportation Networks: networks whose edges carry some sort of traffic and whose nodes act as “switches” passing traffic between different edges
  • capacities on the edges
  • source nodes in the graph, which generate traffic
  • sink (or destination) nodes, which can “absorb” traffic as it arrives
  • traffic, which is transmitted across the edges

• Flow Networks
  • traffic = flow
  • associated with each edge e is a capacity, ce
  • single source node s in V
  • single sink node t in V
  • all other nodes besides s and t are internal nodes
  • no edge enters s and no edge leaves t
  • at least one edge incident to each edge
  • all capacities are integers
• Defining Flow
  • s-t flow is a function f that maps each edge e to a nonnegative real number, f
    • Flow must follow two properties:
      • Capacity: for each e in E: we have 0 ⇐ f(e) ⇐ ce
      • Conservation: for each node v other than s and t: sum of the flow value f(e) over all edges entering node v = sum of the flow values over all edges leaving node v

• The Maximum-Flow Problem
  • goal: arrange the traffic for maximum efficiency of the available capacity
    • given a flow network, find a flow network
  • Each “cut” of the graph puts a bound on the maximum possible flow value
    • maximum-flow algorithm here will be intertwined with a proof that the maximum flow value equals the minimum capacity of any such division, called the minimum cut.

Designing the Algorithm

• Suppose we start with zero flow: f(e) = 0 for all e
  • problem is that its value is 0
  • we want to increase the value of f by “pushing” flow along a path from s to t, up to the limits imposed by the edge capacities
    • need a general way of pushing flow from s to t to increase the value of the current flow
  • General: push forward on edges with leftover capacity / push backward on edges that are already carrying flow to divert it in a different direction
    • Residual Graph: provides a systematic way to search for forward-backward operations
• Residual Graph
  • Residual Graph Gf of G with respect to f:
    • The node set of Gf is the same as that of G
    • For each edge e = (u,v) of G on which f(e) < ce, there are ce - f(e) leftover units of capacity: forward edges
    • For each edge e = (u,v) of G on which f(e) > 0, there are f(e) units of flow that we can undo if we want to: edge e' = (v, u) in Gf
      • e' has the same ends as e, but reverse direction: backward edges
• Augmenting Paths in a Residual Graph

• result of augment(f, P) is a new flow f' in G, obtained by increasing and decreasing the flow values on edges of P
  • f' is a flow in G:
    • to prove: need to check the capacity of edges on P, and check that the capacity condition and the conservation condition both hold true.
• Ford-Fulkerson Algorithm:

• Computes an s-t flow in G

Analyzing the Algorithm: Termination and Running Time

• At every intermediate stage of the Ford-Fulkerson Algorithm, the flow values {f(e)} and the residual capacities in Gf are integers
• Use this property to prove the algorithm terminates
  • Show that the flow value strictly increases when we apply an augmentation
    • Let f be a flow in G, and let P be a simple s-t path in Gf. Then we have v(f') = v(f) + bottleneck(P,f); and since bottleneck(P,f)>0, we have v(f') > v(f)
      • Since G has no edges entering s, the edge e must be a forward edge: increase the flow on this edge by bottleneck(P,f): we do not change the flow on any other edge incident to s, so the value of f' exceeds the value of f by bottleneck(P,f)
    • Suppose, as above, that all capacities in the flow network G are integers. Then the Ford-Fulkerson Algorithm terminates in at most C iterations of the While loop.
      • No flow in G can have value greater than C, due to the capcity condition on the edges leaving s. Since it starts with the value 0, and cannot go higher than C, the While loop in the Ford-Fulkerson Algorithm can run for at most C iterations.
    • Suppose, as above that all capacities in the flow network G are integers. Then the Ford-Fulkerson Algorithm can be implemented to run in O(mC) time.
      • Assuption: m>= n/2: O(m+n) is the same as O(m)
      • Procedure augment(f,P) takes time O(n) as the path P has at most n-1 edges
        • given the new flow f', we can build the new residual graph in O(m) time

This section was not too difficult to understand. I think once you understand the ideas behind network flow, it is very easy to understand how they work. It also helped that we covered this in class yesterday, so phrasing that may have been confusing before was actually pretty clear and easy to understand. Some of the proofs were a little hard to understand, but that is pretty normal and I think more practice will help solidify the ideas of this section!

Readability: 7.0 Interesting: 6.5

Analyzing the Algorithm: Flows and Cuts

• Goal: show that the flow that is returned by the Ford-Fulkerson Algorithm has the maximum possible value of any flow in G
• Use the notion o a cut to develop a much more general means of placing upper bounds on the maximum-flow value
• If we divide the nodes into two sets: A and B (s in A, t in B)
  • all the flow must cross from A to B somewhere
• s-t cut is a partition (A,B) of the vertex set V so that s is in A and t is in B
• capacity of a cut (A,B): c(A,B) → sup of the capacities of all edges
• Let f be any s-t flow and (A,B) any s-t cut. Then v(f) = fout(A) - fin(A).
  • by watching the amount of flow f sends across a cut, we can exactly measure the flow value (amount that leaves A - the amount that swirls back into A)
    • Proof: fin(s) = 0, as source s has no entering edges

• Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) = fin(B) -fout(B)
  • value of flow in terms of sink: fin(t), the amount of flow arriving at the sink.
• Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) ⇐ c(A,B)
  • The value of every flow is upper-bounded by the capacity of every cut
    • If we exhibit any s-t cut in G of some value c*, we know that there cannot be an s-t flow in G of value greater than c*.

Analyzing the Algorithm: Max-Flow Equals Min-Cut

• f+ denotes the flow that is returned by the Ford-Fulkerson Algorithm
• want to show that f+ has the maximum possible value of any flow i G
• If f is an s-t flow such that there is no s-t path in the residual graph Gf, then there is an s-t cut (A*,B*) in G for which v(f) = c(A*B*). Consequently, f has the maximm value of any flow in G, and (A*,B*) has the minimum capacity of any s-t cut in G
  • A* denotes the set of all nodes v in G for which there is an s-v path in Gf
  • B* denotes the set of all other nodes: B* = V - A*

• All edges out of A* are saturated with flow
• All edges into A* are completely unused, so:

• The flow f+ returned by the Ford-Fulkerson Algorithm is a maximum flow
• Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time
  • construct the residual graph Gf, perform breadth-first search/depth-first search, define B* = V - A*, return the cut (A*,B*)
• In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut

Further Analysis: Integer-Valued Flows

• If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer
  • Not every maximum flow is integer-valued, only some maximum flow has this property
• Real Numbers as Capacities?
  • allowing capacities to be rational numbers does not make the situation any more general, since we can determine the least common multiple of all capacities, and multiple them all by this value to obtain an equivalent problem with integer capacities.
  • If real numbers are capacities: concern is that the value of our flow keeps increasing, but in increments that become arbitrarily smaller and smaller; no guarantee that the number of iterations of the loop is finite
  • Capacities in any practical application of network flow would be integers or rational numbers
    • The problem of pathological choices for the augmenting paths can manifest itself even with integer capacities.

This section makes a lot of sense, again, because we began our discussion on this chapter in class on Friday. I think most of the ideas are logical, but some take a little longer to understand than others. The idea of having real numbers as capacities is a little confusing for me, especially because of the way that the section leaves off. The section ends by saying that there can be problems with integer capacities, not just with rational number capacities. I'd like to know more about why that is and what the solution to it is.

Readability: 6.5 Interesting: 6.5

Analyzing the Algorithm: Flows and Cuts

The Problem

• Bipartite Graph G = (V,E) is an undirected graph whose node set can be partitioned as V = X union Y, with the property that every edge e in E has one end in X and the other in Y
• Matching M in G is a subset on the edge M in E such that each node appears in at most one edge in M

Designing the Algorithm

• We construct a flow network G'
• Direct all edges in G from X to Y
• Add a node s, and an edge (s,x) from s to each node in X
• add a node t, and an edge (y,t) from each node in Y to t
• Give each edge in G' a capacity of 1
• Compute a maximum s-t flow in the network G'

Analyzing the Algorithm

• Suppose there is a matching in G consisting of k edges
• Then consider the flow f that sends one unit along each path, that is f(e) = 1 for each ege on one of these paths
• Suppose there is a flow f' in G' of value k
• By the integrality theorem for maximum flows, we know there is an integer-valued flow f of value k
• Since all capacities are 1, f(e) is equal to either 0 or 1 for each edge e
• Consider the set M' of edges in the form (x,y) on which the flow value is 1
  • M' contains k edges
  • Each node in X is the tail of at most one edge in M'
  • Each node in Y is the head of at most one edge in M'
• If we view M' as a set of edges in the original bipartite graph G, we get a matching of size k:
  • 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'
• Bounding the Running Time
  • The Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time
    • Consider the matching M consisting of edges in the bipartite graph
      • Let f be the corresponding flow in G'
      • Matching in not maximum, so f is not a maximum s-t flow, and hence there is an augmenting path in the residual graph G'f.
      • All augmenting paths must alternate between edged used backward and forward, as all edges of the graph G' go from X to Y
        • also known as alternating paths in the context of finding a maximum matching
      • Effect of this augmentation is to take the edges used backward out of the matching and replace them with the edges going forward.
        • Because the path goes from s to t, there is one more forward edge than backward edge (size of the matching increases by one)

Extensions: The Structure of Bipartite Graphs with No Perfect Matching

• What if there is not a perfect matching?
• We can decide if the graph G has a perfect matching by checking if the maximum flow in a related graph G' has at least n
  • By the Max-Flow Min-Cut Theorem, there will be an s-t cut of capacity less than n if the maximum-flow value in G' has value less than n
    • a cut with capacity less than n provides a “certificate” of no matching
• If a bipartite graph G = (V,E) with two sides X and Y has a perfect matching, then for all A in X, we must have |Gamma(A)| >= |A|
  • Hall's Theorem
• Assume that the bipartite graph G = (V,E) has two sides X and Y such that |X| = |Y|. Then the graph G either has a perfect matching or there is a subset A in X such that |Gamma(A)| < |A|.
  • A perfect matching or an appropriate subset A can be found in O(mn) time

This section was more dense, so it was not quite as easy to read. I think this section spent a lot of time trying to prove theorems, and as a result, I had to spend more time processing and learning this section. However, on the whole, I think everything this section says made sense to me. I know I'll need some application practice in order to fully comprehend this section.

Readability: 6.0 Interesting: 6.0

• Many problems have a nontrivial combinatorial search component that can be solved in polynomial time

The Problem: Circulations with Demands

• set S of sources generating flow and set T of sinks that can absorb flow
• Consider a problem where sources have fixed supply values and sinks have fixed deman values
• goal: ship flow from nodes with available supply to those with given demands
• Associated with each node v in V is a demand dv
  • If dv > 0, the node v has a demand of dv for flow
  • Node is a sink and it wishes to receive dv units more flow than it sends out
  • If dv < 0, the node v has a supply of -dv; the node is a source and it wishes to send out -dv units more flow than it receives
  • If dv = 0: node v is neither a source nor a sink
    • Assume all capacities and demands are integers
• S: set of all nodes with negative demand
• T: set of all nodes with positive demand
• Circulation with demands {dv} is a function f that assigns a nonnegative real number to each edge and satisfies the following two conditions:
  • Capacity: for each e in E, we have 0 ⇐ f(e) ⇐ ce
  • Demand: for each v in V, we have v, fin(v)-fout(v) = dv
• Feasibility Problem: does there exist a circulation that meets the two conditions above?
• If there exists a feasible circulation with demands {dv}, then sum of the demands = 0

Designing and Analyzing an Algorithm for Circulations

• We can reduce the problem of finding a feasible circulation with demands {dv} to the problem of finding a maximum s-t flow in a different network
• We attach a “super-source” s* to each node in S and a “super-sink” t* to each node in T
  • create a graph G' from G by adding new nodes s* and t* to G
  • for each node v in T, we add an edge (v,t*) with capacity dv
  • for each node u in S, we add an edge (s*, u) with capacity du
  • carry the remaining structure of G over to G' unchanged
• Can think of this reduction as introducing a node s* that “supplies” all the sources with their extra flow, and a node t* that “siphons” the extra flow out of the sinks.
• There cannot be an s*-t* flow in G' of value greater than D, since the cut (A,B) with A ={s*} only has capacity D
  • Further, if there is a flow of value D in G', there there is such a flow that takes integer values
• There is a feasible circulation with demands {dv} in G if and only if the maximum s*-t* flow in G' has value D. If all capacities and demands in G are integers, and there is a feasible circulation, there there is a feasible circulation that is integer-valued
• The graph G has a feasible circulation with demands {dv} if and only if for all cuts (A,B), the sum of for all v in B of dv ⇐ c(A,B).

The Problem: Circulations with Demands and Lower Bounds

• To force the flow to make use of certain edges, we can enforce lower bounds on edges
• G=(V,E) with a capacity of ce and a lower bound le on each edge e
• -⇐ le ⇐ ce for each e
• each node v also has a demand dv (positive or negative)
• all are integers
• circulation in flow network must satisfy two conditions:
  • Capacity: for each e in E, we have le⇐f(e)⇐ce
  • Demand: for every v in V, we have fin(v)-fout(v) = dv

Designing and Analyzing an Algorithm with Lower Bounds

• Reduce this to the problem of finding a circulation with demands but no lower bounds
• On each edge e, we need to sent at least le units of flow
• Initial circulation: f0(e) = le
  • f0 satisfies all the capacity conditions (both lower and upper bounds)
• If Lv = dv, where Lv is quantity, then we have satisfied the demand condition at v
• If not, then we need to superimpose a circulation f1 on top of f0 that will clear the remaining “imbalance” at v
  • f1in(v)-f1out(v) = sum of all e into v of le = the sum of a v of le
• There is a feasible circulation in G if and only if there is a feasible circulation in G'
  • If all demands, capacities, and lower bounds in G are integers and there is a feasible circulation, then there is a feasible circulation that is integer-valued.

This section took the concept of network flows to the next level by bringing in other variations/extensions of the original problem. While the overarching problems made sense, I got bogged down in a lot of the terminology and new factors that were added in. I think I need to reread this section one more time after we go over it in class to fully grasp the concepts presented in this section.

Readability: 5.5 Interesting: 5.5