Tutorial 6 of CSCI2110 Bipartite Matching Tutor: Zhou Hong (周宏) [email protected] Outline • Maximum Bipartite Matching • B-Matching • Tic-Tac-Toe (Optional) • Midterm Review Maximum Matching The bipartite matching problem: Find a matching with the maximum number of edges. B A E G=(A∪B,E) In the following, we assume |A|=|B| for simplicity. A perfect matching is a matching in which every vertex is matched (i.e. of degree 1). Reduce to Perfect Matching: • Once you know how to solve perfect matching, you can also do maximum matching. Oracle of Perfect Matching output input Perfect Perfect No Perfect Matching Our Goal: find a maximum matching by querying perfect matching oracle as few as possible Bipartite Graph Contains Perfect Matching If G already has a perfect matching M, then M must be a maximum matching. We done with only one query! A B However, what shall we do if G does not contain a perfect matching? Matching of Size n-1 To get an ideal of the reduction step, first, we assume G has a maximum matching of size n-1. A B First Attempt • By adding an appropriate edge, G will contain a perfect matching. We can find it by one query. • Then, remove new added edge from the perfect matching, we done. A B Drawback of This Approach? We need to try different pair of vertices, in the worst case, O(n2) queries are required. A Better Solution • Add two dummy vertices connecting to all vertices on the opposite. • In the new graph, we find a perfect matching by one query. • Remove the new added edges, we have a maximum matching of original graph. A B A matching of size n-1 in original graph guarantees a perfect matching in new graph A Better Solution • Add two dummy vertices connecting to all vertices on the opposite. • In the new graph, we find a perfect matching by one query. • Remove the new added edges, we have a maximum matching of original graph. A B On the other hand, a perfect matching in new graph will guarantee a matching of size n-1 in original graph Complete Reduction No perfect matching in the new graph implies no matching of size n-1 in the original graph. What shall we do? Repeat the previous procedure until we find a perfect matching • In each iteration – We add two dummy vertices connecting with all vertices on the opposite. – Make a query with the updated graph. How many queries do we need? At most n Using binary search, we can improve to log(n) queries! Residence Assignment Assignment Requirements: • Each student can be assigned to at most one room • Each room can accommodate a specific number of students Our Goal: Maximize the number of residents Basic Idea • For a shared room with b beds, treat it as b single rooms • In the new setting – Applying for a shared room becomes applying for all b duplicate single rooms – Then, we only need to find a maximum matching B-Matching Suppose we have a bipartite graph G=(A∪B,E), for each vertex v, there is a degree bound bv. A B A b-matching is a subset of edges so that each vertex v∈A∪B has degree at most bv. Matching is a special case of b-matching, with bv=1 for all v. Reduction to Maximum Matching • For each vertex v with degree bound bv, make bv copies of vertex v. • Connect the duplicate vertices according to the original graph. 1 ′ 1 = 2 2 = 1 1 = 1 1 1 2 2 2 = 2 2 ′ Reduction to Maximum Matching • For each vertex v with degree bound bv, make bv copies of vertex v. • Connect the duplicate vertices according to the original graph. • Find a maximum matching in the new graph. • Map the resulting matching back to the original graph. 1 ′ 1 = 2 2 = 1 1 = 1 1 1 2 2 2 = 2 2 ′ Tic-Tac-Toe • A paper-and-pencil game. – Two players (X and O) – They take turns marking spaces in a 3x3 grid • Player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game • Best play from both parties leads to a draw A game won by the first player X Winning Set of Tic-Tac-Toe Therefore, there are totally 8 winning sets Bipartite Graph • Now, let’s construct a bipartite graph – On one side, the vertices corresponding to the squares in the grid (totally 9) – On the other side, the vertices corresponding to the winning sets (totally 8) – An edge between a square and a winning set indicate that the square is in the winning set 1 2 3 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 Generalized Tic-Tac-Toe • Generalize to nxn grid – There are n2 squares – Winning sets are still the whole horizontal, vertical or diagonal rows, totally 2n+2 B-Matching • Consider a b-matching in the bipartite graph between squares and winning sets – Degree bound for square is 1 – Degree bound for winning set is 2 • We claim that – if there exists a b-matching such that each winning set incidents with exactly 2 edges – then player 2 has a trivial strategy to avoid losing Example of 5x5 Grid • In case of 5x5 grid Tic-Tac-Toe, there exists a b-matching as required – (not shown) • Player 2 has a trivial strategy to force a draw – Pair squares in the grid according to the b-matching – If player 1 marks a square in a pair, then marks the other square in the pair, otherwise marks randomly … … 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Note that, player 1 can never mark both squares in a pair. 4 … … Existence of The Trivial Strategy V.S. Hall’s Theorem • For each winning set, make a copy of it in the bipartite graph • Then, the desired b-matching is corresponding to a matching saturating both original and duplicate winning sets Generalized Hall’s Theorem: A bipartite graph G=(V,W;E) has a matching saturating W if and only if |N(S)| >= |S| for every subset S of W. Player 2 does not always have such a trivial strategy to avoid losing, consider the standard (3x3) Tic-Tac-Toe! Thank You! Q&A?