I had this question when looking at problem C on this morning's code jam:

Suppose you have a set $S$ and $N$ pairs of subsets $\{S_i^0, S_i^1\}$, $S_i^j\subset S.$

Does there exist a cover of $S$ consisting of (at most) one subset from each pair? Ie, does there exist an $\alpha \in \{0,1\}^N$ with $S=\cup_i S_i^{\alpha_i}$?

Is there a polynomial time algorithm for answering this question? It has a network flow "smell" to it and seems like it's probably a standard problem, but I couldn't find it looking at lists of problems related to set cover.


That is tightly equivalent to CNF-SAT.

CNF-SAT ​ $\to$ ​ your problem ​ ​ ​ :

The subscripts are the variables and the superscripts indicate whether the
literal is positive or negative. ​ ​ ​ If you want to preserve the number of solutions, then insert
clauses of the form ​ x or not x ​ for each variable x. ​ ​ ​ Other than that, the elements are
the clauses, and each set is the set of clauses in which the corresponding literal occurs.

your problem ​ $\to$ ​ CNF-SAT ​ ​ ​ :

There is one variable per pair-of-sets, and one clause per element.
For each element x and variable i, ​ ​ ​ ​ ​ ​ ​ not i ​ is in x's clause if and only if x is in $S^i_0$ ​ ​ ​
and ​ ​ ​ (the positive literal) i ​ is in x's clause if and only if x is in $S^i_1$ ​ ​ ​ .

| cite | improve this answer | |

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.