atishey's blog

Maximum Bipartite Matching
By atishey, history, 8 years ago, In English

You will be given two sets of integers. Let's call them set A and set B. Set A contains n elements and set B contains m elements. You have to remove k1 elements from set A and k2 elements from set B so that of the remaining values no integer in set B is a multiple of any integer in set A. k1 should be in the range [0, n] and k2 in the range [0, m].

You have to find the value of (k1 + k2) such that (k1 + k2) is as low as possible. P is a multiple of Q if there is some integer K such that P = K * Q.

Suppose set A is {2, 3, 4, 5} and set B is {6, 7, 8, 9}. By removing 2 and 3 from A and 8 from B, we get the sets {4, 5} and {6, 7, 9}. Here none of the integers 6, 7 or 9 is a multiple of 4 or 5.

So for this case the answer is 3 (two from set A and one from set B).

n and m will be in the range [1, 1000].

Sample Input:

4 2 3 4 5 4 6 7 8 9

Output:

3 **** Why the solution of this problem is maximum bipartite matching ? **** I have solved this question by successively removing the node which has maximum degree until all the edges are removed. Why this approach is wrong?

This question is from lightoj , link is http://lightoj.com/volume_showproblem.php?problem=1149

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Suppose you have these sets:

1 5 7 11 13

10 14 22 26

According to your approach, you will remove the number 1 from the first set:

5 7 11 13

10 14 22 26

Then, you will remove 4 numbers, no matter from which set you pick them (removing the factor-multiple relationship, of course). In the end, you will remove 5 numbers.

Unfortunately, this greedy approach is incorrect. You can simply remove all the elements from the second set (4 numbers).

Read about minimum vertex cover and Konig's Theorem, and it will be clearer to you!

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

i think u need here the number of vertices in minimum vertex cover which is equal to the number of edges in maximum matching in bipartite graphs according to Konig's Theorem. [link](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory))

** Explanation:** you need the minimum number of removals in sets (A,B) to have no pairs of number where one of them divide the other (the divisibility relation between 2 numbers means in our bipartite graph that they have edge between them) ... so we want to remove all the edges in the graph by removing smallest number of vertices and the number of vertices in minimum vertex cover(MVC) is exactly this result ... the MVC contains the lowest number of vertices where all edges are indecent to those vertices (by removing those vertices and all edges indecent to them we are in fact removing all edges in the graph )

hope that i helped your understand why it's a matching problem :P

→ Reply