Checking if several sets of pairs covers a given set of pairs

Question

Suppose we have $N$ arrays of pairs, e.g. for $N=3$:

$A_1 = [ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]$,

$A_2 = [ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]$ and

$A_3 = [ [4,1], [5,1], [5,2], [7,1] ]$.

We can assume that the pairs in every array are sorted by the first number, and then by the second number. Also, the same pair won't appear in the same array more than once (same pair can appear in multiple arrays, as you can see above).

The numbers in every pair are arbitrary integers $\geq 1$.

How could I find all the $k$'s that satisfy:

$\exists \{ p_1, p_2, ... , p_N\}\subseteq [1..N]\ \forall n \in [1..N]: [k,n]\in A_{p_n}$

The expected result for the example above is: $[5, 7]$.

Note: Speed is the most critical factor of the algorithm, then memory. If it helps to optimise for speed/memory, assume that $N\leq 10$. The number of pairs in an array can be ~50000.

Answer 1

Here are some hints.

First, reduce your problem to the following one: given a collection of $N$ subsets $A_1,\ldots,A_N \subseteq [N]$, determine if there is some permutation $\pi$ such that $\pi(i) \in A_i$.

Given the $A_i$, construct a bipartite graph in which node $i$ on the left is connected to node $j$ on the right if $i \in A_j$. A permutation $\pi$ such that $\pi(i) \in A_i$ exists iff this graph contains a perfect matching. We know how to test whether a bipartite graph contains a perfect matching efficiently.