Subgraf umum terbesar dari dua grafik planar maksimal

Pertimbangkan masalah berikut -

Mengingat maksimal planar grafik dan G 2 , menemukan graf G dengan jumlah maksimum tepi sehingga ada subgraph (tidak harus diinduksi) di kedua G 1 dan G 2 yang isomorfik ke G .$G_1$$G_2$$G$$G_1$$G_2$$G$

Bisakah ini dilakukan dalam waktu polinomial? Jika ya, lalu bagaimana?

Diketahui bahwa jika dan G 2 adalah grafik umum, maka masalahnya adalah NP-complete (karena G 1 bisa menjadi klik). Itu juga diketahui bahwa jika G 1 dan G 2 adalah pohon, atau dibatasi k-pohon parsial derajat, maka masalah dapat diselesaikan dalam waktu polinomial. Jadi bagaimana dengan case planar maksimal? Adakah yang tahu ini? Grafik isomorfisme pada dua graf planar maksimal adalah polinomial. Mungkin ini bisa membantu?$G_1$$G_2$$G_1$$G_1$$G_2$

Ini NP-complete, melalui versi modifikasi dari Wigderson yang digunakan untuk membuktikan bahwa Hamiltonicity grafik planar maksimal adalah NP-complete.

Pemeriksaan yang teliti terhadap bukti kelengkapan NP NP-nya Wigderson tahun 1982 untuk siklus Hamiltonian dalam grafik planar maksimal ( http://www.math.ias.edu/avi/node/820 ) menunjukkan bahwa instance yang dihasilkan oleh pengurangannya memiliki properti yang ada di sana. ada sisi sedemikian rupa sehingga ada siklus Hamiltonian melalui e atau tidak ada siklus Hamiltonian sama sekali. Misalnya, e dapat dipilih sebagai salah satu ujung dalam salah satu gadget M Wigderson.$e$$e$$e$$M$

Biarkan menjadi contoh keras dibangun dengan cara ini, dan embed G sehingga ujung e milik segitiga luar embedding. Connect banyak salinan grafik tertanam ini sehingga mereka e -edges membentuk suatu siklus, dan membuat hasil maksimal planar lagi dengan menambahkan dua simpul lagi, satu di setiap sisi siklus ini, terhubung ke semua simpul yang terbuka dari salinan G . Biarkan jumlah salinan menjadi c , dan memanggil grafik yang dihasilkan H . Biarkan n adalah jumlah simpul di G .$G$$G$$e$$e$$G$$c$$H$$n$$G$

Misalnya keras kami untuk subgraph umum terbesar akan menjadi pasangan di mana B adalah bipyramid dengan jumlah yang sama simpul sebagai H . Dengan demikian, subgraph umum yang optimal harus memasangkan semua simpul. Jika kita membuat c cukup besar, subgraf akan selalu memasangkan puncak bipyramid dengan dua simpul yang ditambahkan di H , karena derajatnya ( c dan 2 c ) akan cukup tinggi daripada setiap simpul lain di H , sehingga menambah derajat ini untuk ukuran solusi akan menebus gangguan di tempat lain yang disebabkan oleh pasangan ini.$(H,B)$$B$$H$$c$$H$$c$$2c$$H$

Jika adalah Hamiltonian, maka subgraph umum yang dibentuk dengan mencocokkan siklus Hamiltonian (minus e ) dalam salinan G ke ekuator bipyramid akan memiliki c ( n + 2 ) tepi, c ( n - 1 ) untuk khatulistiwa dan 3 c untuk puncak. Jika G bukan Hamiltonian, maka (untuk pilihan c yang cukup besar bahwa solusi optimal memasangkan apex dengan benar) setiap subgraph umum akan memiliki tepi lebih sedikit: masih 3 c pada apeks tetapi lebih sedikit dari c ( $G$$e$$G$$c(n+2)$$c(n-1)$$3c$$G$$c$$3c$ tempat lain. Jadi menguji apakah subgraph umum H dan B memiliki setidaknya c ( n + 2 ) edge adalah NP-complete.$c(n-1)$$H$$B$$c(n+2)$