Masalah terbuka terkait dengan Grafik isomorfisme

18

Saat ini saya sedang melakukan survei literatur tentang masalah Graph isomorphism (GI).

Saya ingin mengetahui beberapa pertanyaan terbuka terkait hal-hal berikut

  1. Apa parameter grafik yang traktabilitas parameter tetap GI merupakan masalah terbuka.

  2. Apa parameter grafik, dengan memperbaikinya solvabilitas waktu polinomial GI tidak diketahui.

  3. Kompleksitas GI ketika terbatas pada banyak kelas grafik setara dengan GI umum (GI-Completeness). Apa kelas grafik yang kelengkapan GI tidak diketahui.

Terima kasih.

graph-isomorphism fixed-parameter-tractable Kumar
sumber
3
Saya tidak mengetahui adanya jawaban pasti untuk pertanyaan Anda. Jika Anda menemukan jawaban parsial (yang mungkin membutuhkan melihat puluhan makalah penelitian yang diterbitkan), maka akan lebih bagus jika Anda dapat menautkan ke ringkasan yang Anda buat, atau memberikan highlightnya, sebagai jawaban.
András Salamon
ulang 3, pertanyaan. untuk banyak grafik kelas GI yang terbukti lengkap, apakah pertanyaan "bukankah X grafik GI lengkap?" Buka? apakah itu masuk akal? terkait pertanyaan cs.seXX
vzn

Jawaban:

13

Untuk pertanyaan pertama: Grafik Isomorfisme telah dipertimbangkan untuk setidaknya parameter berikut yang traktabilitas parameter tetap masih terbuka.

  • pathwidth / treewidth (lihat [2], telah ditanyakan di sini ), mungkin diselesaikan: http://arxiv.org/abs/1404.0818
  • cutwidth / bandwidth [1]
  • treewidth-k jumlah set penghapusan penghapusan vertex (nomor set vertex umpan balik dalam [7])
  • lebar jarak pohon / jalur (lihat [1]), lebar jarak pohon terhubung (lihat [3], namun Anda bisa cukup dekat dengan yang terakhir, lihat bagian 6.4 dari tesis diploma saya ) : diselesaikan oleh Y. Otachi dan P . Schweitzer: http://arxiv.org/abs/1403.7238
  • clique-width / shrub-depth (atau SC-depth) (lihat [ 4 ])
  • gelar maksimum [5]
  • genus [6] / nomor persimpangan [8]

Perhatikan bahwa ada penelitian yang sedang berlangsung aktif untuk beberapa dari mereka.

[1]: K. Yamazaki, HL Bodlaender, B. de Fluiter dan DM Thilikos. Isomorfisme untuk grafik lebar jarak terbatas. Algorithmica 24.2 (1999)

[2]: HL Bodlaender. Algoritma polinomial untuk isomorfisme grafik dan indeks kronik pada pohon partialk. Jurnal Algoritma 11.4 (1990)

[3]: Y. Otachi. Isomorfisme untuk Grafik Lebar-Path-Distance-Connected. Algoritma dan Komputasi. Springer, 2012

[ 4 ]: http://www.fi.muni.cz/~hlineny/res-en.html#recent

[5]: L. Babai dan EM Luks. Pelabelan kanonik dari grafik. STOC '83.

[6]: IS Filotti dan JN Mayer. Algoritma polinomial-waktu untuk menentukan isomorfisme grafik genus tetap. STOC '80 / G. Miller. Pengujian isomorfisme untuk grafik genus terikat. STOC '80

[7]: S. Kratsch dan P. Schweitzer. Isomorfisme untuk grafik jumlah set vertex umpan balik terikat. SWAT 2010

[8]: http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf

frafl
sumber
1
Dalam hal penelitian yang relevan aktif di bidang ini, ada beberapa referensi tambahan yang saya sarankan. [A] Makalah ini di sini dari IPEC 2012, menunjukkan grafik isomorfisma adalah parameter-tetap yang dapat ditelusur di kedalaman pohon grafik, yang merupakan parameter terkait dengan lebar pohon. [B] Makalah ini di sini menunjukkan bahwa isomorfisma grafik untuk grafik chordal adalah FPT dalam ukuran komponen simplisial terbesar.
Adam Bouland
3
Sg
@Adam Bouland Apakah ada algoritma waktu FPT atau Polinomial untuk isomorfisme Graph untuk lebar pita terbatas.
Kumar
1
@ Kumar Ini adalah poli-waktu yang dapat dipecahkan tetapi tidak dikenal sebagai FPT. Lihat Yamazaki et al. [1] dalam jawaban frafl.
Yota Otachi
5

Untuk pertanyaan ketiga: Makalah survei Brandstadt, Le, dan Spinrad, Graph Classes: A Survey, SIAM, 1999, berisi beberapa kelas grafik yang kelengkapan GInya tidak diketahui. Salah satu kelas tersebut adalah grafik trapesium . Kelas lain adalah grafik busur lingkaran yang disebut sebagai masalah terbuka dalam pengantar makalah, Traktabilitas dan Intrabilitas pada Grafik Persimpangan Geometris oleh Uehara.

EDIT : Masalah Graph Isomorphism untuk turnamen tidak diketahui sebagai GI-complete.

Mohammad Al-Turkistany
sumber
4

Untuk pertanyaan ketiga, Anda juga dapat mengunjungi www.graphclasses.org : luncurkan java applet dan pilih Masalah -> Masalah Batas / Buka -> Grafik isomorfisme.

Anda akan mendapatkan daftar besar kelas grafik yang status masalahnya GI tidak diketahui oleh ISGCI (bisa dalam P atau GI-lengkap); mungkin bagi beberapa dari mereka kelengkapan GI telah diselesaikan, atau mereka belum dipelajari; tetapi ini adalah titik awal yang baik untuk mencari makalah tentang mereka.

Marzio De Biasi
sumber