Menunjukkan bahwa penghapusan vertex minimal ke grafik bipartit adalah NP-complete

Pertimbangkan masalah berikut yang input instansinya adalah grafik sederhana dan bilangan bulat alami . $G$ $k$

Apakah ada himpunan sehingga adalah bipartit dan ? $S \subseteq V(G)$ $G - S$ $|S| \leq k$

Saya ingin menunjukkan bahwa masalah ini adalah -complete dengan mengurangi 3-SAT, CLIQUE, -DOMINATING SET atau -VERTEX COVER untuk itu. $\rm{NP}$ $k$ $k$ $k$

Saya percaya saya bisa mengurangi masalah 3-WARNA itu jadi saya hanya perlu melihat bagaimana mengurangi salah satu masalah yang disebutkan untuk itu. Tetapi karena itu akan agak berantakan saya bertanya-tanya apakah seseorang melihat pengurangan yang elegan untuk masalah yang disebutkan di atas.

Juga, apakah ada nama untuk masalah keputusan ini?

complexity-theory np-complete reductions Jernej
sumber

Transversal Ganjil .

Pål GD

Ini tampaknya mirip dengan set vertex umpan balik . Artinya, Anda ingin menemukan subset minimum dari simpul untuk menghapus sedemikian rupa sehingga grafik yang dihasilkan adalah asiklik. Grafik asiklik adalah definisi pohon (atau hutan) yang bipartit.

Nicholas Mancuso

@NicholasMancuso Tidak begitu mirip. Ini benar-benar seperti yang saya katakan di atas, masalah Transversal Ganjil Siklus. Atau seperti yang ditunjukkan Vor, disebut penghapusan Bipartite (atau vertex) oleh Yannakakis pada tahun 70an dan 80an.

Pål GD

@ PålGD, saya setuju. Saya merasa bahwa pengurangan termudah adalah dari FVS. Namun, itu dibuat tidak perlu dengan definisinya sebagai Odd Cycle Transversal.

Nicholas Mancuso

@Jernej: Anda berkata "... Saya ingin menunjukkan bahwa masalah ini ada di NP dengan menguranginya menjadi 3-SAT, k-CLIQUE, ...". Apakah maksud Anda "Saya ingin menunjukkan bahwa masalah ini NP-hard menggunakan pengurangan dari 3-SAT, k-CLIQUE, ..."? (masalahnya jelas dalam NP karena pengujian jika grafik bipartit dapat dilakukan dalam waktu linier)

Vor

Jawaban:

Masalah Anda adalah kasus khusus dari kelas masalah yang lebih luas bernama masalah penghapusan-simpul :

JM Lewis dan M. Yannakakis, "Masalah penghapusan-simpul untuk sifat turunan adalah NP-complete"

... Makalah ini membahas kelas masalah grafik yang didefinisikan sebagai berikut:
untuk properti grafik tetap , temukan jumlah minimum simpul (atau simpul) yang harus dihapus dari grafik diberikan sehingga hasilnya memuaskan . Kami menyebutnya masalah penghapusan simpul untuk . Hasil kami menunjukkan bahwa jika adalah properti nontrivial yang diturunkan pada subgraph yang diinduksi, maka masalah penghapusan-simpul untuk adalah NP-hard. Selanjutnya, jika kita menambahkan syarat bahwa pengujian untuk $\Pi$ $G$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ dapat dilakukan dalam waktu polinomial, maka hasil kami menyiratkan bahwa masalah penghapusan node untuk adalah NP-lengkap. ... $\Pi$

Masalah Anda adalah masalah penghapusan simpul untuk bipartiteness , tetapi (seperti dicatat oleh Pal), sekarang dikenal sebagai masalah Odd cycle traversal (OCT).

EDIT

Untuk apa pengurangan langsung, saya memikirkan yang ini dari 3SAT.

Diberikan instance 3SAT dengan variabel dan klausa , buat grafik berikut: tambahkan dua node untuk setiap variabel dan keunggulan di antara mereka. Untuk mensimulasikan tugas kebenaran, tambahkan node untuk setiap variabel dan hubungkan keduanya ke dan ; dengan cara ini, untuk membuat grafik bipartit menghapus paling banyak node, setidaknya satu antara dan harus dihapus. Akhirnya untuk setiap klausa $n$ $m$ $x_i, \overline{x_i}$ $n+1$ $x_i$ $x_i$ $\overline{x_i}$ $n$ $x_i$ $\overline{x_i}$ tambahkan 4 node dan membangun sebuah siklus aneh yang menghubungkan variabel dalam . $C_j$ $C_j$

Grafik dihasilkan dapat dibuat bipartit menghapus paling banyak node jika dan hanya jika rumus 3SAT asli memuaskan. $G$ $n$

masukkan deskripsi gambar di sini

Vor
sumber

Ini sebenarnya bukan jawaban pertanyaan yang diajukan. OP ingin mengurangi secara eksplisit menggunakan masalah yang diberikan. Selain itu, masalahnya sekarang dikenal sebagai Odd Cycle Transversal.

Pål GD

@ PålGD: Anda benar.

Vor

Ya, tapi saya tidak bisa langsung melihat pengurangan dari daftar masalah OP, meskipun ... Saya hanya tahu yang Anda sebutkan, oleh Yannakakis.

Pål GD

@ PålGD: Saya akan memikirkan pengurangan yang berbeda, tetapi jujur saja saya tidak yakin apa yang sebenarnya diinginkan OP (lihat komentar saya di atas).

Vor

@Vor Apa yang saya inginkan adalah melihat pengurangan sederhana menjadi satu dari salah satu masalah yang disebutkan. Artikel ini diketahui oleh saya tetapi saya agak mencari pengurangan paling langsung.

Jernej