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

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

<p>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}$?</p>

<p>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.</p>

<set-cover>
Set cover by alternative of sets
user168715
# Set cover by alternative of sets

(Asked by: username_0 on 2017-05-13)

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.

**Tags:** set-cover


---

## 0 answers

