Set cover by alternative of sets 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$ ​ ​ ​ .