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