2
$\begingroup$

Let $A_1,A_2,\ldots,A_k$ be finite sets. Furthermore, for each $i\in\{1,2,\ldots,k\}$, let $B_i$ be a set whose elements are subsets of $A_i$.

Is there any polynomial-time algorithm that decides whether there exists a choice of precisely one element $C_i$ of each $B_i$ such that for all $x\in (C_1\cup C_2\cup\ldots\cup C_k)$ the following property is satisfied:

If $x\in A_i$ then $x\in C_i$ for each $i\in\{1,2,\ldots,k\}$?

Any pointer to a paper etc. would be greatly appreciated. Thanks.

$\endgroup$
3
  • $\begingroup$ This sounds related to 3 dimensional matching, an NP hard problem. Perhaps someone can post a reduction of 3DM or nDM to this problem? Gerhard "Ask Me About System Design" Paseman, 2010.06.10 $\endgroup$ Jun 10, 2010 at 18:09
  • $\begingroup$ This rather sounds like reducing 3SAT to me. $\endgroup$ Jun 10, 2010 at 18:15
  • $\begingroup$ I added the complexity-theory and NP tags. $\endgroup$ Jun 10, 2010 at 20:29

1 Answer 1

3
$\begingroup$

It seems to me that your problem is stronger than $\ell$-SAT. In fact, let $A$ be the set of our literals. Assume that we have $p$ clauses. For each $i\in\left\lbrace 1,2,...,p\right\rbrace$, let $A_i$ be the set of the literals occuring in the $i$-th clause, and let $B_i$ be the set of all nonempty subsets of $A_i$. Besides, add some more sets $A_{p+1}$, $A_{p+2}$, ..., $A_i$ which are of the form {literal, its negation}, and for every such sets $A_k$, let $B_k$ be the set of its 1-element subsets. I think that a choice of $C_i$ is the same as a satisfaction of all our clauses (the elements of $C_1\cup C_2\cup ...\cup C_k$ corresponding to those literals that are satisfied).

$\endgroup$
4
  • $\begingroup$ But perhaps you should use 3-SAT or other bounded size disjunctions, to avoid the blow-up in size that comes from taking all nonempty subsets for $B_i$? $\endgroup$ Jun 10, 2010 at 18:29
  • $\begingroup$ Thanks. In fact I intuitively perceived the size of the clauses to be "really small" compared to their number ;) $\endgroup$ Jun 10, 2010 at 18:38
  • $\begingroup$ Yes, I think this is required, since otherwise you won't have a polynomial reduction. $\endgroup$ Jun 10, 2010 at 20:13
  • $\begingroup$ Thanks to everybod and particularly to Darij for the reduction from SAT. Not quite what I had hoped for, but at least I now know that there "no" hope for a polynomial-time algorithm. $\endgroup$
    – simone
    Jun 11, 2010 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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