Isomorfismo de gráfico e subgrupos ocultos

23

Estou tentando entender a relação entre isomorfismo de gráfico e o problema de subgrupo oculto. Existe uma boa referência para isso?

Suresh Venkat
fonte
2
Tssk, não apenas precisaremos curar sua doença gastrointestinal, mas também todos os leitores pobres de sua pergunta que também serão infectados! (Isto é em tom de brincadeira, estou um pouco propensos à doença GI também.)
András Salamon
1
verdade demais. Eu tenho que ficar longe de Dave Bacon agora :)
Suresh Venkat
2
FYI, o seguinte artigo relativamente recente, acho que colocou o prego no caixão dos "algoritmos de peneira quântica" para o IG, que cobre muitas das tentativas até agora (e não é mencionado na publicação de Dave Bacon no blog): dx.doi.org/ 10.1137 / 080724101 . O artigo é pesado sobre a teoria da representação, mas a introdução não é, e é uma leitura muito boa.
Joshua Grochow

Respostas:

20

As referências podem ser encontradas na resposta de martinschwarz, mas aqui está um resumo de algumas reduções.

O grupo simétrico atua nos gráficos de n vértices permutando os vértices. Determinar se os dois gráficos são isomorfos é de tempo polinomial equivalente para computar um conjunto gerador de tamanho polinomial para um u t ( L ) .SnAut(G)

Redução para o HSP sobre o grupo simétrico (onde n é o número de variáveis ​​no gráfico). A função F é f ( P ) = P ( L ) , onde P é uma permutação em S n , e p ( L ) é a versão permutada de L . Em seguida, f é constante em classes laterais de uma u t ( G ) e distinto em classes laterais distintas (nota que a imagem de fSnnff(p)=p(G)pSnp(G)GfAut(G)fconsiste em todos os gráficos isomórficos para ). Desde o subgrupo escondido é exatamente A u t ( G ) , se pudéssemos resolver este HSP então teríamos o grupo gerador para A u t ( G ) , que é tudo o que precisamos para resolver GI (veja acima).GAut(G)Aut(G)

A redução para a HSP mais de . Se queremos saber se dois gráficos G e H nos n vértices são isomórficos, considere o gráfico K, que é a união disjunta de G e H nos 2 n vértices. Deixe- Z / 2 Z agir sobre os vértices trocando i com n + i para i = 1 , . . . , N . Qualquer umSnZ/2ZGHnKGH2nZ/2Zin+ii=1,...,n ou um u t ( K ) = ( A u t ( L ) x Um u t ( H ) ) s e m i d i r e c t Z / 2 Z . Como antes, deixe f ( xAut(K)=Aut(G)×Aut(H)Aut(K)=(Aut(G)×Aut(H))semidirectZ/2Z onde x é agora um elemento de S nZ / 2 Z que age em K como descrito. O subgrupo escondido associada a f é exactamente Um u t ( K ) , como na redução anterior. Se resolvermos este HSP, temos um grupo gerador para A u t ( K ) . É fácil verificar se o grupo gerador contém algum elemento que troque a cópia de G pela cópia de H dentrof(x)=x(K)xSnZ/2ZKfAut(K)Aut(K)GH (possuicomponente Z / 2 Z não trivial).KZ/2Z

Joshua Grochow
fonte
17

Você pode ler a recente postagem no blog de Dave Bacon sobre Graph Isomorphism, com links para a literatura.

Martin Schwarz
fonte
14

"Algoritmos quânticos para problemas algébricos" de Andrew Childs e Wim van Dam arXiv: 0812.0380 é um artigo de pesquisa muito bom que contém uma boa introdução ao HSP não-abeliano e sua relação com o isomorfismo de grafos.

dabacon
fonte