content warning: polyamory, NP-complete problems
“It’s a shame that Facebook doesn’t let people list multiple romantic partners. Get with the times, Facebook.”
- Amanda MacAskill
I think Amanda’s right: this limitation turns out to generate some pretty complicated algorithmic problems, and they’re an unwelcome addition to my dating life.
Suppose you’re in a polycule (that is, a connected component of the relationship graph) and you want to represent your relationships on Facebook. Obviously, you can’t represent them all: every person in the polycule can only be in a single relationship.
Which relationships should you show on Facebook? Well, presumably you want to show the most important ones. Let’s just say that we’re measuring importance by the length of the relationship. So the question becomes: How do you decide a subset of relationships of a polycule, such that no-one is in more than one of those relationships, and the sum of lengths of relationships is maximized? Or equivalently: given a connected, weighted, undirected graph, choose a subset of edges with no shared nodes to maximize the sum of weights of edges.
This at first looked to me like the weighted set packing problem, one of Karp’s original NP-complete problems—each edge in the polycule corresponding to a two-element set in the set packing problem.
But then I looked into it more, and it turns out that for the specific case of relationships between only two people (sorry, triad participants), this problem is known as weighted maximum matching, and there’s a fast algorithm for it! You can read about the fast algorithm in this paper, and you can download the implementation here. It says it’s licensed for research only: I’m not sure whether that license permits usage for personal romantic relationships, but I think the likelihood of getting in trouble for it is pretty low.