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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.