Memukul set keluarga berpotongan berpasangan

Sebuah set memukul dari keluarga adalah bagian dari sehingga untuk . Masalah untuk menemukan set minimum memukul keluarga yang diberikan adalah NP-hard secara umum, karena itu menggeneralisasi masalah vertex cover. Sekarang pertanyaan saya adalah:H ⋃ n i = 1 S i H ∩ S i ≠ ∅ 1 ≤ i ≤ $\mathcal{S} = \{S_1, \dots, S_n\}$$H$$\bigcup_{i=1}^{n} S_i$$H \cap S_i \ne \emptyset$$1 \le i \le n$

Apakah masalah hitting set tetap NP-keras ketika elemen $\mathcal{S}$ berpasangan berpotongan?

Saya juga tertarik pada kekerasan perkiraan (atau traktabilitas) dari masalah ini.

Jawabannya adalah ya - masalahnya masih NP-Lengkap. untuk setiap set buat elemen palsu dan buat set baru S_i' = S_i \ cup \ {e_i '\} dan S_i' '= S_i \ cup \ {e_i' '\}} . Sangat mudah untuk memverifikasi bahwa hitting set dari sistem lama adalah hitting set dari sistem baru. Selain itu, kecuali untuk elemen palsu, setiap elemen sekarang mencapai setidaknya tiga set.e ′ i , e ″ i S ′ i = S i ∪ { e ′ i } S ″ i = S i ∪ { e ″ i$S_i$$e_i', e_i''$$S_i' = S_i \cup \{ e_i'\}$$S_i'' = S_i \cup \{e_i''\}$

Selanjutnya, untuk setiap pasangan set dalam sistem baru (sebut saja $T_i$ dan $T_j$ untuk menghindari kebingungan), buat elemen palsu $x_{ij}$ dan tambahkan ke $T_i$ dan $T_j$ . Jelas, dalam sistem himpunan yang dihasilkan, semua himpunan berpasangan berpasangan, tetapi hitting set optimal asli masih set hitting optimal untuk sistem terbaru ini.

Tanpa batasan lebih lanjut, masalahnya tampak sekeras masalah aslinya.

BTW, membuktikan bahwa memang solusi optimal tidak akan menggunakan elemen palsu tidak sepele. Pertama, kita dapat mengasumsikan bahwa hitting set yang diberikan untuk sistem baru tidak termasuk atau , karena jika tidak kita dapat memindahkan elemen ke elemen asli set, dan mendapatkan set pukulan dengan ukuran yang sama. Ini sedikit lebih halus untuk melihat mengapa elemen tidak dalam set memukul optimal. Karena membosankan, saya hanya akan meninggalkan petunjuk: membangun grafik yang menghubungkan dua set dan dalam sistem asli jika menghubungkan dua set yang diturunkan dari set ini. Berargumen bahwa grafik ini dalam hitting set minimal harus$e_i'$$e_i''$$x_{ij}$$S_i$$S_j$$x_{ij}$$3$teratur, dan dengan demikian jumlah tepi di dalamnya benar-benar melebihi jumlah set yang ada sebagai simpul. Dengan demikian, seseorang dapat menemukan set pukulan yang lebih kecil untuk set ini.