Efficient computational matchings and lax sexual morality

Hall’s marriage theorem is well-known and frequently useful, but it’s a nightmare from a computational perspective.

The standard proof can be turned into an algorithm which finds a matching, but it’s impracticably slow. The reason for this is that the theorem contains the phrase “every subset”, and one doesn’t want to be testing every subset of a set in real life. Indeed, an algorithm that matches n men to n women in time is in some sense not much better than trying every possible matching in turn!

But, as it turns out, there’s another way of going about the subject which is much more efficient in practice: an approach apparently well-known to experts, but not well-known to one of the authors (JDC) until last week.

We’ll need the notion of a partial matching: that’s when we have some marriages, and perhaps some unmarried people left over. Ignoring civil partnerships, bigamy, trigamy, and all higher-order polygamy, real life is a partial matching; the concept is familiar.

Given a partial matching, we’ll say that a swingers’ party is a line of people with the following properties:

• there are an even number of people (at least two);
• they alternate between men and women;
• the people at each end are unmarried (wlog, a man on the left and a woman on the right);
• the people between the ends are a chain of married couples;
• every pair of neighbours in the line wouldn’t mind being married.

In other words, it alternates between couples who simply fancy each other, and couples who are already married:

Note that there is a degenerate case, consisting of two people: one unmarried man and one unmarried woman who would be happy to be married. Conventional morality frowns strongly upon unmarried men being alone at parties with unmarried women, so we do not mind calling this degeneration a swingers’ party.

However, in a striking departure from conventional morality, swingers’ parties are a great thing for improving matchings. If you can find a swingers’ party, you can swap over the married couples and the unmarried couples, and that increases the number of marriages by one.

The theorem of interest is that a configuration admits a total matching if and only if, given every partial matching, and any unmarried person, we could hold a swingers’ party featuring that person. In fact it’s enough to have this true for any unmarried man, or alternatively for any unmarried woman.

If we have an incomplete matching with no potential swingers’ parties, then we can find a set which violates Hall’s marriage condition. Specifically, we choose an unmarried man, together with all the women whom he fancies, and all of their husbands, and so on until we can go no further. This cannot terminate in an unmarried woman, lest we would have a swingers’ party. Hence, the resulting set must necessarily contain a surplus of men, violating the marriage condition and thereby proving that Hall’s condition implies that every incomplete matching contains a potential swingers’ party. The converse is trivial, so this is equivalent to the existence of a perfect matching.

What’s more, this theorem leads to a genuinely efficient algorithm. Given a partial matching and a choice of unmarried man, we can construct a swingers’ party in time linear in the number of potential marriages, if one exists, by searching in the obvious way and keeping track of dead ends. That means that, starting from the empty partial matching, with everybody unmarried, one can produce a total matching (if one exists) in time (and less if the number of potential marriages is bounded somehow), which is a considerable improvement.

In the literature, swingers’ parties seem to go by the euphemism alternating paths, but our instinct is to call them what they are.

(This post is a joint effort with James Cranch. Both authors wish to apologise for the inherent heteronormativity of the subject matter, and would love to hear about theorems which reflect reality better.)