Jadi, masalah cover set sepele jika tidak ada set kandidat berpotongan satu sama lain.
Namun, bagaimana jika ukuran persimpangan untuk setiap pasangan calon paling banyak 1? Apakah ini masalah NP-hard?
Saya sangat menghargai wawasan apa pun.
Terima kasih, Garrett
Jawaban:
Jika saya tidak melewatkan sesuatu, Anda dapat menggunakan pengurangan dari SINGLE OVERLAP RESTRICTED EXVER COVER DENGAN 3 SETS (SINGLE OVERLAP RX3C) yang saya terbukti sebagai NPC dalam pertanyaan ini .
SAMPUL SAMPAI DENGAN TIGA SET (X3C):
Misalnya : Set dan koleksi C = { C 1 , . . . , C m } dari subset 3-unsur X . Pertanyaan : Apakah C berisi penutup yang tepat untuk X , yaitu subkoleksi C ′ ⊆ C sehingga setiap elemen X terjadi tepat pada satu anggota CX= { x1, x2, . . . , x3 q} C= { C1, . . . , Cm} X
X C' ⊆C X ?C'
X3C adalah NP-complete (lihat G&J), dan seperti yang ditunjukkan pada [1] itu tetap NP-complete bahkan jika setiap elemen terkandung dalam tepat 3 himpunan bagian C (COAT EKSPRES YANG DIPULIHKAN OLEH THREE SETS, RX3C).xi C
Saya membuktikan bahwa itu tetap melengkapi NP bahkan jika setiap pasangan himpunan bagian dalam berbagi paling banyak satu elemen; yaitu untuk semua i ≠ j , | C i ∩ C j | ≤ 1 (Saya menyebut versi terbatas ini SINGLE OVERLAP RX3C).C i≠j |Ci∩Cj|≤1
SET SAMPUL DENGAN dibatasi SIMPANG UKURAN 1 (versi keputusan) hanyalah sebuah generalisasi dari TUNGGAL OVERLAP RX3C, memang Anda dapat memilih alam semesta yang sama dan koleksi yang sama dari himpunan bagian C 1 , . . . C m dari TUNGGAL OVERLAP RX3C dan meminta penutup dengan q himpunan bagian atau kurang.X C1,...Cm q
Jelas penutup dengan himpunan bagian tidak bisa eksis karena setiap bagian mengandung tiga unsur dan ada 3 q elemen di X . Sebuah penutup dengan q subset harus sama persis: jika dua himpunan bagian mengandung unsur bersama maka ada kurang dari 3 q elemen tertutup.<q 3q X q 3q
[1] Teofilo F. Gonzalez: Clustering untuk Meminimalkan Jarak Intercluster Maksimum. Teor Komputasi. Sci. 38: 293-306 (1985).
sumber