Grafik Sangat Reguler dan Kelengkapan GI

Hal ini tidak diketahui apakah grafik isomorfisma (GI) untuk grafik sangat teratur (SRGs) dalam P . Apakah ada petunjuk bahwa itu mungkin atau mungkin tidak GI -Lengkap? Adakah konsekuensi kuat dalam kasus-kasus seperti itu? (Mirip dengan keyakinan bahwa GI mungkin tidak NP-Lengkap).

cc.complexity-theory graph-theory graph-algorithms graph-isomorphism structural-complexity DurgaDatta
sumber

Saya pribadi percaya bahwa masalahnya lebih mudah daripada GI, karena algoritma Spielman untuk SRG, yang memiliki eksponen lebih kecil daripada yang oleh Luks untuk grafik umum. Sepertinya ada lebih banyak struktur! (yang pada akhirnya mungkin tidak ada artinya)

Timothy Sun

O (n)

$O(n)$

O (n^{3 / 2})

$O(n^{3/2})$

Jawaban:

Saya percaya semua hasil kelengkapan GI yang diketahui adalah functorial (definisi dalam makalah ini), dan Babai baru-baru ini menunjukkan (ITCS 2014, salinan penulis gratis ) - berdasarkan pada batas pada struktur kelompok automorfisme dari grafik yang sangat teratur - bahwa tidak ada functorial reduksi dari GI menjadi GI yang sangat teratur.

Joshua Grochow
sumber