Kekerasan NP dari masalah partisi grafik?

16

Saya tertarik dengan masalah ini: Diberi grafik tidak terarah , Apakah ada partisi ke dalam grafik dan sedemikian sehingga dan isomorfis?G G 1 ( E 1 , V 1 ) G 2 ( E 2 , V 2 ) G 1 G 2G(E,V)GG1(E1,V1)G2(E2,V2)G1G2

Di sini dipartisi menjadi dua set terpisah dan . Set dan tidak selalu terpisah. dan .E 1 E 2 V 1 V 2 E 1 E 2 = E V 1 V 2 = VEE1E2V1V2E1E2=EV1V2=V

Masalah ini setidaknya sama sulitnya dengan Masalah Grafik Isomorfisme. Saya kira ini lebih sulit daripada Grafik Isomorfisme tetapi tidak NP-keras.

Apakah ini masalah partisi -hard?NP

EDIT 3-3-2012: Diposting di MathOverflow .

EDIT 3-5-2012: Ternyata referensi dalam jawaban Diego adalah salah satu hasil yang tidak dipublikasikan. Setelah menggali, saya menemukan rujukan di Kolom NP-Completeness: An Ongoing Guide oleh David JOHNSON (halaman 8). Saya menemukan makalah lain yang mengutip hasil kelengkapan NP dari Graham dan Robinson sebagai tidak dipublikasikan.

Mohammad Al-Turkistany
sumber
1
Saya pikir maksud Anda dan , kalau tidak itu hanya dapat dipecahkan dalam dan saya menyebutkan ini karena Jika dan terpisah, penyatuan tidak mungkin benar dalam kasus umum (untuk tepian). V 1V 2 = V P V 1 V 2E1E2=EV1V2=VPV1V2
Saeed
@ Saeed, GI, yang tidak diketahui berada di P, dapat direduksi ke masalah ini.
Mohammad Al-Turkistany
1
Tampaknya terkait dengan permainan pelestarian simetri (lihat makalah Harary: "Strategi Simetris dalam Game Penghindaran Grafik", "Pada Panjangnya Permainan Melestarikan-Pelestarian Simetri pada Grafik") ... keduanya "terlalu jauh" dari level saya saat ini. keahlian :-(
Marzio De Biasi
1
Saya pikir Anda dapat mengasumsikan . V1=V2=V
Diego de Estrada
1
Jika , ada w V 2 - V 1 sejak | V 1 | = | V 2 | . Anda dapat menambahkan v ke V 2 dan w ke V 1 dan memetakannya dalam isomorfisme, karena mereka diisolasi dalam subgraph. vV1-V2wV2-V1|V1|=|V2|vV2wV1
Diego de Estrada

Jawaban:

7

Saya telah menemukan bahwa masalah ini NP-hard, bahkan terbatas pada pohon. Rujukannya adalah Graham dan Robinson, "faktorisasi isomorfik IX: bahkan pohon", tetapi saya tidak bisa mendapatkannya.

Diego de Estrada
sumber