Algorithme de canonisation de graphe simple

8

Je recherche un algorithme qui fournit une chaîne canonique pour un graphique coloré donné. C'est à dire. un algorithme qui renvoie une chaîne pour un graphique, de telle sorte que deux graphiques obtiennent la même chaîne si et seulement s'ils sont isomorphes.

En particulier, je recherche un algorithme simple et facile à implémenter avec des performances raisonnables sur la plupart des graphes (super-polynôme pire cas, bien sûr). Je m'attends à de petits graphiques, donc les performances ne doivent pas être stellaires, juste assez bonnes.

Malheureusement, la plupart des choses que j'ai trouvées sont très complexes et s'intéressent plus à exprimer des connexions mathématiques profondes qu'à décrire simplement l'algorithme. J'ai bien peur de ne pas avoir le temps de plonger aussi profondément. Quelqu'un peut-il me donner un raccourci?

J'espère quelque chose comme l'algorithme Floyd-Warshall. Pas optimal, mais assez bon et facile à mettre en œuvre.

algorithms graph-theory combinatorics Peter
la source
Les graphiques sont-ils étiquetés de manière cohérente? Si oui, notez simplement tous les bords et triez la liste.
adrianN
Ah désolé. Les sommets et les bords sont étiquetés, mais pas uniquement. Chaque étiquette peut se produire plusieurs fois. Je suppose que l'expression mathématique est "colorée" plutôt qu'étiquetée. Je vais modifier la question.
Peter
"pire cas NP, bien sûr" - juste pour que nous soyons clairs: il existe un algorithme de temps polynomial (déterministe) connu pour l'isomorphisme des graphes, donc le meilleur que vous puissiez attendre est une solution superpolynomiale. Et oui, le problème est dans NP. Voir ici pour plus de détails sur ces notions.
Raphael
@Raphael Vous avez raison, une terminologie plus inexacte. Le pire des cas est super-polynomial. Il existe cependant des algorithmes polynomiaux à cas moyen, ce qui devrait au moins être réalisable.
Peter
@Raphael Le mieux que vous puissiez attendre est un algorithme rapide qui fonctionne pour la plupart des graphiques.
Yuval Filmus

Réponses:

3

Brendan McKay et Adolfo Piperno ont rédigé un document d'enquête sur cette question en 2013. Ils présentent plusieurs programmes informatiques efficaces qui canonisent de nombreux graphiques plus rapidement que vous ne l'imaginez. Il n'est pas nécessaire (et inutile) de mettre en œuvre ces algorithmes vous-même - ils sont disponibles en ligne, même en tant que code source.

Yuval Filmus
la source
Il y a une réduction entre le GI coloré et le GI (avec une explosion multiplicative constante étant donné un nombre constant de couleurs), ou peut-être que les algorithmes eux-mêmes pourraient être modifiés.
Yuval Filmus
Pouvez-vous en décrire un ici pour donner une réponse complète?
Raphael
3
Pour chaque couleur, ajoutez un sommet supplémentaire. Connectez chaque sommet d'origine au sommet représentant sa couleur en ajoutant une arête. Assurez-vous que les degrés des sommets "couleur" sont uniques - si ce n'est pas le cas, ajoutez des boucles ou d'autres faux bords. Soit dit en passant, je suis moins que satisfait du document d'enquête McKay / Piperno - il s'agit d'une enquête sur leurs propres recherches, et les comparaisons qu'ils font avec d'autres outils sont conformes aux critères qu'ils considèrent intéressants. Ils omettent d'importants développements récents et presque tous les repères dérivés d'applications non théoriques, ce qui affecte les résultats empiriques.
Igor Markov
2

J'ai fini par implémenter l'algorithme Nauty, mais ce faisant, j'ai trouvé une réponse à ma propre question. Nauty étend cet algorithme de base avec de nombreuses heuristiques compliquées:

Soit un petit graphe G de longueur n:

  1. Boucle sur tout n! permutations de ses sommets.
  2. Générez une représentation sous forme de chaîne de chacun (un à un).
  3. Définissez un ordre canonique des chaînes et rappelez-vous la plus petite chaîne rencontrée.

Cet algorithme est O(n!), mais pour les petits graphiques, cela devrait fonctionner correctement.

Nauty étend cet algorithme principalement en élaguant l'espace de recherche des graphiques à considérer, lorsque vous recherchez celui avec la plus petite représentation de chaîne.

Peter
la source
1
Les graphiques doivent être vraiment petits si cette approche par force brute est plausible. Même15! est supérieur à 1012.
David Richerby
1
@DavidRicherby Absolument. Cependant, il existe des cas d'utilisation, tels que l'analyse de motifs, où cette opération n'est effectuée que sur des graphiques de taille 3 ou 4. En fait, je ne sais pas si la recherche d'un sous-graphique canonique isomorphe peut être obtenue en un temps raisonnable pour les graphiques sur 15 nœuds (même si l'isomorphisme sous-graphique lui-même est maintenant connu pour être très proche du polynôme)
Peter