2
$\begingroup$

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.

||cite|improve this question
$\endgroup$
  • $\begingroup$ Hint: Try reducing from Set Cover again, with $X$ containing one more element than than the ground set in the SC instance, and $Y$ equal to $a$ copies of that ground set, where $a$ is the SC threshold parameter ("Does a set cover using at most $a$ sets exist?"). It's OK for each matrix row to look... Similar ;-) (Finally, I find it easier to think of each $S_{i,j}$ as a subset of edges in a complete bipartite graph; we are looking for an intersection that leaves no isolated vertices.) $\endgroup$ – j_random_hacker Jul 20 '17 at 0:03

Your Answer

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

Browse other questions tagged or ask your own question.