CMSC 451: Maximum Bipartite Matching

1 CMSC 451: Maximum Bipartite MatchingSlides By: carl KingsfordDepartment of Computer ScienceUniversity of Maryland, College ParkBased on Section ofAlgorithm Designby Kleinberg & Flowssuvtxw201030205301020101051515510 The network flow problem is itself even more interesting is how you can use it to solve manyproblems that don t involve flows or even Graphs Suppose we have a set ofpeopleLand set of jobsR. Each person can do onlysome of the jobs. Can model this as abipartite graph uxLRPeopleTasksPerson u can do task xBipartite Matching Amatchinggives anassignment of people totasks. Want to get as many tasksdone as possible. So, want amaximummatching: one thatcontains as many edges aspossible. (This one is not Maximum .)abcde12345 LRPeopleTasksMaximum Bipartite MatchingMaximum Bipartite MatchingGiven a Bipartite graphG= (A B,E), find anS A Bthat isa Matching and is as large as : We re givenAandBso we don t have to find them.

2 Sis aperfect matchingif every vertex is matched. Maximumis not the same asmaximal: greedy will get Given an instance ofbipartite Matching , Create an instance ofnetwork flow. Where the solution to thenetwork flow problem caneasily be used to find thesolution to the of Maximum Bipartite MatchingInstance of Network Flowtransform,aka reduceReducing Bipartite Matching to Net Flowabcde12345 LRPeopleTasksReducing Bipartite Matching to Net Flowabcde12345 LRPeopleTasksReducing Bipartite Matching to Net Flowabcde12345 LRPeopleTasksstReducing Bipartite Matching to Net Flowabcde12345 LRPeopleTasksst1111111111111111111 Using Net Flow to Solve Bipartite MatchingTo Recap:1 Given Bipartite graphG= (A B,E), directthe edges new an edge fromsto every vertex an edge from every vertex all the capacities Maximum network flow problem on this new graphG.

3 The edges used in the Maximum network flow willcorrespond to the largest possible Matching !Analysis, Notes Because the capacities are integers, our flow will be integral. Because the capacities are all 1, we will either: use an edge completely (sending 1 unit of flow) or not use an edge at all. LetMbe the set of edges going fromAtoBthat weuse. We will show that1 Mis a matching2 Mis the largest possible matchingMis a matchingWe can choose at most one edge leaving any node can choose at most one edge entering any node we chose morethan 1, we couldn thave balanced between flows and matchings If there is a matchingofkedges, there is aflowfof valuek. fhas 1 unit offlow across each ofthekedges. 1 unit leaves &enters each node(excepts,t) If there is a flowfofvaluek, there is amatching (f) = fout(A) - fin(A)Correspondence between flows and matchings If there is a matchingofkedges, there is aflowfof valuek.

4 Fhas 1 unit offlow across each ofthekedges. 1 unit leaves &enters each node(excepts,t) If there is a flowfofvaluek, there is amatching (f) = fout(A) - fin(A)Mis as large as possible We find themaximumflowf(say withkedges). This corresponds to a matchingMofkedges. If there were a Matching with>kedges, we would have founda flow with value>k, contradicting thatfwas Maximum . Hence,Mis Time How long does it take to solve the network flow problem onG ? The running time of Ford-Fulkerson isO(m C) wherem isthe number of edges, andC= eleavingsce. C=|A|=n. The number of edges inG is equal to number of edges inG(m) plus 2n. So, running time isO((m+ 2n)n) = (mn+n2) =O(mn)TheoremWe can find Maximum Bipartite Matching in O(mn) : Bipartite Matching Fold-Fulkerson can find amaximum Matching in abipartite graph inO(mn)time.

5 We do this byreducingtheproblem of maximumbipartite Matching tonetwork of Maximum Bipartite MatchingInstance of Network Flowtransform,aka reduc