Algoritmo determinístico mais rápido conhecido para o problema de isomorfismo de grafos não direcionado

Qual é o algoritmo de isomorfismo de gráfico não direcionado mais rápido conhecido?

cc.complexity-theory reference-request graph-algorithms graph-isomorphism bbejot
fonte

Eu acho que é melhor se você apenas pedir o algoritmo mais rápido conhecido, e não a correção do algoritmo dado no artigo (em particular, consulte a meta questão relevante ). Para mim, o resumo já é uma bandeira vermelha (as conclusões também parecem conter informações falsas).

Juho

Geralmente, se um resultado importante para um problema famoso estiver correto, ele aparecerá nos blogs de teoria famosos 1 2 e no artigo da Wikipedia sobre o problema .

Kaveh

O papel não passa no teste de cheiro. Pretende resolver um grande problema, mas apareceu em uma conferência obscura. Não há provas. A correção é "validada" experimentalmente. Os autores pensam que o isomorfismo do gráfico é NP-difícil.

Sasho Nikolov

2^{\sqrt{n \log n}}

$2^{\sqrt{n\log n}}$

2^{O (\sqrt{n \log n})}

$2^{O(\sqrt {n \log n})}$

Respostas:

a pesquisa sobre isomorfismo de gráfico geralmente é direcionada para a observação de algoritmos eficientes ou aprimorados para muitas classes gráficas especiais com algoritmos P-Time para os quais houve muito progresso e também análises mais empíricas com software de ponta, por exemplo Nauty analisando os comportamentos médios e os piores casos separadamente. para o problema geral de acordo com esta pesquisa de blog de Bennett / Flammia / Harrow, aparentemente um resultado antigo de Babai / Luks pode ser o mais conhecido.

“Rotulagem canônica de gráfico” por László Babai e Eugene M. Luks STOC 1983 ( artigo aqui ) Isso descreve uma subexponencial (ou, err, como Scott decidiu chamar isso?), Exp (-n ^ {frac {1} { 2} + c}), algoritmo de tempo para um gráfico com n vértices. Agora, como uma lista de leitura, ainda não recomendo pular este artigo, mas só queria extinguir seu otimismo em relação a um algoritmo clássico, mostrando a você (a) o melhor que temos em geral é um algoritmo de tempo subexponencial, (b) esse registro permanece há quase três décadas e (c) que, se você olhar para o jornal, poderá ver que não é fácil. Abandonar a esperança a todos que entram?

aqui estão duas outras pesquisas bastante abrangentes para avaliar o estado da arte, mas talvez mais com uma inclinação empírica.

Algoritmos eficientes para teste de isomorfismo de grafos Jose Luis Lopez Presa Tese de doutorado (2009)
O problema do isomorfismo dos grafos (1996) Fortin (1996)

vzn
fonte

outro ponto é que, como na resposta de JGs, o isomorfismo de grafos tem profundas ligações teóricas ao problema do isomorfismo de grupo. isso pode ser visto neste outro blog sobre subj por RJLipton, Uma abordagem para isomorfismo gráfico

vzn

Observe que a pesquisa Fortin tem quase 20 anos, o que é uma eternidade em um campo em que, por exemplo, o conceito de completude de NP tem apenas 40 anos.

David Richerby

sim, observou isso também, mas também há o fenômeno de problemas-chave / abertos do TCS mostrando pouco progresso importante ao longo de décadas, obviamente incluindo também P vs NP como um exemplo canônico disso, e o IG também se encaixa como indicado.

vzn

Você parece confundir as afirmações "Ainda não resolvemos o problema" e "nenhum progresso foi feito".

David Richerby

$2^{\log n^{O(1)}}$

Mohammad Al-Turkistany
fonte

Supostamente é executado em tempo quase-polinomial. Mesmo que sua análise seja falha e seja meramente subexponencial, ainda será o algoritmo mais rápido.

Stella Biderman 29/03