Prueba de isomorfismo de gráficos asimétricos

13

Durante la lectura de las preguntas ejemplos donde la unicidad de la solución hace que sea más fácil encontrar , una nueva (? Más fácil) pregunta vino a la mente: en realidad no sabemos si el isomorfismo de grafos ( problema) está en P .solyoPAG

Pero, ¿qué sucede si suponemos que tanto como G 2 son asimétricos (es decir, ambos tienen solo el automorfismo trivial (identidad))? ¿El problema se vuelve más fácil (tiempo polinómico)? sol1sol2

Nota: el problema no puede ser más difícil que el Automorfismo de Gráficos ( ), porque hay una reducción rápida: solo use G A en G 1 ∪ G 2solUNsolUNsol1∪sol2 , si la respuesta es sí, entonces los dos gráficos son isomorfos (vea también Johannes Köbler, Uwe Schöning, Jacobo Torán: El isomorfismo gráfico es bajo para PP . 401-411).

reference-request graph-isomorphism Marzio De Biasi
fuente
2
Con una probabilidad cercana a 1 a medida que n crece, su gráfico solo tiene el automorfismo trival por la complejidad de Kolmogorov.
Chad Brewbaker
1
+1 Buena pregunta, tu pregunta potencialmente conduce a un ataque contra P contra NP. Intente demostrar que no existe una reducción de Turing de a su problema. solUN
Mohammad Al-Turkistany
44
Este problema se conoce como el problema de isomorfismo de gráfico rígido. Si se puede resolver en tiempo polinómico o no, está ampliamente abierto. Hay algo de trabajo tratando de atacarlo a través de algoritmos cuánticos, por ejemplo, reduciéndolo al problema del turno oculto ( arxiv.org/abs/quant-ph/0510185 ) pero los resultados son en su mayoría negativos que muestran que las técnicas probadas no trabajo.
Mateus de Oliveira Oliveira
1
Es posible rigidizar cualquier gráfico de modo que tenga un solo endomorfismo (y, por lo tanto, automorfismo), al adjuntar gráficos mutuamente rígidos a cada vértice. Esto implica una reducción de Turing de GI a decidir el isomorfismo de los gráficos asimétricos. Por desgracia, no es polinomial.
András Salamon
1
Well Childs / Wocjan no está solo en el uso de rígido para denotar gráficos con un solo automorfismo. Hay una encuesta de Babai de 1994 que ya señala que la terminología no es el estándar www.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf. También en los tiempos modernos, rígido ha sido utilizado en este sentido por Jacobo Toran ( uni-ulm.de/fileadmin/website_uni_ulm/.../toran/hard.pdf ). Parece que es una cuestión de si el autor se preocupa por las incrustaciones o no. Pero utilicé asimétrica en mi respuesta para evitar confusiones.
Mateus de Oliveira Oliveira

Respuestas:

11

A petición de Marzio De Biasi, estoy convirtiendo mi comentario en una respuesta.

Un gráfico es asimétrico (algunos autores se refieren a él como rígido) si tiene un automorfismo único, es decir, la identidad. Como señaló Chad Brewbacker, la mayoría de los gráficos son asimétricos. Sin embargo, las siguientes dos preguntas están abiertas:

1) ¿El isomorfismo de los gráficos asimétricos en P?

2) ¿Se puede reducir el isomorfismo de los gráficos generales al isomorfismo de los gráficos asimétricos?

La pregunta 1) ha recibido mucha atención en la computación cuántica debido al hecho de que el isomorfismo de los gráficos asimétricos puede reducirse al problema del subgrupo oculto no beliano y al problema del cambio oculto no abeliano . Sin embargo, los resultados son negativos, lo que demuestra que hay que prepararse al menosΩ(norteIniciar sesión⁡norte) estados de subgrupos ocultos o estados de desplazamiento ocultos para tener suficiente información para resolver el problema del isomorfismo.

Mateus de Oliveira Oliveira
fuente