Smallest set not included in a collection of sets

Given as input an integer $n$ and a set $S$ of sets of elements of $\{1, ..., n\}$, what is the complexity of finding a set $T$ of elements of $\{1, ..., n\}$ such that $T$ has minimal cardinality and $T$ is included in none of the sets of $S$?

• both answers so far mention hitting sets. note that hitting sets also show up in hypergraphs, called the transversal, and CNF$\leftrightarrow$DNF conversion of monotone boolean formulas.
– vzn
Dec 21 '12 at 16:36

Let $[n] = \{ 1, 2, \dotsc, n \}$, and let $\mathcal{F} = \{S_1, S_2, \dotsc, S_m \} \subseteq 2^{[n]}$ be the input set family. Unless I misunderstood your problem formulation, we want to find a minimum-size set $T \subseteq [n]$ such that $T \not\subseteq S_i$ for all $i = 1, 2, \dotsc, m$.

To answer your question, note that $T \not\subseteq S_i$ if and only if $T \cap ([n] \setminus S_i) \not= \emptyset$. That is, $T$ has to intersect the complement of each $S_i$. But this means that your problem is, essentially, equivalent to the hitting set problem (consider hitting set with input $\mathcal{G} = \{ [n] \setminus S_i \ \colon \ i = 1, 2, \dotsc, m \}$):

Hitting Set. Given a set family $\mathcal{F} \subseteq 2^{[n]}$ and integer $k$, does there exists a set $T \subseteq [n]$ with $|T| \le k$ and $T \cap S \not= \emptyset$ for all $S \in \mathcal{F}$?

Hitting set is known to be NP-complete and cannot be, loosely speaking, solved faster than in time $O(2^n)$ unless the Strong Exponential-time Hypothesis fails.

• Ah, I did think about hitting set, but I hadn't seen the reduction. Thanks!
– a3nm
Dec 20 '12 at 16:07

The problem is equivalent to the Set Cover Problem / Hitting Set Problem:

Given a family $\cal F$ of subsets of $\{1,\dots, n\}$, find a set $T \subset \{1,\dots, n\}$ of minimal possible size that intersects every set in the family $\cal F$.

Your problem is equivalent to the Hitting Set Problem since $T$ does not lie in any set in $S$ if and only if it intersects every set in ${\cal F} = \{\bar A: A\in S\}$. (So to solve an instance of the Hitting Set Problem, it suffices to solve the instance of your problem with $S = \{\bar A: A\in {\cal F}\}$.)

The Hitting Set problem is NP-hard [Karp' 72]. There is an $O(\log n)$ approximation algorithm for it and a matching hardness of approximation result [Lund, Yannakakis '94, Feige '98].