Apa variasi berikut pada Set Cover yang dikenal sebagai?

15

Apa variasi berikut pada penutup yang dikenal sebagai?

Diberikan himpunan S, kumpulan C himpunan bagian dari S dan bilangan bulat positif K, apakah ada set K di C sehingga setiap pasangan elemen S terletak di salah satu himpunan bagian yang dipilih.

Catatan: Tidak sulit untuk melihat bahwa masalah ini adalah NP-Lengkap: Diberikan masalah penutup normal (S, C, K), buat tiga salinan S, katakan S ', S' ', dan S' '', lalu buat himpunan bagian Anda sebagai S '' ', | S | himpunan bagian dari bentuk {a '} U {x dalam S' '| x! = a} U {a '' '}, | S | himpunan bagian dari bentuk {a ''} U {x dalam S '| x! = a} U {a '' '}, {a', a '' | a di C_i}. Kemudian kita bisa menyelesaikan masalah set cover dengan subset K jika kita bisa menyelesaikan masalah cover pasangan dengan K + 1 + 2 | S | himpunan bagian.

Ini digeneralisasikan menjadi tiga kali lipat, dll. Saya ingin tidak membuang-buang setengah halaman untuk membuktikan ini, dan mungkin tidak cukup jelas untuk dianggap sepele. Tentu saja cukup bermanfaat bahwa seseorang telah membuktikannya, tetapi saya tidak tahu siapa atau di mana.

Juga, apakah ada tempat yang baik untuk mencari hasil Kelengkapan NP yang tidak di Garey dan Johnson?

np-hardness set-cover cc.complexity-theory Deinst
sumber

Jawaban:

7

Untuk menjawab pertanyaan kedua Anda, ringkasan Kahn-Crescenzi hasil kekerasan-NP adalah sumber yang berharga untuk hasil kekerasan, dan juga mencakup banyak varian masalah inti G&J. T ia masuk untuk set penutup adalah contoh yang baik dari ini.

Suresh Venkat
sumber
2
Saya telah melihat itu sebelumnya, dan ya, itu membantu, tetapi bahkan tidak mulai menggaruk permukaan NP-Complete yang telah terbukti. Untuk memberikan contoh lain, perlu waktu lebih lama bagi saya untuk menemukan bukti Uehara bahwa Vertex Cover adalah NP-lengkap pada grafik 3 planar kubik yang terhubung daripada yang saya perlukan untuk membuktikannya. (Buktinya jauh lebih bersih daripada milikku.)
deinst
7

Kedengarannya seperti Anda menggeneralisasi set penutup untuk mempertimbangkan tidak hanya elemen S, tetapi setiap subset ukuran-M dari S. Kita dapat menyatakan masalah secara lebih umum:

"Diberikan himpunan S, kumpulan C himpunan bagian himpunan S dan bilangan bulat positif m, berapakah jumlah terkecil elemen C sehingga setiap himpunan ukuran-M S terletak pada salah satu elemen C yang dipilih?"

Ini benar-benar mengejutkan saya sebagai generalisasi set cover yang cukup jelas, dan bukan yang Anda perlukan untuk membuktikan NP-complete melampaui satu baris. Lagi pula, memilih m = 1 memulihkan masalah set penutup asli. Mungkin formulasi yang lebih umum ini cukup baik untuk tujuan Anda sehingga tidak perlu masuk ke dalam rincian?

Pertanyaan Anda tentang serangkaian hasil kelengkapan NP yang diperbarui adalah pertanyaan yang bagus, dan pantas untuk pertanyaan sendiri. Crescenzi dan Kann telah menyusun ringkasan yang bermanfaat secara online di sini .

Kedua, ini hampir tidak menyebar, tetapi Manual Perancangan Algoritma oleh Steven Skiena seringkali merupakan perhentian pertama yang berguna untuk sejumlah besar masalah, dan tersedia secara online sebagian .

Anand Kulkarni
sumber
Saya hanya tertarik pada m = 2. Mungkin ada bukti satu baris, tetapi kata bukti lolos dari saya. Saya yakin saya menyatakan hal itu dengan jelas dalam kalimat kedua dari pertanyaan itu.
deinst
Permintaan maaf; Saya tidak bermaksud menyarankan bahwa ada bukti singkat dalam kasus berpasangan! Bukti satu baris yang saya sarankan hanya dalam versi umum masalah: "kasus khusus m = 1 memulihkan penutup set standar". Seperti yang Anda tunjukkan, bukti dalam case berpasangan jelas (perkenalkan elemen dummy dan set ke set penutup standar untuk menghasilkan set cover berpasangan), tapi ya, akan butuh beberapa baris untuk menunjukkannya menjadi formal. Saya akan melihat apakah saya dapat menemukan referensi untuk itu dalam literatur.
Anand Kulkarni