Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 16 down vote accepted

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.

share|improve this answer
    
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].

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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