### Gay Marriage - The Theoretical CS Perspective

You may know of the database perspective on gay marriage. If you're like me, you read that thinking: "Is this something we really want to leave to applied science?" I mean, they'll probably use meters instead of feet and crash everyone into Mars. Fortunately, combinatorics provides us with a much better solution.

I am referring, of course, to the stable marriage problem.

Suppose we are given $n$ men and $n$ women. Each person makes a preference ranking $p_1\succ \dots \succ p_n$ indicating who they would like to marry. E.g. the ranking $A \succ B \succ C$ would correspond to wanting to marry A the most, then B, then C the least.

A solution here is referred to as "stable" if extra-marital love is always unrequited. So it's OK for Joe to love Jane as long as Jane doesn't love Joe. (At least she can't love him as much as her current husband.)

Gale and Shapley found a stable (but not optimal) solution which runs in $n \log n$ expected time in 1962.

Here is where things get interesting. You might expect that a gay world would have an even faster solution, since we've cut the number of variables in half. But you'd be wrong! Not only does the gay matching problem not have a quick solution, a solution is not even guaranteed to exist!

So the gay community may be doomed to an ever-changing cycle of romantic partnerships. Whether that's better than guarantee of adequacy given to heterosexuals is left as an exercise for the reader.

(As a side note: this "gay marriage problem" is referred to in the literature as the "stable roomate problem." You would think that a simple renaming would lead to a massive grant from some fundamentalist college for any researcher demonstrating the "intractability of gay marriage.")

To shed some more light on the subject, let's invert the problem. We previously tried to group people based on who they like, now let's try to group them based on who they don't like.

In a purely heterosexual world this can be represented as a graph, where each vertex is a person and an edge from $v_i$ to $v_j$ indicates that person $i$ is of the same gender as person $j$. To partition the graph into disjoint subsets is now very easy, and can even be done in linear time.

However, warning bells should be going off in your head. The general case of graph partitioning is not just hard but NP-Complete.

The introduction of gay people doesn't throw off our original, simple, algorithm here though. As long as no gay person likes a straight person (or vice versa), gay women can be seen as equivalent to straight men and a trivial greedy algorithm can partition it in linear time. (Although the subsets may not be of equal size.)

You're probably expecting me to bring in bisexuals here as the monkeywrench. But bisexuals are the best possible vertices to have! Since they have no edges going anywhere, we can essentially ignore them.

The real problem is not bisexuals but asexuals: people who have taken a vow of chastity or who otherwise don't have sex. These people have edges going to everyone, causing the partition problem to reach full NP-Completeness!

I think we can agree: the problem society faces is not gay marriage, but chastity. If campaigners were really committed to reducing society's computational complexity, they would be working to ensure everyone has sex with as many people as possible.