Algorithm puzzle

Suppose that you live in a society with arranged marriages and you've been elected the town matchmaker. You'd like to make everyone happy, so you request a list from each man and woman about who they would be willing to marry. Your job is then to find a set of pairings that maximize the number of matches.

Okay, that's not too bad, it's a bipartite matching problem and can be solved with the Hopcroft-Karp algorithm.

Now suppose that it's also a polyandrous society, where every woman marries exactly two men. In addition to preferring certain men, each women also wants a pair of men with complementary skills, but every woman has a slightly different opinion about what that entails. So, for example, we may have:

Alice is willing to marry (Martin and Nick) or (Martin and Otto) or (Nick and Paul).
Beatrice is willing to marry (Martin and Nick) or (Otto and Paul).

How do we determine the maximum matching? (in polynomial time)


28 comments to Algorithm puzzle