# Pick elements that don't exhaust any set

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.

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.