Najmniejszy zestaw nie zawarty w kolekcji zestawów

14

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

cc.complexity-theory ds.algorithms

— a3nm
źródło

obie odpowiedzi do tej pory wspominają o uderzeniach. należy zauważyć, że zestawy uderzeń pojawiają się również w hipergraphach, zwanych przekrojami poprzecznymi i konwersji CNF

\leftrightarrow

$\leftrightarrow$ DNF monotonicznych wzorów boolowskich.

— vzn

16

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

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 \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)$

— Janne H. Korhonen
źródło

Ach, myślałem o uderzeniu w set, ale nie widziałem redukcji. Dzięki!

— a3nm

11

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

— Yury
źródło