<p><span class="math-container">$\textbf{Decision Problem:}$</span></p>
<p>Given a finite set of elements <span class="math-container">$E$</span> and a collection <span class="math-container">$C$</span> of non empty sets, <span class="math-container">$C=\{E_1,...,E_n\}$</span>, such that each <span class="math-container">$E_i$</span> covers at least one element of <span class="math-container">$E$</span>. The goal is to check whether there exists at least one combination of elements in <span class="math-container">$C$</span> that yields exactly the same content of <span class="math-container">$E$</span>. The combination can be done with the following operations: <span class="math-container">$Union (\cup)$</span>, <span class="math-container">$Intersection (\cap)$</span> and Difference <span class="math-container">$(\backslash)$</span>.</p>
<p>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.</p>
<p><span class="math-container">$\textbf{Note:}$</span> There is no minimization to do here, I just want to check whether the subsets of <span class="math-container">$C$</span> can cover in some way all elements of <span class="math-container">$E$</span>.</p>
<p><span class="math-container">$\textbf{Example 1:}$</span></p>
<p><span class="math-container">$E=\{1,2,3,4\}, C=\{E_1,E_2,E_3,E_4\}$</span> with <span class="math-container">$E_1=\{1,2,3\}, E_2=\{3,4\}, E_3=\{1,2,3,4,5\}, E_4=\{5,6,7\}.$</span> Thus, two solutions exist: <span class="math-container">$E_1 \cup E_2$</span> and <span class="math-container">$E_3\backslash E_4$</span>.</p>
<p><span class="math-container">$\textbf{Example 2:}$</span></p>
<p><span class="math-container">$E=\{1,2,3,4\}, C=\{E_1,E_2,E_3\}$</span> with <span class="math-container">$E_1=\{1,2,3\}$</span>, <span class="math-container">$E_2=\{3,4,5\}$</span>, <span class="math-container">$E_3=\{5,6,7\}$</span>. The solution is given by <span class="math-container">$(E_1 \cup E_2)\backslash E_3$</span>.</p>

CC BY-SA 4.0
2021-12-22T13:56:17.763Z
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?
Neal Young
CC BY-SA 4.0
2021-12-22T14:09:07.177Z
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$. :-)
Neal Young
<combinatorics><set-theory><subset-sum><covering-problems>
Is this a variant of the set cover problem?
mahou_2019
# Is this a variant of the set cover problem?

(Asked by: username_0 on 2021-12-22)

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

**Tags:** combinatorics, set-theory, subset-sum, covering-problems
> **Comments:**
> **username_1**: 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?  
> **username_1**: 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$. :-)  

---

## 0 answers

