Conjunto menor não incluído em uma coleção de conjuntos

Dado como entrada um número inteiro e um conjunto de conjuntos de elementos de , qual é a complexidade de encontrar um conjunto de elementos de tal que tem cardinalidade mínima e está incluído em nenhum dos conjuntos de ?$n$$S$$\{1, ..., n\}$$T$$\{1, ..., n\}$$T$$T$$S$

Seja e seja a entrada definir família. A menos que eu tenha entendido mal a formulação do seu problema, queremos encontrar um conjunto de tamanho mínimo tal que para todos .F = { S 1 , S 2 , ... , S m } ⊆ 2 [ n ] T ⊆ [ n ] T ⊈ S i i = 1 , 2 , ... , $[n] = \{ 1, 2, \dotsc, n \}$$\mathcal{F} = \{S_1, S_2, \dotsc, S_m \} \subseteq 2^{[n]}$$T \subseteq [n]$$T \not\subseteq S_i$$i = 1, 2, \dotsc, m$

Para responder sua pergunta, observe que $T \not\subseteq S_i$ se e somente se $T \cap ([n] \setminus S_i) \not= \emptyset$ . Ou seja, $T$ tem que cruzar o complemento de cada $S_i$ . Mas isso significa que seu problema é, essencialmente, equivalente ao problema do conjunto de ocorrências (considere acertar com a entrada $\mathcal{G} = \{ [n] \setminus S_i \ \colon \ i = 1, 2, \dotsc, m \}$ ):

Batendo Set. Dada uma família de conjuntos $\mathcal{F} \subseteq 2^{[n]}$ e um número inteiro $k$ , existe um conjunto $T \subseteq [n]$ com $|T| \le k$ e $T \cap S \not= \emptyset$ para todos os $S \in \mathcal{F}$ ?

Sabe-se que o conjunto de batidas é NP-completo e não pode ser, de maneira geral, resolvido mais rapidamente que no tempo , a menos que a Hipótese de Tempo Exponencial Forte falhe.$O(2^n)$

O problema é equivalente ao Problema na Tampa do Conjunto / Problema no Conjunto de Bater:

Dada uma família de subconjuntos de , encontre um conjunto de tamanho mínimo possível que cruze todos os conjuntos na família .$\cal F$$\{1,\dots, n\}$$T \subset \{1,\dots, n\}$$\cal F$

Seu problema é equivalente ao Problema do Conjunto de Acertos, pois não está em nenhum conjunto em se, e somente se, cruza todos os conjuntos em . (Portanto, para resolver uma instância do Problema do Conjunto de Acertos, basta resolver a instância do seu problema com .)$T$$S$${\cal F} = \{\bar A: A\in S\}$$S = \{\bar A: A\in {\cal F}\}$

O problema do Hitting Set é NP-difícil [Karp '72]. Existe um algoritmo de aproximação para ele e uma dureza correspondente do resultado da aproximação [Lund, Yannakakis '94, Feige '98].$O(\log n)$