# For each given set choosing either it or its complement such that their union exactly has a given size

Given an integer $$k$$ and $$n$$ sets $$A_1,\ldots,A_n$$, denote $$U=A_1\cup A_2\cup\cdots\cup A_n$$, $$A_i^0=A_i$$ and $$A_i^1=U\backslash A_i$$. The problem asks whether there exists $$(b_1,\ldots, b_n)\in\{0,1\}^n$$ such that

$$\left|\bigcup_{i=1}^nA_i^{b_i}\right|=k.$$

Is this problem NP-complete?

• the space is $2^n$, right? – kelalaka Oct 7 '18 at 18:29
• I am not able to recall, but can you tell us whether the problem without the complement of each set is NP-complete? – Apass.Jack Oct 7 '18 at 19:36
• @kelalaka Yes, of course. – xskxzr Oct 8 '18 at 2:27
• @Apass.Jack Yes, it is NP-complete. – xskxzr Oct 8 '18 at 2:30

If $$k=|U|$$, this problem is exactly another wording for SAT where each clause contains all variables. More precisely, for each element $$j\in U$$, let $$l_{ij}=b_i$$ if $$j\notin A_i$$ while $$l_{ij}=\neg b_i$$ otherwise. The problem is exactly to satisfy the clauses $$l_{1j}\vee l_{2j}\vee\cdots \vee l_{nj}$$ for all $$j$$. If all possible clauses are involved in, the answer is certainly NO. Otherwise, without loss of generality, say one missing clause is $$b_1\vee\cdots\vee b_n$$, we can set $$b_1=\cdots=b_n=0$$ to satisfy all other clauses, thus the answer is YES.
If $$k<|U|$$, then at least one element should not be included in the union. We can test for each element: if this element is not included in the union, we can determine for each set whether it or its complement should be chosen, then we can see whether their union exactly has size $$k$$.