Suppose I have two sets $A$ and $B$. We will be considering pairs of elements $(a,b)$, where $a\in A$ and $b \in B$. I have a function $f(a,b) \rightarrow \{0,1\}$, i.e. for each pair I can say whether it is "allowed" or not. Given the complete output of $f$, i.e. the list of all allowed pairs, I want to determine the maximum number of mutally allowed pairings that can be achieved. By mutually allowed I mean that elements of $A$ and $B$ may only appear once in a set of mutually allowed pairs.
Here's a simple example in the form of a table:
| a0 | a1 | a2 | |
|---|---|---|---|
| b0 | X | X | |
| b1 | X | ||
| b2 | X | X |
i.e. this is the output of my function $f$. So the indices of the allowed pairs are (0,0), (1,0), (1,1), (1,2), and (2,2). In this case it is fairly intuitive to see that the maximum number of simultaneous pairs is achieved by (1,1),(2,2),(3,3), so the answer is 3. But I am not sure about the general case.
It feels like there is probably some matrix voodoo that can be done to solve this problem efficiently. I am hoping it can be done with better than combinatoric complexity, which I think is what you get if you try to just check all the possible sets of mutually-allowed pairings and see which is largest.