Menguji isomorfisme grafik asimetris

13

Saat membaca pertanyaan Contoh dimana keunikan dari solusi membuatnya lebih mudah untuk menemukan , baru (? Mudah) pertanyaan datang ke pikiran saya: sebenarnya kita tidak tahu apakah Grafik isomorfisma ( ) masalah adalah di P .GIP

Tapi apa yang terjadi jika kita berasumsi bahwa kedua dan G 2 adalah asimetris (yaitu keduanya memiliki hanya sepele (identitas) automorphism)? Apakah masalah menjadi lebih mudah (waktu polinomial)? G1G2

Catatan: masalahnya tidak bisa lebih sulit daripada Graph Automorphism ( ), karena ada pengurangan cepat: cukup gunakan G A pada G 1 ∪ G 2GAGAG1∪G2 , jika jawabannya adalah ya maka kedua grafik tersebut adalah isomorfik (lihat juga Johannes Köbler, Uwe Schöning, Jacobo Torán: Grafik Isomorfisme Rendah untuk PP . 401-411).

reference-request graph-isomorphism Marzio De Biasi
sumber
2
Dengan probabilitas mendekati 1 saat n bertambah, grafik Anda hanya memiliki automorfoisme trival oleh kompleksitas Kolmogorov.
Chad Brewbaker
1
+1 Pertanyaan yang bagus, pertanyaan Anda berpotensi menyebabkan serangan pada P vs NP. Coba buktikan bahwa tidak ada pengurangan Turing dari ke masalah Anda. GSEBUAH
Mohammad Al-Turkistany
4
Masalah ini dikenal sebagai masalah isomorfisme grafik kaku. Jika itu bisa diselesaikan dalam waktu polinomial atau tidak terbuka lebar. Ada beberapa pekerjaan yang mencoba untuk menyerang melalui algoritma kuantum, misalnya, dengan menguranginya menjadi masalah shift tersembunyi ( arxiv.org/ab/quant-ph/0510185 ) tetapi hasilnya sebagian besar negatif yang menunjukkan bahwa teknik yang dicoba tidak kerja.
Mateus de Oliveira Oliveira
1
Dimungkinkan untuk menguatkan grafik apa pun sehingga hanya memiliki endomorfisme tunggal (dan karenanya automorfisme), dengan melampirkan grafik yang saling menguatkan pada setiap titik. Ini menyiratkan pengurangan Turing dari GI untuk menentukan isomorfisma grafik asimetris. Sayangnya, ini bukan polinomial.
András Salamon
1
Well Childs / Wocjan tidak sendirian dalam menggunakan rigid untuk menunjukkan grafik dengan automorfisme tunggal. Ada survei dari Babai dari tahun 1994 yang sudah menyatakan bahwa terminologinya tidak standar www.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf. Juga di zaman modern ini kaku telah digunakan dalam hal ini oleh Jacobo Toran ( uni-ulm.de/fileadmin/website_uni_ulm/.../toran/hard.pdf ). Jadi sepertinya itu masalah apakah penulis peduli tentang embeddings atau tidak. Tetapi saya menggunakan asimetris dalam jawaban saya untuk menghindari kebingungan.
Mateus de Oliveira Oliveira

Jawaban:

11

Atas permintaan Marzio De Biasi saya mengubah komentar saya menjadi jawaban.

Grafik asimetris (beberapa penulis menyebutnya sebagai kaku) jika memiliki automorfisme yang unik, yaitu identitas. Seperti yang ditunjukkan oleh Chad Brewbacker, sebagian besar grafik asimetris. Namun dua pertanyaan berikut terbuka:

1) Apakah isomorfisma grafik asimetris dalam P?

2) Dapatkah isomorfisma grafik umum direduksi menjadi isomorfisme grafik asimetris?

Ω(nlog⁡n)

Mateus de Oliveira Oliveira
sumber