3
$\begingroup$

Input:

  • $X$ = {$x_1$,$x_2$,$x_3$,...,$x_n$}

  • $Y$ = {$y_1$,$y_2$,$y_3$,...,$y_m$}

  • $k$, where, $k$ $\leq$ $m$

Output (Yes/No): Satisfying the following condition, can all the elements in set $X$ be assigned to elements in set $Y$, such that, no elements in $X$ is left unassigned?

Condition: At least $k$ elements in $Y$ is needed to access all the elements in $X$. All the elements assigned to $y_i \in Y$ are said to be accessible using $y_i$.

Reduce this decision problem to CNF-SAT.

Thoughts:

I have considered $n \times m$ no. of variables. Each variables for a pair of element of set $X$ and set $Y$. i.e., $a_{ij}$ : for all $x_i$ and $y_j$.

For ensuring that no elements in $X$ is left unassigned the CNF expression will be. $(a_{11} \vee a_{12} \vee ... \vee a_{1m}) \wedge (a_{21} \vee a_{22} \vee ... \vee a_{2m})... (a_{n1} \vee a_{n2} \vee ... \vee a_{nm})$

I am not able to form the CNF expression for ensuring that at least $k$ elements from $Y$ are required to access all the elements in $X$. It seems that there will be an exponential number of clauses in the expression.

Thanks for helping.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed and/or downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Aug 10 '16 at 7:26
  • $\begingroup$ @Raphael - Thanks for your suggestions. I have edited the details of the question as suggested. $\endgroup$ – Gradient Aug 10 '16 at 10:04
4
$\begingroup$

Yes, you certainly can reduce it to SAT: the problem you state is obviously in NP, and thanks to Cook's theorem, everything in NP can be reduced to SAT.

I suspect that wasn't what you actually meant to ask. Actually, your problem is in P: Hall's theorem says that such an assignment exists if and only if the corresponding bipartite graph has a perfect matching. You can test whether a bipartite graph has a perfect matching in polynomial time using standard algorithms.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.