# Matching girls with boys without mutual attraction (variant of maximum bipartite matching)

Let us say you have a group of guys and and a group of girls. Each girl is either attracted to a guy or not, and vice versa. You want to match as many people as possible to a partner they like.

Does this problem have a name? Is it feasibly solvable? Sounds hard to me...

Ps. note that since the attraction is not neccessarily mutual the standard max-flow solution does not work.

-
Title improvements welcome. Don't feel it is as helpful as could be, but was the best I could come up with. – The Unfun Cat Nov 21 '12 at 11:05

I think it is still the standard bipartite maximum matching problem, which can be solved by the algorithm of Hopcroft and Karp.

You put an edge in the bipartite boys-girls graph, iff you have mutual attraction. Then you maximize your matching and voilà. Notice that if you would never assign a boy to a girl with one-sided attraction, since this does not increase you objective function (# of mutal attractions).

If you want to maximize the number of happy people, then you set the weights of the complete bipartite boys-girls graph as follows

• mutual attraction = 2 happy people
• one sided attraction = 1 happy people
• otherwise = 0 happy people

You then can compute the maximum weighted bipartite matching.

-
"You want to match as many people as possible to a partner they like." With this I meant that if A likes B but B does not like A you might possibly still include the A to B edge as it would give you a score of one. If both liked each other that would give you a score of two. I probably did not explain this well enough, very sorry. – The Unfun Cat Nov 21 '12 at 13:10
Ah, there is a weighted version. Thanks. – The Unfun Cat Nov 21 '12 at 13:21