Algorithme déterministe le plus rapide connu pour le problème d'isomorphisme de graphe non orienté

Quel est l'algorithme d'isomorphisme de graphe non orienté le plus rapide connu?

cc.complexity-theory reference-request graph-algorithms graph-isomorphism bbejot
la source

Je pense que c'est mieux si vous demandez simplement l'algorithme le plus rapide connu, et non l'exactitude de l'algorithme donné dans l'article (en particulier, voir la méta-question pertinente ). Pour moi, le résumé est déjà un drapeau rouge (les conclusions semblent également contenir de fausses informations).

Juho

Généralement, si un résultat majeur pour un problème célèbre est correct, il apparaîtra sur les blogs théoriques célèbres 1 2 et sur l'article Wikipedia pour le problème .

Kaveh

Le papier ne passe pas le test de l'odeur. Il prétend résoudre un problème majeur mais est apparu lors d'une obscure conférence. Il n'y a pas de preuves. La correction est "validée" expérimentalement. Les auteurs pensent que l'isomorphisme des graphes est NP-difficile.

Sasho Nikolov

@JoshuaGrochow dit que l'algorithme le plus rapide connu prend du temps

dans cette réponsecstheory.stackexchange.com/a/22059/4896. Je pense que l'algorithme est déterministe.

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

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

Sasho Nikolov

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

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

Réponses:

la recherche sur l'isomorphisme des graphes a généralement été orientée vers la recherche d'algorithmes efficaces ou améliorés pour de nombreuses classes de graphes spéciales avec des algorithmes P-Time pour lesquels il y a eu beaucoup de progrès, et aussi une analyse plus empirique avec des logiciels de pointe, par exemple Nauty examine séparément les comportements moyens et les pires cas. pour le problème général selon cette enquête de blog de Bennett / Flammia / Harrow, un vieux résultat de Babai / Luks est apparemment le plus connu.

«Étiquetage canonique du graphique» par László Babai et Eugene M. Luks STOC 1983 ( article ici ) Ceci décrit un sous-exponentiel (ou, euh, comment Scott a-t-il décidé d'appeler cela?), Exp (-n ^ {frac {1} { 2} + c}), algorithme de temps pour un graphe à n sommets. Maintenant, en tant que liste de lecture, je ne recommande pas encore de sauter dans cet article, mais je voulais simplement étouffer votre optimisme pour un algorithme classique en vous montrant (a) le meilleur que nous avons en général est un algorithme de temps sous-exponentiel, (b) ce record existe depuis près de trois décennies, et (c) que si vous regardez le journal, vous pouvez voir que ce n'est pas facile. Abandonnez l'espérance à vous tous qui entrez?

voici deux autres enquêtes assez complètes pour évaluer l'état de l'art mais peut-être plus avec une orientation empirique.

Algorithmes efficaces pour tester l'isomorphisme des graphes Thèse de doctorat de Jose Luis Lopez Presa (2009)
Le problème de l'isomorphisme graphique (1996) Fortin (1996)

vzn
la source

un autre point est que, comme dans la réponse de JG, l'isomorphisme graphique a des liens théoriques profonds avec le problème d'isomorphisme de groupe. cela peut être vu dans cet autre blog sur subj par RJLipton, An approach to graph isomorphism

vzn

Il est à noter que l'enquête Fortin a près de 20 ans, ce qui est une éternité dans un domaine où, par exemple, le concept d'exhaustivité NP n'a que 40 ans environ.

David Richerby

Oui, cela a également été noté, mais il y a aussi le phénomène des problèmes ouverts / difficiles du TCS montrant peu de progrès majeurs au cours des décennies, incluant évidemment P vs NP comme exemple canonique de cela, et GI s'adapte également comme indiqué.

vzn

Vous semblez confondre les déclarations "Nous n'avons pas encore résolu le problème" et "aucun progrès n'a été fait".

David Richerby

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

Mohammad Al-Turkistany
la source

Fonctionne prétendument en temps quasi-polynomial. Même si son analyse est défectueuse et qu'elle est simplement sous-exponentielle, ce sera toujours l'algorithme le plus rapide.

Stella Biderman