Gráfico fortemente regular e integridade GI

16

Não se sabe se isomorfismo gráfico (GI) para gráficos fortemente regulares (SRGS) é em P . Existe alguma dica de que possa ou não ser GI- Complete? Existem fortes consequências nesses casos? (Semelhante à crença de que o IG pode não ser NP-Completo).

cc.complexity-theory graph-theory graph-algorithms graph-isomorphism structural-complexity DurgaDatta
fonte
6
Pessoalmente, acredito que o problema é estritamente mais fácil que o IG, por causa do algoritmo de Spielman para SRGs, que tem um expoente menor que o de Luks para gráficos gerais. Parece que há muito mais estrutura! (o que em última instância pode significar nada)
Timothy dom
2
Embora eu concorde com o @TimothySun, eu realmente não sei razões formais para pensar que o SRGI é estritamente mais fácil do que o IG. Por exemplo, se houver um redução do GI para SRGI seguida, que daria origem a um algoritmo de melhor para GI do que o actualmente conhecido, mas se os golpes de redução até ao número de vértices mesmo para S ( n 3 / 2 ) , em seguida, que seria não tem essa conseqüência surpreendente. Quanto ao seu segundo q., Duvido que haja conseqüências de complexidade de qualquer problema (conhecido por reduzir a IG), sendo GI-completo, uma vez que não tem relação com a maioria das outras classes de complexidade (ao contrário do fato de GI ser NPC colapsar PH). O(n)O(n3/2)
Joshua Grochow

Respostas:

11

Eu acredito que todos os resultados GI-completude conhecidos são functorial (definição no papel), e Babai mostrou recentemente (ITCS 2014, cópia do autor livre ) - com base em limites sobre a estrutura de grupos de automorfismos de grafos fortemente regulares - que não há functorial redução de GI para GI fortemente regular.

Joshua Grochow
fonte