Encuentra todos los isomorfismos entre dos grafos planos

Question

Dado que el problema de isomorfismo de grafos planos se puede resolver en tiempo polinómico, ¿podemos encontrar todos los isomorfismos entre dos grafos planos en tiempo polinómico?

Answer 1

Como se señala en los comentarios, no existe un algoritmo general para enumerar los posibles isomorfismos exponenciales.

Sin embargo, se pueden enumerar los isomorfismos con un retraso polinómico, lo que significa que el tiempo transcurrido entre dos salidas es polinómico en el tamaño del grafo.

Se puede hacer una estimación aproximada utilizando el siguiente algoritmo para encontrar todos los isomorfismos del grafo $A$ al gráfico $B$ :

Preparación:

Enumerar todos los nodos con números de $1$ a $n$ y asignar a cada nodo un Graph $G_i$ que es un círculo con $n+1$ nodos y tiene $i$ picos (nodos adicionales que se conectan directamente al círculo. Así, estos gráficos $G_i$ son paiwise nonisomorphic. Para cada $G_i$ marcar un nodo de conexión. Marcamos un nodo en el gráfico $A$ o $B$ conectando este nodo con el nodo de conexión de $G_i$ . Como utilizamos dos copias de $G_i$ (uno para $A$ y uno para $B$ ) los denotamos con $G_i^A$ y $G_i^B$ . Si cada nodo de $A$ está marcado por un gráfico distinto $G_i^A$ y cada nodo de $B$ está marcado por un gráfico distinto $G_i^B$ estas gráficas son planas como $G_i^J$ es plano y está conectado por una sola arista. Cada uno de estos gráficos tiene $O(n^2)$ nodos. Así, comprobar si son isomorfos es polinómico en el tamaño de $A$ .

Enumeración:

Find_Isomorphism(i) {
   mark node $a_i$ with graph $G_i^A$
   for j in 1, ... , n {
     if node $b_j$ is 
     mark node $b_j$ with graph $G_i^B$
     if marked graphs $A$ and $B$ are isomorphic {
       if (i = n) {
         Output_Isomorphism
       } else {
         Find_Isomorphism(i+1)
       }
     }
     unmark node $b_j$
   }
}

El isomorfismo está codificado por la permutación de los grafos marcadores $G_i$ .

El procedimiento Find_Isomorphism entra en recursión sólo si los grafos marcados siguen siendo isomorfos. Así, se encuentra un isomorfismo siempre que se alcanza la mayor profundidad de recursión. En cada nivel de recursión, como máximo $n$ se realizan pruebas de isomorfismo gráfico. Como hemos $n$ niveles, el retardo entre las salidas de dos isomorfismos es de aproximadamente $O(n^2)$ veces la complejidad del problema de isomorfismo de grafos del grafo marcado, que es polinómica como se ha mostrado anteriormente.

Nota: Hay formas mucho más eficaces de marcar los nodos que en este ejemplo.

Editar: Es fácil ver que un algoritmo de retraso polinómico es polinómico si su salida es polinómica.

Answer 2

Si $\psi$ es un isomorfismo fijo de un grafo $G$ a un gráfico $H$ entonces cada isomorfismo de $G$ a $H$ es la composición de $\psi$ con un elemento de $\mathrm{Aut}(H)$ . Así que puedo especificar el conjunto de isomorfismos de $G$ a $H$ dando $\psi$ y un conjunto de generadores para $\mathrm{Aut}(H)$ .

Así que los comentarios sobre los "isomorfismos exponencialmente numerosos" parecen no tener sentido. Dado un algoritmo de tiempo polinómico para calcular el grupo de automorfismo de un grafo plano, podemos producir un isomorfismo y un conjunto de generadores en tiempo polinómico.