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

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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}\}$.)</p>

<p>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].</p>

CC BY-SA 3.0
2012-12-20T15:53:07.087Z
2012-12-20T15:53:07.087Z
Yury
<p>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$.</p>

<p>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  \}$):</p>

<blockquote>
  <p><strong>Hitting Set.</strong>
  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}$?</p>
</blockquote>

<p>Hitting set is known to be NP-complete and <a href="http://arxiv.org/abs/1112.2275">cannot be, loosely speaking, solved faster than</a> in time $O(2^n)$ unless the Strong Exponential-time Hypothesis fails.</p>

CC BY-SA 3.0
2012-12-20T16:07:14.650Z
Ah, I did think about hitting set, but I hadn't seen the reduction. Thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-12-20T15:51:06.063Z
2012-12-20T15:51:06.063Z
Janne H. Korhonen
<p>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$?</p>

CC BY-SA 3.0
2012-12-21T16:36:54.070Z
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
<cc.complexity-theory><ds.algorithms>
Smallest set not included in a collection of sets
Antoine Amarilli 'a3nm'
# Smallest set not included in a collection of sets

(Asked by: username_0 on 2012-12-20)

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$?

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2012-12-20. Score: 16 | Accepted answer

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](http://arxiv.org/abs/1112.2275) in time $O(2^n)$ unless the Strong Exponential-time Hypothesis fails.

> **Comments:**
> **username_0**: Ah, I did think about hitting set, but I hadn't seen the reduction. Thanks!  

---

### Answer by username_2 on 2012-12-20. Score: 11

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].


---

