Let $X = \{x_1, ... , x_k\}$ and $Y = \{y_1, ... , y_h\}$.
A subset $S \subset X \times Y$ is a correspondence if :
- $\forall x, \exists y, (x,y) \in S$ and
- $\forall y, \exists x, (x,y) \in S$
That is to say, $S$ fully projects onto $X$ and $Y$.
Now for the problem. Given an $n \times m$ matrix of subsets $(S_{i,j})$, select a subset from each row, (denoted by a selection function $s:\{1,..,n\} \rightarrow \{1,..,m\}$) such that the intersection $\cap_{i=1}^{n} S_{i,s(i)} $ contains a correspondence; or conclude there is no such function.
Is this solvable in polynomial time of $max \{k,h,n,m\}$ ?
I have tried reducing the problem from Set Packing, Set Cover, and Hitting Set with no luck. It is clearly NP, and I suspect it is NP-hard.