Riwayat dan status masalah pencocokan grafik

Bagian dari kesulitan untuk mengetahui lebih lanjut tentang masalah ini adalah bahwa masalah pencocokan grafik berbeda dari sepupunya yang jauh lebih terkenal, masalah pencocokan, tetapi sulit dibedakan dari itu ketika menggunakan mesin pencari.

Diberikan dua grafik $G=(V,E)$ dan sedemikian rupa sehingga, tugasnya adalah untuk menemukan bijection sedemikian rupa sehingga bijection ini membangun korespondensi sebanyak mungkin antara tepi dan .$G'=(V',E')$$|V| = |V'|$$\pi : V \rightarrow V'$$G$$G'$

Dengan kata lain, jika dan adalah matriks kedekatan, maka kami ingin memaksimalkan$M$$M'$

$\sum_{v,w \in V} M_{v,w} \cdot M'_{\pi(v),\pi(w)}$

Masalah ini jelas mengandung isomorfisme grafik sebagai kasus khusus, dan dapat direduksi menjadi pencocokan bipartit dalam pengurangan (non-polinomial!).

Algoritma macam apa yang ada, dan apa yang diketahui tentang kompleksitasnya?

Dari makalah Perkiraan Grafik Isomorfisme :

Kami mempelajari versi optimisasi Graph Isomorphism. Mengingat dua grafik , kami tertarik dalam menemukan bijection dari ke yang memaksimalkan jumlah pertandingan (tepi dipetakan ke tepi atau non-tepi dipetakan ke non-tepi). Kami memberikan skema perkiraan waktu yang untuk faktor konstan , menghitung apro-estimasi . Kami membuktikan ini dengan menggabungkan algoritma perkiraan kesalahan aditif waktu Arora et al. [Matematika. Program., 92, 2002] dengan algoritma rata-rata sederhana. Kami juga mempertimbangkan masalah minimisasi yang sesuai (ketidakcocokan) dan membuktikan bahwa NP-hard to$G_1,G_2$$π$$V(G_1)$$V(G_2)$$n^{O(\log{n})}$$α < 1$$α$$n^{O(\log{n})}$$α$ -roksimasi untuk faktor konstan . Selanjutnya, kami menunjukkan bahwa NP-hard untuk memperkirakan jumlah maksimum tepi yang dipetakan ke tepi di luar faktor 0,94.$α$

Saya tidak tahu tentang masalah Anda. Tapi kebetulan saya tahu banyak koleksi makalah yang berkaitan dengan algoritma Graph Matching DENGAN PDF . Tepuk tangan untuk Seth Pettie!

Makalah yang ditunjukkan oleh @Austin Buchanan di atas tentang perkiraan Grafik Isomorfisme tampaknya tidak sesuai dengan versi yang ditanyakan. Saya mengasumsikan bahwa matriks adjacency memiliki entri dalam hal tujuan hanya mengukur tepi yang cocok. Perkiraan model Graph Isomorphism mengukur keduanya cocok dengan tepi yang tidak cocok yang membuatnya sedikit lebih mudah dari sudut pandang perkiraan.$0,1$

Tampaknya masalah yang ditanyakan setidaknya sama sulitnya dengan masalah -dense-subgraph yang saat ini hanya mengakui pendekatan polinomial. Lihat http://arxiv.org/abs/1001.2891 dan http://arxiv.org/abs/1110.1360 untuk rincian lebih lanjut dan status saat ini dalam hal algoritma dan kekerasan.$k$

Sekarang untuk reduksi. Misalkan kita ingin menyelesaikan masalah -dense-subgraph dalam grafik ; yaitu kita ingin menemukan subset dari node yang memaksimalkan jumlah tepi dalam grafik yang diinduksi . Anda dapat mengurangi ini untuk masalah Anda dengan menetapkan menjadi grafik yang terdiri dari kelompok pada -vertices dan simpul terisolasi, dan ditetapkan menjadi .$k$$H$$k$$S$$G[S]$$G$$k$$n-k$$G'$$H$