Najmniejszy zestaw nie zawarty w kolekcji zestawów

Ze względu na wejściu liczba całkowita $n$ i zestaw $S$ zestawów elementów $\{1, ..., n\}$ , co jest złożoność znalezienia zestawu $T$ z elementami $\{1, ..., n\}$ takie, że $T$ ma minimalną liczność, a $T$ jest zawarty w żadnym zestawie $S$ ?

$[n] = \{ 1, 2, \dotsc, n \}$$\mathcal{F} = \{S_1, S_2, \dotsc, S_m \} \subseteq 2^{[n]}$$T \subseteq [n]$ i = 1 , 2 , … , $T \not\subseteq S_i$$i = 1, 2, \dotsc, m$

Aby odpowiedzieć na twoje pytanie, zwróć uwagę, że wtedy i tylko wtedy, gdy . Oznacza to, że musi przecinać dopełnienie każdego . Ale to oznacza, że ​​twój problem jest w zasadzie równoważny problemowi z zestawem uderzeń (rozważ uderzenie zestawu z wejściem ): T ∩ ( [ n ] ∖ S i ) ≠ ∅ T S i G = { [ n ] ∖ S i : i = 1 , 2 , … , m $T \not\subseteq S_i$$T \cap ([n] \setminus S_i) \not= \emptyset$$T$$S_i$$\mathcal{G} = \{ [n] \setminus S_i \ \colon \ i = 1, 2, \dotsc, m \}$

Zestaw uderzeniowy. Biorąc pod uwagę zestaw rodziny i liczbę całkowitą , czy istnieje zestaw z i dla wszystkich ?$\mathcal{F} \subseteq 2^{[n]}$$k$$T \subseteq [n]$$|T| \le k$$T \cap S \not= \emptyset$$S \in \mathcal{F}$

Zestaw uderzeń jest znany jako NP-kompletny i nie można, luźno mówiąc, rozwiązać szybciej niż w czasie chyba że hipoteza silnego czasu wykładniczego zawiedzie.$O(2^n)$

Problem jest równoważny problemowi z pokrywą / problemem z zestawem uderzeniowym:

Biorąc pod uwagę rodzinę podzbiorów , znajdź zestaw o minimalnym możliwym rozmiarze, który przecina każdy zestaw w rodzinie .$\cal F$$\{1,\dots, n\}$$T \subset \{1,\dots, n\}$$\cal F$

Twój problem jest równoważny Problemowi Uderzenia Zestawu, ponieważ nie znajduje się w żadnym zestawie w wtedy i tylko wtedy, gdy przecina każdy zestaw w . (Aby rozwiązać przykład problemu z zestawem uderzeń, wystarczy rozwiązać problem z .)$T$$S$${\cal F} = \{\bar A: A\in S\}$$S = \{\bar A: A\in {\cal F}\}$

Problem zestawu uderzeń jest trudny do wykonania [Karp '72]. Istnieje dla niego algorytm aproksymacji i twardość dopasowywania wyniku aproksymacji [Lund, Yannakakis '94, Feige '98].$O(\log n)$