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.
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.