Choosing mutually exclusive pairs efficiently

Question

This is a problem that could be done with some type of brute-force algorithm, but I was wondering if there are some efficient ways of doing this.

Let's assume that we have the following pairs of integers

 (1, 3), (2, 5), (4, 7), (2, 7), (10, 9)

We want to figure out what is the maximum number of mutually exclusive pairs.

By mutually exclusive pair, I mean pairs such that they do not have any common integer.

For instance, we cannot choose both (2, 5), (2, 7) since both pairs contain 2.

In the above case, 4 would be a solution as we can choose the following mutually exclusive pairs:

      (1, 3), (2, 5), (4, 7), (10, 9)  

thus 4 maximum pairs total.

I was wondering if there are efficient ways of doing so.

Answer 1

Your question is equivalent to finding a maximum matching on a graph. The nodes of your graph are integers, and your pairs (a, b) are edges of the graph. A matching is a set of pairwise non-adjacent edges, which is equivalent to saying the same integer doesn't appear in two edges.

A polynomial time solution to this problem is the Blossom algorithm also known as Edmond's algorithm. It's rather too complicated to include the details in the answer here.