2
$\begingroup$

I'm trying to find a general approach to determining how many unique pairs I can form given two lists of items. The elements of each list are different. Within each list, items can be repeated. For example,

list 1     list 2
======     ======
1          A
2          A
2          A
3          A
3          A
3          B
4          B
5          B

Because of repetition, in this case there are only 7 unique pairs possible. ([3,A] must appear more than once).

If we pair the items in the order they are given, we get 6 unique pairs:

(1,A), (2,A), (3,A), (3,B), (4,B), (5,B) are unique [(2,A) and (3,A) would appear twice]

However, if we pair differently, we can get one more unique pair.

(1,A), (2,A), (2,B), (3,A), (3,B), (4,B), (5,A) are unique [(3,A) would appear twice]

Order doesn't matter (i.e., pair 1,A is the same as A,1).

Is there a general approach to computing the unique possible matchings? Any leads are appreciated.

$\endgroup$
  • $\begingroup$ Is a pair of elements from the same list allowed? $\endgroup$ – barak manos Feb 19 '15 at 15:33
  • $\begingroup$ No, the pairs have to use exactly one item from list 1 and one item from list 2 $\endgroup$ – pequod Feb 19 '15 at 16:02
  • $\begingroup$ What about the order? For example, are $(1,A)$ and $(A,1)$ considered two different pairs? $\endgroup$ – barak manos Feb 19 '15 at 16:10
  • $\begingroup$ No, those would be the same pair. Order doesn't matter. Thanks. $\endgroup$ – pequod Feb 19 '15 at 16:14
  • $\begingroup$ Your example isn't clear to me. I see $5$ different elements on the first list and $2$ different elements on the second list, hence the total number of different pairs is $5\cdot2=10$. How did you get to $8$ or $7$??? $\endgroup$ – barak manos Feb 19 '15 at 16:17
1
$\begingroup$

After looking at various research papers I am fairly comfortable with using the greedy algorithm outlined below, suspecting it always produces a maximum pairing. In any case there is a quick check to determine when any pairing is a maximum (in linear time in number of vertices). If this check finds a pairing is not a maximum, then it provides a way to construct a larger pairing.

Greedy algorithm

Take the list with the fewest distinct values (the 2nd list in the example) and pair the highest frequency value there (in this case A) with as many distinct values from the other list as possible.

In this case that produces five distinct pairs:

(1,A), (2,A), (3,A), (4,A), (5,A)

leaving the reduced problem of determining how many distinct matches we can make with B from the second list, and the remaining two distinct values in the first list:

(2,B), (3,B)

One way to think about this is the maximum number of edges in a labelled bipartite graph with (vertex) degree constraints, e.g.

1(1)
2(2)        A(5)
3(3)
4(1)        B(3)
5(1)

where the maximum allowed degrees are shown in parentheses next to the vertex "labels".

In the literature this type of problem is called the "degree constrained subgraph" problem as well as the "maximum cardinality b-matching" problem. Here $b$ denotes a function on the vertices of a graph $G$, $b: V \to \mathbb{N}$, that gives an upper bound on the degree $\delta(v)$ that vertex would have in a subgraph (subset $M$ of edges of $G$). Note that if $b\equiv 1$ at all vertices, this notion is simply that of a matching on $G$.

If $G=(X,Y;X\times Y)$ is a complete bipartite graph (as is the case here; any item on one list can be paired with any item on the second list), the problem of determining if the specified degree sequences $\delta(v) = b(v)$ can be attained in a subgraph of $G$ is called the bipartite realization problem, for which a polynomial time algorithm exists by consequence of the Gale-Ryser theorem. When it succeeds in attaining all the degree bounds exactly, this is essentially the greedy algorithm above.

Formulation as a maximum network flow

The Ford-Fulkerson approach solves the bipartite realization problem, but also the more general problem posed here, of finding the maximum number of pairings (b-matching).

Given the two sets $X$ and $Y$ of distinct values in lists 1 and 2, respectively, define the complete bipartite graph $X\times Y$ and two additional nodes, source $s$ and sink $t$. If each edge in the complete bipartite graph $X\times Y$ is given capacity 1, and if edges from $s$ to each vertex in $X$ are given capacity equal to the frequency it appears in the first list (degree constraint) and similarly edges from each vertex in $Y$ to $t$ given capacity equal to the frequency in the second list, then the maximum network flow from source to sink will be equal to the maximum cardinality of a b-matching in $G$.

I realize a picture will be helpful here:

Flow with source and sink added to bipartite graph

This formulation works when $G$ is any bipartite graph, not necessarily complete. The contribution of Ford and Fulkerson is to find a more efficient algorithm than merely solving the network flow by linear programming (i.e. maximizing flow out of source = flow into sink, subject to the sums of in/out flows cancelling at all internal nodes).

This more efficient algorithm uses the concept of augmenting paths, a path that alternates between edges of $G$ that are included in a current matching and edges that are not. A b-matching is a maximum if and only if there is no augmenting path, but if there is an augmenting path, this can be used to increase the size of the b-matching. The search for an augmenting path can be done in time linear to the number of vertices of $G$.

A fairly recent paper in this area is An $O(n^3)$ time algorithm for the maximum weight b-matching problem on bipartite graphs (Oct. 2014).

For a more historical introduction I recommend Edmonds, Matching, and the Birth of Polyhedral Combinatorics by William R. Pulleyblank, though it quickly moves beyond the treatment of bipartite graphs to matchings in general graphs by Jack Edmonds "blossom algorithm".

$\endgroup$
  • $\begingroup$ This is helpful, but I'm having trouble seeing how I would go from the picture (or the labeled graph you have in the table) to then compute the number of unique pairs? Can you say a little more? $\endgroup$ – pequod Feb 19 '15 at 19:35
  • $\begingroup$ I wasn't sure what your background with such graph algorithms might be, but I included some links to background material that is "classic" for this area. Let me first try to find a case where the greedy algorithm fails, because Ford-Fulkerson, while polynomial, is more complicated to implement. $\endgroup$ – hardmath Feb 19 '15 at 19:44
  • $\begingroup$ Awesome answer. Thanks so much. I've got an implementation that allows me to calculate max flow and so far it seems to be working! Need to do some more reading of the references you gave really wrap my head around what's happening. $\endgroup$ – pequod Feb 21 '15 at 19:36
  • $\begingroup$ Glad to be of service. I'm going to add more about the Gale-Ryser thm. on bipartite realization and the degree constrained subgraph problem. Just finished small fixes to the Wikipedia article on that. $\endgroup$ – hardmath Feb 21 '15 at 19:40
  • $\begingroup$ Also, in the image, shouldn't there be two additional edges between the green and blue nodes? The middle section is not complete. The second from the bottom and second from the top, of the green nodes, only have one connection to blue? $\endgroup$ – pequod Feb 21 '15 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.