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