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.
Given multiple families of sets, select a set from each such that the intersection of selected sets is a correspondence
time complexity;np complete;set cover