Pick elements that don't exhaust any set

Question

The following is an NP-Complete problem:

---

Suppose you have a collection $\mathcal{C}$ of sets, so that $A_i\in \mathcal{C}$ and $A_i$ is some set--we can suppose the elements of $A_i$ are integers. We want some $k$ integers, say $X \subseteq \bigcup_{A_i\in \mathcal{C}}A_i$ where $X$ has $k$ elements, and subject to the constraint that $A_i \not\subseteq X$ for any $A_i \in \mathcal{C}$.

---

I primarily am curious whether this is a named problem and if so, what is it's name? I've already figured out how to show that it's NP-Complete by reduction to the Independent Set problem. However I am curious to get some more context to this problem, so I wanted to research it a bit. But I can't find it referenced anywhere.

Answer 1

This is the hitting set problem in disguise.

Let $U=\cup_{A_i \in \mathcal{C}} A_i$ be the universe and $\overline{X} = U \setminus X$. Then your problem can be equivalently stated as follows: given $\mathcal{C}$ and $k$, find $\overline{X}$ that has $|U|-k$ elements, and such that $A_i \cap \overline{X} \ne \emptyset$ for each $A_i \in \mathcal{C}$. That is exactly the hitting set problem.