Set terkecil tidak termasuk dalam koleksi set

Diberikan sebagai input bilangan bulat dan himpunan dari himpunan elemen , apa kompleksitas menemukan himpunan elemen dari sedemikian sehingga memiliki kardinalitas minimal dan tidak termasuk dalam set ?$n$$S$$\{1, ..., n\}$$T$$\{1, ..., n\}$$T$$T$$S$

Biarkan , dan biarkan menjadi input mengatur keluarga. Kecuali saya salah paham perumusan masalah Anda, kami ingin menemukan set ukuran minimum sehingga untuk semua i = 1, 2, \ dotsc, m .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$

Untuk menjawab pertanyaan Anda, perhatikan bahwa $T \not\subseteq S_i$ jika dan hanya jika $T \cap ([n] \setminus S_i) \not= \emptyset$ . Artinya, $T$ harus memotong masing-masing $S_i$ . Tetapi ini berarti bahwa masalah Anda, pada dasarnya, setara dengan masalah hitting set (pertimbangkan memukul set dengan input $\mathcal{G} = \{ [n] \setminus S_i \ \colon \ i = 1, 2, \dotsc, m \}$ ):

Hitting Set. Diberikan keluarga himpunan $\mathcal{F} \subseteq 2^{[n]}$ dan integer $k$ , apakah ada himpunan $T \subseteq [n]$ dengan $|T| \le k$ dan $T \cap S \not= \emptyset$ untuk semua $S \in \mathcal{F}$ ?

Hitting set dikenal sebagai NP-lengkap dan tidak dapat, secara longgar, diselesaikan lebih cepat daripada dalam waktu kecuali Hipotesis waktu Eksponensial Kuat gagal.$O(2^n)$

Masalahnya sama dengan Set Cover Problem / Hitting Set Problem:

Diberikan keluarga himpunan bagian dari , temukan himpunan dengan ukuran seminimal mungkin yang memotong setiap set dalam keluarga .{ 1 , ... , n } T ⊂ { 1 , ... , n } $\cal F$$\{1,\dots, n\}$$T \subset \{1,\dots, n\}$$\cal F$

Masalah Anda setara dengan Masalah Hitting Set karena tidak terletak pada set apa pun dalam jika dan hanya jika itu memotong setiap set dalam . (Jadi untuk memecahkan contoh Masalah Set Menekan, cukup untuk memecahkan contoh masalah Anda dengan .)$T$$S$${\cal F} = \{\bar A: A\in S\}$$S = \{\bar A: A\in {\cal F}\}$

Masalah Hitting Set adalah NP-hard [Karp '72]. Ada algoritma aproksimasi untuknya dan kekerasan yang cocok dengan hasil pendekatan [Lund, Yannakakis '94, Feige '98].$O(\log n)$