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 2
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 = 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?
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.
sumber
Jawaban:
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.
sumber