Misalkan Anda diberi grafik yang terhubung, sederhana, tidak berarah H.
Masalah pemotongan bebas-H didefinisikan sebagai berikut:
Diberikan grafik sederhana, tidak terarah G, adakah potongan (partisi simpul menjadi dua set non-kosong, L, R) sedemikian rupa sehingga grafik yang diinduksi oleh set-potong (L dan R) keduanya tidak mengandung subgraph isomorfik ke H .
Sebagai contoh, ketika H adalah grafik dengan dua simpul yang terhubung oleh satu sisi, masalahnya sama dengan menentukan apakah grafik itu bipartit dan berada dalam P.
Dalam kasus H adalah segitiga, ini seperti versi vertex dari masalah Segitiga Monokromatik .
Saya pikir saya telah dapat menunjukkan bahwa ketika H-2-terhubung dengan setidaknya tiga simpul, masalah cut-H-bebas adalah NP-Lengkap.
Saya belum dapat menemukan referensi untuk masalah ini (dan hasilnya, apa pun).
Bisakah kita menghentikan kondisi 2-koneksi dan masih membuktikan NP-Completeness?
Adakah yang tahu tentang hasil yang diketahui yang menyiratkan hasil di atas atau hasil yang lebih kuat (atau Anda pikir mungkin relevan)?
Jawaban:
Anda bisa mencari istilah "bipartition" atau "partisi vertex" atau "pewarnaan" daripada "cut". Berbagai generalisasi dari bilangan kromatik di sepanjang garis yang Anda sebutkan telah dipertimbangkan sejak pertengahan 80-an (atau mungkin lebih awal). Ada beberapa referensi awal yang sulit ditemukan di konferensi kombinatorik Kanada, tetapi Anda mungkin ingin memeriksa Cowen, Goddard dan Jesurum (JGT atau SODA 1997) dan referensi / kutipan terkait.
Diedit 15/02/2011
Seperti yang ditunjukkan oleh Aravind dan Moron (dalam komentar di bawah), referensi berikut menunjukkan bahwa masalah bebas- adalah NP-hard kecuali dalam kasus-kasus sepele.H
D. Achlioptas. Kompleksitas colourability gratis. Matematika Terpisah. 165/166 (1997) 21-30. [pdf] .G
A. Farrugia. Partisi-vertikal ke dalam sifat herediter yang diinduksi aditif tetap adalah NP-hard. Elektron. J. Combin. 11 (2004) # R46 (9 pp).
sumber
Saya menyadari bahwa ini mungkin tidak langsung menjawab pertanyaan Anda (tentang referensi), tetapi saya ingin menguraikan pendekatan yang mungkin untuk menunjukkan kekerasan NP tanpa kondisi 2-terhubung. Ada dua hal yang hilang: satu adalah bukti dari NP-hardness dari 'masalah sumber', jadi untuk berbicara, dan yang lainnya adalah bahwa saya mengurangi ke versi 'berwarna' dari H-cut yang mungkin atau mungkin tidak bermanfaat. Adapun bottleneck pertama, saya percaya saya punya bukti dalam pikiran saya bahwa saya malas formalisasi, jadi saya berharap saya akan segera melakukannya. Saya telah memikirkan beberapa tentang mengurangi versi berwarna menjadi yang Anda presentasikan, dengan sedikit keberuntungan sejauh ini. Saya juga sangat ingin tahu tentang bukti Anda jika H-2 terhubung, bisakah Anda memberikan beberapa detail?
Jadi versi berwarna adalah sebagai berikut: setiap simpul dalam grafik dilengkapi dengan daftar warna dari palet P (set tetap, terbatas). Kita diharuskan menemukan potongan sehingga tidak ada partisi yang menginduksi salinan monokromatik H, yaitu, tidak ada subset dari | H | simpul yang menginduksi salinan H, dan daftar warna yang sesuai memiliki persimpangan tidak kosong.
Berikut adalah pengurangan dari varian terbatas d-SAT, di mana d adalah | H |. (Perhatikan bahwa ini jelas tidak akan berfungsi ketika d = 2).
Varian terbatas dari d-SAT adalah sebagai berikut:
Setiap klausa hanya memiliki literal positif atau negatif saja, izinkan saya merujuk klausa seperti klausa P dan klausa N masing-masing,
Setiap klausa P dapat dipasangkan dengan klausa N sehingga kedua klausa tersebut melibatkan set variabel yang sama.
(Saya punya ide tentang mengapa versi yang tampaknya terbatas ini mungkin sulit - pembatasan yang terkait sangat sulit, dan saya bisa membayangkan pengurangan dari sana, meskipun saya bisa dengan mudah keliru!)
Mengingat masalah ini, reduksi mungkin menunjukkan dirinya. Grafik memiliki titik untuk setiap variabel rumus. Untuk setiap klausa C_i, menginduksi salinan H pada set variabel yang berpartisipasi dalam klausa, dan menambahkan warna i ke set simpul ini. Ini menyelesaikan konstruksi.
Tugas apa pun secara alami berhubungan dengan pemotongan:
L = set semua variabel yang ditetapkan ke 0, R = set semua variabel yang ditetapkan ke 1.
Klaimnya adalah bahwa penugasan yang memuaskan sesuai dengan potongan bebas-H-monokromatik.
Dengan kata lain, (L, R), ketika diberikan oleh tugas yang memuaskan, akan sedemikian rupa sehingga L atau R tidak menginduksi salinan monokromatik dari H. Jika L memiliki salinan seperti itu, maka perhatikan bahwa klausa P yang sesuai harus memiliki semua variabelnya diatur ke 0, yang bertentangan dengan fakta bahwa tugasnya memuaskan. Sebaliknya, jika R memiliki salinan seperti itu, maka N-klausa yang sesuai harus memiliki semua variabelnya diatur ke 1, kontradiksi lagi.
Sebaliknya, pertimbangkan potongan apa pun, dan atur variabel di satu sisi ke 1 dan yang lain ke 0 (perhatikan bahwa tidak masalah ke arah mana Anda melakukannya - mengingat jenis rumus yang kami kerjakan, tugas dan itu terbalik versi setara sejauh kepuasan berjalan). Jika suatu klausa tidak puas dengan penugasan ini, maka kita dapat melacaknya kembali ke salinan monokromatik H di salah satu sisi, yang bertentangan dengan kemewahan monchromatic-H-cut.
Alasan seseorang harus menikmati pewarnaan adalah karena salinan H dapat mengganggu untuk membuat salinan palsu H yang tidak sesuai dengan klausa, dalam upaya pengurangan langsung. Memang, itu gagal - buruk - bahkan ketika H adalah sesuatu yang sederhana seperti jalan.
Saya tidak beruntung dalam menyingkirkan warna, dan saya tidak yakin bahwa saya telah membuat masalah lebih sederhana. Namun, saya berharap - jika benar - ini bisa menjadi awal.
sumber