Não tenho conhecimento na área da teoria da complexidade envolvendo grupos, portanto peço desculpas se esse é um resultado bem conhecido.
Questão 1. Seja um gráfico simples e não direcionado da ordem n . Qual é a complexidade computacional (em termos de n ) de determinar se G é vértice-transitivo?
Recorde-se que um gráfico é vértice-transitivo se uma u t ( G ) actua transitively em
Não tenho certeza se a definição acima permite um algoritmo de tempo polinomial, pois pode ser que a ordem de seja exponencial.
No entanto, os gráficos transitivos em vértices têm outras propriedades estruturais que podem ser exploradas para poder determiná-las com eficiência, portanto, não tenho certeza de qual é o status da pergunta acima.
Outra subclasse interessante de gráficos transitivos em vértices que possui ainda mais estrutura é a classe de gráficos de Cayley . Portanto, é natural também fazer a seguinte pergunta relacionada
Questão 2. Qual é a complexidade computacional de determinar se um gráfico é um gráfico de Cayley?
Respostas:
Não tenho uma resposta completa, mas acho que os dois problemas estão abertos.
O artigo de Jajcay, Malnič, Marušič [3] está relacionado à sua primeira pergunta. Eles fornecem algumas ferramentas para testar a transitividade de vértices. Eles dizem na introdução que:
Observe que o teste de transitividade de vértice pode ser realizado testando o isomorfismo do gráfico vezes. Faça duas cópias G e G ' do seu gráfico, com âncoras especiais (como caminhos de comprimento n + 1 ) em u ∈ V ( G ) e v ∈ V ( G ′ ) . Existe um isomorfismo entre G e G ' se e somente se o gráfico original tiver um automorfismo mapeado de u para v . Assim, você pode testar a tansatividade do vértice fixando um vérticen−1 G G′ n+1 u∈V(G) v∈V(G′) G G′ u v verificar se há automorfismos mapeando x para todos os outros vértices.x x
Observe também que, se o teste de transitividade de vértices pode ser realizado em tempo polinomial, o mesmo ocorre com o teste de isomorfismo para gráficos transitivos de vértices. Isso ocorre porque dois gráficos transitivos de vértice são isomórficos se e somente se sua união dissuasiva for transitiva de vértice. Eu acredito que a complexidade do isomorfismo de grafos para grafos transitivos por vértices não é conhecida.
Para a segunda pergunta, encontrei um resultado parcial. Um gráfico circulante é um gráfico de Cayley em um grupo cíclico. Evdokimov e Ponomarenko [2] mostram que o reconhecimento de gráficos circulantes pode ser feito em tempo polinomial. Também o capítulo do livro de Alspach [1, Capítulo 6: Gráficos de Cayley, Seção 6.2: Reconhecimento] seria interessante para você, apesar de dizer que:
fonte