14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vzn Dec 21 '12 at 16:36
16
$\begingroup$

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.

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

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

$\endgroup$

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.