Estoy trabajando en un problema relacionado con los cuadrados latinos, y quiero un método para lo que esencialmente se reduce al problema de decisión:
Entrada : Un gráfico simple finito G.
Salida : YES
si G tiene un automorfismo no trivial, de lo NO
contrario.
Por lo tanto...
Pregunta : ¿Existe un algoritmo eficiente para determinar si un gráfico tiene o no un automorfismo no trivial?
Podríamos usar Nauty o Bliss (y posiblemente otros paquetes) para calcular todo el grupo de automorfismo, pero no lo necesito; todo lo que necesito determinar es si es o no trivial.
Es posible que este problema de decisión sea teóricamente equivalente en complejidad a "calcular todo el grupo de automorfismo" de alguna manera. No estoy seguro.
Para mi propósito, "eficiente" básicamente significa "más rápido en la práctica que computar todo el grupo de automorfismo", pero también estoy interesado en la teoría detrás de esto.
fuente
Respuestas:
Como también está interesado en la teoría detrás de esto, le daría un algoritmo de tiempo cuasi-polinomial para su problema.
Todo el camino muy largo mencionado anteriormente, pero polinomialmente largo , debe ser de la misma longitud.
Llame al algoritmo de Babai en la entrada de este par de gráficos recién producido.
La complejidad del tiempo de ejecución sigue siendo cuasi-poli.
fuente