10/22/2008 A. Smith; based on slides by S. Raskhodnikova and K. Wayne Adam Smith Algorithm Design and Analysis LECTURE 27 Network Flow •Application: Bipartite MatchingRecently: Ford-Fulkerson • Find max s-t flow & min s-t cut in O(mnC) time – All capacities are integers C –(We will discuss how to remove this assumption) •Duality: Max flow value = min cut capacity •Integrality: if capacities are integers, then FF algorithm produces an integral max flow 10/22/2008 A. Smith; based on slides by S. Raskhodnikova and K. WayneLast time • Reductions •Project Selection Problem (Section 7.11) –Reduction of project selection to min-cut •Today: –Maximum bipartite matching –Reducing MBM to max-flow –Hall’s theorem 10/22/2008 A. Smith; based on slides by S. Raskhodnikova and K. WayneMatching. Input: undirected graph G = (V, E). M E is a matching if each node appears in at most edge in M. Max matching: find a max cardinality matching. MatchingBipartite Matching Bipartite matching. Input: undirected, bipartite graph G = (L R, E). M E is a matching if each node appears in at most edge in M. Max matching: find a max cardinality matching. 1 3 5 1' 3' 5' 2 4 2' 4' matching 1-2', 3-1', 4-5' R LBipartite Matching Bipartite matching. Input: undirected, bipartite graph G = (L R, E). M E is a matching if each node appears in at most edge in M. Max matching: find a max cardinality matching. 1 3 5 1' 3' 5' 2 4 2' 4' R L max matching 1-1', 2-2', 3-3' 4-4'Reductions Roughly: Problem A reduces to problem B if there is a simple algorithm for A that uses an algorithm for problem B as a subroutine. Usually: • Given instance x of problem A we find a instance x’ of problem B • Solve x’ • Use the solution to build a solution to x Useful skill: quickly identifying problems where existing solutions may be applied. • Good programmers do this all the timeReduction to Max flow. Create digraph G' = (L R {s, t}, E' ). Direct all edges from L to R, and assign capacity 1. Add source s, and capacity 1 edges from s to each node in L. Add sink t, and capacity 1 edges from each node in R to t. Reducing Bipartite Matching to Maximum Flow s 1 3 5 1' 3' 5' t 2 4 2' 4' 1 1 1 R L G'Theorem. Max cardinality matching in G = value of max flow in G’. Proof: We need two statements • max. matching in G max flow in G’ • max. matching in G max flow in G’ Bipartite Matching: Proof of CorrectnessTheorem. Max cardinality matching in G = value of max flow in G'. Pf. Given max matching M of cardinality k. Consider flow f that sends 1 unit along each of k paths. f is a flow, and has cardinality k. Bipartite Matching: Proof of Correctness s 1 3 5 1' 3' 5' t 2 4 2' 4' 1 1 1 1 3 5 1' 3' 5' 2 4 2' 4' G' GTheorem. Max cardinality matching in G = value of max flow in G'. Pf. Let f be a max flow in G' of value k. Integrality theorem k is integral; all capacities are 1 f is 0-1. Consider M = set of edges from L to R with f(e) = 1. – each node in L and R participates in at most one edge in M – |M| = k: consider cut (L s, R t) Bipartite Matching: Proof of Correctness 1 3 5 1' 3' 5' 2 4 2' 4' G s 1 3 5 1' 3' 5' t 2 4 2' 4' 1 1 1 G'Exercises • Give an example where the greedy algorithm for MBM fails. • How bad can the greedy algorithm be, i.e. how far can the size of the maximum matching (global max) be from the size of the greedy matching (local max)? • What do augmenting paths look like in this max-flow instance?Def. A matching M E is perfect if each node appears in exactly one edge in M. Q. When does a bipartite graph have a perfect matching? Structure of bipartite graphs with perfect matchings. Clearly we must have |L| = |R|. What other conditions are necessary? What conditions are sufficient? Perfect MatchingNotation. Let S be a subset of nodes, and let N(S) be the set of nodes adjacent to nodes in S. Observation. If a bipartite graph G = (L R, E), has a perfect matching, then |N(S)| |S| for all subsets S L. Pf. Each node in S has to be matched to a different node in N(S). Perfect Matching No perfect matching: S = { 2, 4, 5 } N(S) = { 2', 5' }. 1 3 5 1' 3' 5' 2 4 2' 4' L RMarriage Theorem. [Frobenius 1917, Hall 1935] Let G = (L R, E) be a bipartite graph with |L| = |R|. Then, G has a perfect matching iff |N(S)| |S| for all subsets S L. Pf. This was the previous observation. Marriage Theorem 1 3 5 1' 3' 5' 2 4 2' 4' L R No perfect matching: S = { 2, 4, 5 } N(S) = { 2', 5' }.Pf. Suppose G does not have a perfect matching. Formulate as a max flow problem with constraints on edges from L to R and let (A, B) be min cut in G'. By max-flow min-cut, cap(A, B) < | L |. Choose S = L A. cap(A, B) = | L B | + | R A |. Since min cut can't use edges: N(S) R A. |N(S )| | R A | = cap(A, B) - | L B | < | L | - | L B | = | S|. Proof of Marriage Theorem S = {2, 4, 5} L B = {1, 3} R A = {2', 5'} N(S) = {2', 5'} s 1 3 5 1' 3' 5' t 2 4 4' 1 2' 1 1 1 A G' Which max flow algorithm to use for bipartite matching? Generic augmenting path: O(m val(f*) ) = O(mn). Capacity scaling: O(m2 log C ) = O(m2). Shortest augmenting path (not covered in class): O(m n1/2). Non-bipartite matching. Structure of non-bipartite graphs is more complicated, but well-understood. [Tutte-Berge, Edmonds-Galai] Blossom algorithm: O(n4). [Edmonds 1965] Best known: O(m n1/2). [Micali-Vazirani 1980] Recently: better algorithms for dense graphs, e.g. O(n2.38) [Harvey] Bipartite Matching: Running
View Full Document