Unformatted text preview:

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

PSU CSE 565 - Network Flow

Download Network Flow
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Network Flow and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Network Flow 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?