$\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$.

  • 1
    $\begingroup$ 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? $\endgroup$
    – Neal Young
    Commented Dec 22, 2021 at 13:56
  • $\begingroup$ 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$. :-) $\endgroup$
    – Neal Young
    Commented Dec 22, 2021 at 14:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.