Introdução suave ao isomorfismo de grafos para gráficos de valência limitada

17

Estou lendo sobre classes de gráficos para o qual Graph Isomorfismo ( ) está em . Um desses casos são gráficos de valência limitada (máximo acima do grau de cada vértice), conforme explicado aqui . Mas achei muito abstrato. Ficaria muito grato se alguém puder me sugerir algumas referências de natureza expositiva. Como não tenho formação sólida em teoria de grupos, prefiro trabalhos que usem a teoria de grupos de maneira suave (minha formação é em CS).GIP

DurgaDatta
fonte
11
Infelizmente, não tenho o livro, mas O Problema do Isomorfismo do Gráfico: Sua Complexidade Estrutural, de Johannes Köbler, Uwe Schöning e Jacobo Torán, pode conter uma prova para o caso de grau limitado. Você pode querer verificar isso.
Tsuyoshi Ito
2
@TsuyoshiIto: Embora seja um excelente livro que fornece uma boa introdução à IG e a um pouco de complexidade estrutural geral, ele não contém muito (se é que existe) sobre o caso de graduação limitada. Não conheço uma introdução suave ao caso do grau limitado, mas está tão intimamente ligado aos métodos da teoria dos grupos que duvido que exista uma exposição que use a teoria dos grupos "apenas gentilmente" (conforme solicitado pelo OP).
Joshua Grochow
Estou ansioso para dar uma visão geral, farei isso em breve!
Jim

Respostas:

14

O algoritmo para isomorfismo de gráfico de grau limitado está tão intimamente ligado à teoria dos grupos (permutação) que duvido que exista uma introdução que use os grupos "apenas suavemente". No entanto, você pode consultar o Ph.D. de Paolo Codenotti tese para um histórico mais completo. Ele não cobre exatamente o isomorfismo de gráfico de grau delimitado, mas cobre as ferramentas necessárias para ele (e o restante da tese trata de hipergrafos de classificação limitada, estendendo o algoritmo mais conhecido para o isomorfismo de gráfico geral ao caso do hipergrafo de classificação limitada) .

Você também pode achar útil o livro Algoritmos Teóricos de Grupos e Isomorfismo de Gráfico , pois cobre a maior parte do contexto necessário (o Capítulo 2, "Conceitos Básicos", tem 47 páginas) e é uma exposição muito mais lenta do que a maioria dos trabalhos publicados sobre o tópico.

Joshua Grochow
fonte
1

Notação: Let ser gráfico, e = ( v 1 , v 2 ) uma aresta de X . O conjunto vértice V k ser o conjunto de vértices de distância k a partir de e , e deixá- H ser a altura de X .X=(V,E)e=(v1,v2)XVkkehX

De acordo com a definição de , V = V 0V 1 ... V H e V ( h + 1 ) = . Seja o subconjunto E k das arestas de X ( 0 k h ) definido comoVkV=V0V1VhV(h+1)=EkX(0kh)

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

O subgrafo é definido comoXi

Xk=(V0V1Vk,E0E1E(k1)}

Por exemplo, X2={(V0V1V2,E0E1)}

é o grupo de automorfismo do gráfico X em que e é fixo. Se B é um grupo gerador de um u t e ( X k ) , que escreverB = Um u t e ( X k ) , por exemplo, é evidente que uma u t e ( X 0 ) = ( v 1 , v 2Aute(X)XeBAute(Xk)B=Aute(Xk) Onde ( v 1 , v 2 ) é uma permutação de vértices v 1 , v 2 de X .Aute(X0)=(v1,v2)(v1,v2)v1,v2X

Princípio A construção de um grupo gerador de automorfismo de é um problema completo de GI (gráfico isomorfismo) [1]. Portanto, se pudermos calcular o conjunto gerador do grupo automorfismo X (que tem valência limitada no tempo polinomial), podemos resolver o GI no tempo polinomial. Então, queremos determinar A u t e ( X ) .XXAute(X)

Técnica:

Vamos construir . Para cada X k , construiremos A u t e ( X ( k ) )X0,X1.....XhXkAute(X(k))

Note-se que, uma permutação de pode ser estendido para uma automorphism de um u t e ( X ( k + 1 ) ) .Aute(X(k))Aute(X(k+1))

So, generators of Aute(X(k+1)) can be obtained from generators for Aute(Xk).

To construct generator, structure-type of Ek is manipulated. The structure-type of Ek can be divided into finite classes. For example, in the trivalent case, there are only six type (only five of those cases can actually occur).

We will classify the edges in Ek into types and will group them into families . This helps to create a number of unique labels.

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
fonte
[1]Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132.
Jim