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.

  • $\begingroup$ Title improvements welcome. Don't feel it is as helpful as could be, but was the best I could come up with. $\endgroup$ Nov 21, 2012 at 11:05

1 Answer 1


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.

  • $\begingroup$ "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. $\endgroup$ Nov 21, 2012 at 13:10
  • $\begingroup$ Ah, there is a weighted version. Thanks. $\endgroup$ Nov 21, 2012 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.