2
$\begingroup$

I am wondering if this problem has been studied, and in particular if there is an algorithm for it.

Consider a universe $\mathcal U$ and a set $A \subseteq U$, and a family of sets $\mathcal F \subset 2^{\mathcal U}$. We know that $$\mathcal U = \bigcup_{F \in \mathcal F} F.$$

I want to find a minimal set $\mathcal E \subseteq \mathcal F$ such that $$A = \triangle_{E \in \mathcal E} E$$ where $\triangle_{E \in \mathcal E} E$ means the symmetric difference of all the sets in $\mathcal E$.

The set family $\mathcal F$ is not closed under symmetric difference, but we know that for any $B \subseteq \mathcal U$, there exists a $\mathcal F' \subseteq \mathcal F$ such that $$B = \triangle_{F \in \mathcal F'} F,$$ so the problem is solvable.

I think the decision problem should be NP-hard.

Edit: The links in Kristoffer Arnsfelt Hansen's comments show that the problem of finding the smallest subset expressible as a symmetric difference of the subsets in $\mathbb F$ is NP-complete. This problem is somewhat different, and I am still looking for an algorithm.

$\endgroup$