# Is this a variant of the set cover problem?

$$\textbf{Decision Problem:}$$

Given a finite set of elements $$E$$ and a collection $$C$$ of non empty sets, $$C=\{E_1,...,E_n\}$$, such that each $$E_i$$ covers at least one element of $$E$$. The goal is to check whether there exists at least one combination of elements in $$C$$ that yields exactly the same content of $$E$$. The combination can be done with the following operations: $$Union (\cup)$$, $$Intersection (\cap)$$ and Difference $$(\backslash)$$.

I would like to know if this is a variant of the set cover problem or some other problem, and also, if this problem is NPC.

$$\textbf{Note:}$$ There is no minimization to do here, I just want to check whether the subsets of $$C$$ can cover in some way all elements of $$E$$.

$$\textbf{Example 1:}$$

$$E=\{1,2,3,4\}, C=\{E_1,E_2,E_3,E_4\}$$ with $$E_1=\{1,2,3\}, E_2=\{3,4\}, E_3=\{1,2,3,4,5\}, E_4=\{5,6,7\}.$$ Thus, two solutions exist: $$E_1 \cup E_2$$ and $$E_3\backslash E_4$$.

$$\textbf{Example 2:}$$

$$E=\{1,2,3,4\}, C=\{E_1,E_2,E_3\}$$ with $$E_1=\{1,2,3\}$$, $$E_2=\{3,4,5\}$$, $$E_3=\{5,6,7\}$$. The solution is given by $$(E_1 \cup E_2)\backslash E_3$$.

• Wait, if each set $E_i$ is a subset of $E$ (per your first sentence), then isn't the answer yes iff $E =\bigcup_i E_i$? Oh, I see in your example that you intend to allow $E_i \not\subseteq E$. Maybe fix your first sentence? Dec 22, 2021 at 13:56
• Your problem seems to be in $P$. Define two elements $x$ and $y$ to be equivalent if they are in exactly the same sets, that is $\{i : x\in E_i\} = \{i : y\in E_i\}$. Then the answer is no iff there are two equivalent elements $x$ and $y$ such that $x\in E$ but $y\not\in E$. (If there are two such elements the answer is no because no sequence of operations can "separate" $x$ and $y$. I'll leave the converse as an exercise for the reader, with the hint that given any "formable" set, if it contains $x$ and $y$ such that $x\not\equiv y$, there is an operation that removes $y$ but not $x$. :-) Dec 22, 2021 at 14:09