Existe um algoritmo eficiente para determinar se um gráfico tem ou não um automorfismo não trivial?

Estou trabalhando em um problema relacionado aos quadrados latinos e quero um método para o que se resume basicamente ao problema de decisão:

Entrada : Um gráfico finito e simples G.
Saída : YESse G tiver um automorfismo não trivial, NOcaso contrário.

Conseqüentemente...

Pergunta : Existe um algoritmo eficiente para determinar se um gráfico possui ou não um automorfismo não trivial?

Poderíamos usar o Nauty ou o Bliss (e possivelmente alguns outros pacotes) para calcular todo o grupo automorfismo, mas eu não preciso disso; tudo o que preciso determinar é se é trivial ou não.

É possível que esse problema de decisão seja teoricamente equivalente em complexidade para "computar todo o grupo automorfismo" de alguma maneira. Não tenho certeza.

Para meu propósito, "eficiente" significa basicamente "mais rápido na prática do que computar todo o grupo automorfismo", mas também estou interessado na teoria por trás dele.

algorithms graphs graph-theory reference-request Rebecca J. Stones
fonte

Isso é equivalente ao isomorfismo do gráfico.

Yuval Filmus

@YuvalFilmus Até onde eu sei, não há redução conhecida de "Is

isomorphic to

" para "

possui um automorfismo não trivial". Obviamente, se

, sua união disjunta tem um automorfismo não trivial (troca

), mas qualquer automorfismo não trivial de

também seria um automorfismo não trivial de

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

G_{1} ≃ G_{2}

$G_1\simeq G_2$

G_{1}

$G_1$

G_{2}

$G_2$

G_{1}

$G_1$

G_{1} + G_{2}

$G_1+G_2$

precisa saber é o seguinte

Com relação à sua última pergunta, se for dado um oráculo ao GA, pode-se, em tempo polinomial, encontrar um conjunto gerador do grupo automorfismo, então GI é Turing redutível ao GA, o que não tenho certeza se é conhecido.

Ariel

@DavidRicherby E o que se segue? sciencedirect.com/science/article/pii/…

Yuval Filmus

@YuvalFilmus OK, então você está usando reduções de Turing e eu estou usando várias reduções. E acho que as reduções de Turing são mais relevantes para alguém que está realmente tentando resolver o problema.

David Richerby

Respostas:

Como você também está interessado na teoria subjacente, eu daria a você um algoritmo de tempo quase polinomial para o seu problema.

$u\neq v$ $G$ $u$ $v$

$G$ $G'$ $u$ $G$ $v$ $G'$

Then, for each $w\in N(u)$ attach to it a very long path, but only polynomially long.

Then, for each (copy of) $w\in N(copy\ of\ v)$ attach to it a very long path, but only polynomially long.

All the mentioned above very long path, but polynomially long, should be of the same length.

Call Babai's algorithm on the input of this newly produced pair of graphs.

If for any pair $(u, v)$ , we have a $YES$ answer from Babai's, answer $YES$ and halt.

If none returns a $YES$ answer, answer $NO$ and halt.

Clearly, attaching to all vertices in $N(u)$ and $N(v)$ forces the graph isomorphism of Babai's inner working mechanism of his algorithm to only map vertices in $N(u)$ to $N(v)$ . Thus, if Babai's answer is $YES$ then we can safely plug in back $u$ and $v$ to have a non-trivial automorphism of $G$ , since $G'$ is a copy of $G$ .

The run-time complexity is still quasi-poly.

Thinh D. Nguyen
fonte