Introduction en douceur à l'isomorphisme des graphes pour les graphes à cantonnière bornée

17

Je lis sur les classes de graphiques pour lesquels Graphique Isomorphisme ( ) est en . Un de ces cas est des graphiques de valence bornée (maximum sur le degré de chaque sommet) comme expliqué ici . Mais je l'ai trouvé trop abstrait. Je serais reconnaissant si quelqu'un pouvait me suggérer quelques références de nature expositoire. Je n'ai pas une solide formation en théorie des groupes, donc je préférerais des articles qui utilisent la théorie des groupes d'une manière douce (mon expérience est en CS).PGIP

DurgaDatta
la source
1
Je n'ai pas le livre (malheureusement), mais The Graph Isomorphism Problem: Its Structural Complexity de Johannes Köbler, Uwe Schöning et Jacobo Torán peut contenir une preuve pour le cas du degré borné. Vous voudrez peut-être le vérifier.
Tsuyoshi Ito
2
@TsuyoshiIto: Bien que ce soit un excellent livre qui donne une bonne introduction à l'IG et à un peu de complexité structurelle générale, il ne contient pas beaucoup (voire rien) sur le cas des degrés bornés. Je ne connais pas d'introduction en douceur au cas des degrés bornés, mais il est si intimement lié aux méthodes théoriques de groupe que je doute qu'il existe une exposition qui n'utilise la théorie de groupe que "doucement" (comme le demande l'OP).
Joshua Grochow
Je tiens à donner un aperçu, je le ferai bientôt!
Jim

Réponses:

14

L'algorithme pour l'isomorphisme du graphe à degrés bornés est si étroitement lié à la théorie des groupes (de permutation) que je doute qu'il existe une introduction qui n'utilise les groupes «que doucement». Cependant, vous pouvez consulter le doctorat de Paolo Codenotti. thèse pour un fond plus complet. Il ne couvre pas exactement l'isomorphisme des graphes à degrés bornés, mais couvre les outils nécessaires pour cela (et le reste de la thèse concerne les hypergraphes à rang borné, étendant le meilleur algorithme connu pour l'isomorphisme général des graphes au cas d'hypergraphe à rang borné) .

Vous pouvez également trouver le livre Group-Theoretic Algorithms and Graph Isomorphism utile, car il couvre la majeure partie de l'arrière-plan nécessaire (le chapitre 2, "Concepts de base", est de 47 pages) et est une exposition beaucoup plus tranquille que la plupart des articles publiés sur le sujet.

Joshua Grochow
la source
1

Notation: Soit est graphique, e = ( v 1 , v 2 ) d' un bord de X . L'ensemble de sommets V k l'ensemble des sommets de la distance k de e , et que h soit la hauteur de X .X=(V,E)e=(v1,v2)XVkkehX

Selon la définition de , V = V 0V 1V h et V ( h + 1 ) = . Soit, le sous-ensemble E k des arêtes de X ( 0 k h ) est défini commeVkV=V0V1VhV(h+1)=EkX(0kh)

Ek={(u,w)|uVk,wVkV(k+1)}.

Le sous-graphe est défini commeXi

Xk=(V0V1Vk,E0E1E(k1)}

Par exemple, X2={(V0V1V2,E0E1)}

est le groupe d'automorphisme du graphe X e est fixe. Si B est un ensemble de génération de A u t e ( X k ) , on écritB = A u t e ( X k ) , par exemple, il est clair que A u t e ( X 0 ) = ( v 1 , v 2Aute(X)XeBAute(Xk)B=Aute(Xk) ( v 1 , v 2 ) est une permutation de sommets v 1 , v 2 de X .Aute(X0)=(v1,v2)(v1,v2)v1,v2X

Principe La construction d'un groupe électrogène d'un groupe d'automorphisme de est un problème complet de GI (isomorphisme graphique) [1]. Donc, si nous pouvons calculer le groupe électrogène du groupe d'automorphisme de X (qui a une valence limitée en temps polynomial), nous pouvons résoudre GI en temps polynomial. Nous souhaitons donc déterminer A u t e ( X ) .XXAute(X)

Technique:

Nous allons construire . Pour chacun, X k nous construirons A u t e ( X ( k ) )X0,X1.....XhXkAute(X(k))

Notez que, une permutation de peut être étendue à un automorphisme de A u t e ( X ( k + 1 ) ) .Aute(X(k))Aute(X(k+1))

Aute(X(k+1))Aute(Xk)

EkEk

Ek

For a fixed valence, the number of labels is small. At this point, we use the concept of setwise-stabilizers to find permutations which acts on particular label. In the process, we find the generator of Aute(X(k)). Then, we use the generator ofAute(X(k)) to find the generator of Aute(X(k+1)), as stated earlier. Proceeding in this manner, we obtain, Aute(X) .

Jim
la source
[1]Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132.
Jim