Given universal set $U=X \cup Y = \{x_1, \ldots, x_{n_1} \} \cup \{y_1, \ldots, y_{n_2}\}$ where $X \cap Y = \emptyset$ and sets $\mathcal{S}=\{s_1, \ldots, s_m\}$ such that $s_i \subseteq U$ for all $i=1,\ldots,m$ and integer $k \in \mathbb{Z}^{+}$.
Find $\mathcal{C} \subseteq \mathcal{S}$ (denote $Z = \cup_{s \in \mathcal{C}} s$) that maximizes
$|\{ z \in Z \mid (z \in X \text{ and is covered even times by } \mathcal{C}) \text{ or } (z \in Y \text{ and is covered odd times by } \mathcal{C} )\}|$
s.t
- $|\mathcal{C}| = k$
In other words, we consider an element to be covered if it satisfies the odd/even coverage requirement according to its membership ($X$ or $Y$).
This problem differs from the standard maximum set cover in the definition of "covering an element".
Is this problem NP-hard? Is so, how to prove it?
