Isomorfisme grafik yang efisien untuk kueri grafik yang serupa

Mengingat grafik G1, G2 dan G3, kami ingin melakukan uji isomorfisme F antara G1 dan G2 serta G1 dan G3. Jika G2 dan G3 sangat mirip sehingga G3 dibentuk dengan menghapus satu simpul dan memasukkan satu simpul dari G2, dan kita memiliki hasil F (G1, G2), dapatkah kita menghitung F (G1, G3) tanpa menghitungnya dari awal dengan memperluas metode canggih yang ada?

Misalnya, jika G2 dibentuk oleh node 2,3,4,5 dan G3 dibentuk oleh node 3,4,5,6, dapatkah kita menggunakan hasil F (G1, G2) untuk menghitung F (G1, G3) lebih efisien?

graph-theory graph-algorithms graph-isomorphism Eric Huang
sumber

Saya tidak punya argumen saat ini. Tetapi firasat saya adalah bahwa masalah Anda secara moral terkait dengan dugaan rekonstruksi ( en.wikipedia.org/wiki/Reconstruction_conjecture ).

Yixin Cao

Ini adalah pengurangan waktu polinomial sederhana untuk menunjukkan bahwa masalahnya adalah GI selesai : bahkan jika Anda tahu bahwa adalah isomorfis, memeriksa apakah , dibangun dari menghapus dan menambahkan sebuah simpul, isomorfik ke sama sulitnya dengan grafik isomorfisma sendiri (dalam kasus terburuk). $G_1, G_2$ $G_3$ $G_2$ $G_1$

Diberikan dua grafik build $G = (V, E), G'= (V', E')$

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

yaitu penyatuan dua grafik ditambah simpul ekstra terhubung ke semua simpul dari $u$ $V$

pilih ; dan jelas mereka isomorfik. $G_2 = G_1$

Sekarang bangun menghapus dan menambahkan terhubung ke semua simpul dari : $G_3$ $u$ $u'$ $V'$

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ adalah isomorfik jika $G, G'$ adalah isomorfik.

Marzio De Biasi
sumber

Ini pengurangan yang bagus! Namun, saya akan menambahkan bahwa kelengkapan-GI saja tidak selalu berarti tidak ada keuntungan, hanya saja dalam kasus terburuk kompleksitas mereka terkait secara polinomi. Sebagai contoh lain, perhatikan bahwa GI berwarna titik juga lengkap, tetapi sebagian besar algoritma yang saya tahu masih bisa memanfaatkan warna titik dengan cara yang bermanfaat.

Joshua Grochow

@ JoshuaGrochow: terima kasih, saya menjelaskan poin itu.

Marzio De Biasi

@MarzioDeBiasi: terima kasih atas penjelasannya. Berdasarkan pemahaman saya tentang penjelasan Anda, kami tidak dapat mengambil keuntungan apa pun untuk menghitung F (G1, G3) mengetahui F (G1, G2) jika simpul yang terhubung ke u dan u 'berbeda (tidak harus terhubung ke semua simpul V atau V ') bahkan jika kita tahu G dan G adalah isomorfik. Apakah itu benar? Dalam hal ini, apakah masalah ini sekeras grafik isomorfisme itu sendiri?

Eric Huang

@EricHuang: pengurangan mengatakan bahwa diberi dua grafik isomorfik

dan cara eksplisit untuk membangun

dengan menghapus / menambahkan satu node (dan beberapa tepi) untuk

masalah memeriksa apakah

isomorfik sekeras grafik isomorfisme. BTW, hasil ini juga meluas ke terkait masalah janji di mana Anda tidak mengingat cara eksplisit untuk membangun

, tetapi hanya janji bahwa

isomorfik sampai ke node menghapus / add operasi.

G_{1}, G_{2}

$G_1, G_2$

G_{3}

$G_3$

G_{2}

$G_2$

G_{1}, G_{3}

$G_1, G_3$

G_{3}

$G_3$

G_{1}, G_{3}

$G_1,G_3$

Marzio De Biasi

Anda dapat mencoba metode Weisfeiler-Lehman atau variasinya, terutama jika grafik asli Anda memiliki struktur seperti planar, pohon, grafik interval atau grafik treewidth terikat, dimensi Weisfeiler-Lehman mereka adalah konstanta kecil, pada langkah penyempurnaan, saya kira Anda dapat manfaatkan hubungan kedua grafik.

Rupei Xu

Isomorfisme grafik yang efisien untuk kueri grafik yang serupa

Jawaban: