NP-hardness of maximum set cover with even/odd coverage requirement

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?

One can rephrase your question as follows:


Given a matrix $A$ and a vector $b$ over $GF(2)$, find a vector $x$ of weight $k$ such that $|Ax-b|$ is as small as possible.

A very similar problem was shown to be NP-complete by Stadnicki on cstheory:


Given a matrix $A$ and a vector $b$ over $GF(2)$, does there exist a vector $x$ of weight at most $k$ such that $Ax = b$?

This implies that your problem is intractable as well.

StackExchange Computer Science Q#60593, answer score: 3