7.5 A First Application: The Bipartite Matching Problem

• A Bipartite graph G =(V,E) is an undirected graph whose node set can be partitioned as V = X U Y, where every edge e ∈ E has one end in X and the other in Y.
• A Matching M in G is a subset of the edges M ⊆ E such that each node appears in at most one edge in M.
• The Problem: Find the matching in G of largest possible size
  

• Create digraph G' = (L ∪ R ∪ {s, t}, E' )
• Direct all edges from L to R, and assign unit capacity
• Add source s, and unit capacity edges from s to each node in L
• Add sink t, and unit capacity edges from each node in R to t

• Let's suppose there is a matching in G consisting of k edges (x_i,y_i),…,(x_ik,y_ik)
• Let's now consider the flow f that sends one unit along each path of the form s,x_ij,y_ij),t
  

=⇒ f(e) = 1 for each edge on one of these paths

• Then suppose there is a flow f' in G' of value k.
  • ⇒ By integrality Theorem for maximum flows, there is an integer-valued flow of value k. Since all capacities are 1, this means that f(e) is equal to either 0 or 1 for each edge edge e
    

Let's now consider the set M' of edges of 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'
• The size of the maximum matching in G = value of the maximum flow in G', and 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 implemented to find a maximum matching in a bipartite graph in O(mn) time.

• We need to find a way to convince one that there is no perfect matching in a certain graph. This “certificate” would allow us to convince someone that there is no perfect matching without having to trace the entire execution of the algorithm. To do so, we proceed as follows:
  • We decide if the graph G has a perfect Matching by checking if the maximum flow in a related graph G' has value 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
  • Thus in a way a cut with capacity less than n provides us with such certificate( that way of convincing someone there is no perfect matching in graph without having to trace out the entire algorithm.)
• Let's consider a subset of nodes A⊆ X and let Γ(A) ⊆ Y be the set of all nodes that are adjacent to nodes in A:
  • If the graph has a perfect matching, then each node in A has to be matched to a different node in Γ(A)
  • Thus Γ(A) must be at least as large as A. Consequently:
    • If a bipartite graph G = (V,E) with two sides X and Y has a perfect matching, then for all A ⊆ X we must have |Γ(A)| ≥ |A|
• Let us assume that the bipartite graph G = (V,E) has two sides in X and Y such that |X| = |Y|.
  • Then the graph G either has a perfect matching or there is a subset A⊆ X such that |Γ(A)| < A.
  • A perfect matching can be found in O(mn) time
    

When I was in class, I didn't have a chance to follow the lecture as much as I was supposed to. Because I had missed out on the foundations of this section, I couldn't find myself as I had a really bad week and couldn't review the slides. But reading this section helps me a lot and puts me a bit back on track.
I give this section an 8/10