Describo un enfoque para el isomorfismo gráfico que probablemente tiene falsos positivos, y tengo curiosidad por saber si hay literatura que indique que no funciona.
Dadas dos matrices de adyacencia , un método ciertamente ingenuo para verificar el isomorfismo es verificar si para cada fila u de G , hay una fila v de G que es una permutación de la fila u , denotada por G [ u ] ∼ H [ v ] . Un poco más estricta es la pregunta, ¿hay un "isomorfismo local" π para el cual G [ u ] ∼ H [ π ( u ) ]para todas las filas La producción de un isomorfismo local se puede hacer en tiempo polinomial construyendo una matriz A con A [ u , v ] = ( G [ u ] ∼ H [ v ] ) ; entonces G y H son localmente isomórficos si A tiene una cubierta de ciclo, y cada cubierta de ciclo es un isomorfismo local.
Todos los gráficos regulares engañan a este método, obviamente, por lo que un enfoque un poco menos ingenuo es calcular las potencias de las matrices y verificar si hay isomorfismo local, explotando el hecho de que tienes múltiples matrices configurando A [ u , v ] = 0 cuando encuentre cualquier potencia tal que G k [ u ] ≁ H k [ v ]y verificando la cobertura del ciclo solo al final. Un enfoque aún menos ingenuo es encontrar un conjunto de polinomios, de hecho un conjunto de circuitos aritméticos, y establecer cuando encontramos cualquier polinomio p con p ( G ) [ u ] ≁ p ( H ) [ v ] .
Esto me parece un enfoque increíblemente ingenuo para el isomorfismo gráfico, por lo que estoy seguro de que alguien ya lo ha investigado y demostrado un teorema como
Pregunta: ¿Existe tal teorema? He buscado en la literatura y no puedo encontrarla.
algoritmo para isomorfismo gráfico. Si tales polinomios (o circuitos aritméticos) son fáciles de adivinar, entonces tenemos un algoritmo coRP . Si siempre existe una (familia de) circuitos aritméticos para presenciar isomorfismo no local, entonces esto proporciona un algoritmo coNP .
Tenga en cuenta que podemos evitar el problema de que las entradas de matrices de alta potencia crecen demasiado calculando los polinomios sobre campos pequeños, por ejemplo, calculando módulos primos pequeños. En un algoritmo coNP , el probador puede proporcionar estos primos.
fuente