Isomorfismo gráfico "minúsculo"

19

Mientras pensaba en la complejidad de probar el isomorfismo de los gráficos asimétricos (vea mi pregunta relacionada sobre teoría), me vino a la mente una pregunta complementaria.

Supongamos que tenemos una máquina de Turing de tiempo polinomial que en la entrada genera un gráfico con nodos.M 1 n G M , n nM1nGM,nn

Podemos definir el problema :Π MΠM

("Tiny" GI): Dado un gráfico , ¿ es isomorfo a ?G = ( V , E ) G G M , | V |G=(V,E)GGM,|V|

En otras palabras, debemos comparar un gráfico dado con un gráfico de "referencia" del mismo tamaño generada por una máquina de Turing polinomio tiempo fijo .METROM

Para todas las máquinas de Turing tiempo polinomio , tenemos , y para muchos de ellos tenemos . Pero, ¿es cierto para todos los ? ¿Se conoce el problema?M Π MN P Π MP MMΠMNPΠMP
M

A primera vista, pensé que cada debería ser mucho más fácil que , porque para cada solo hay un gráfico de "referencia" de ese tamaño y quizás las simetrías / asimetrías de los gráficos generados por pueden explotarse y ser eficiente El probador de isomorfismo ad-hoc se puede construir ... pero no es cierto: puede contener algún tipo de máquina de Turing universal polinomial que utiliza la entrada (unaria) para generar gráficos de referencia completamente diferentes (en la estructura) como aumentaΠ M G I n M M 1 n nΠMGInMM1nn

Marzio De Biasi
fuente
Interesante, ¿Conoces un ejemplo de máquina de Turing de tiempo P M que genere el gráfico G M , N ? MGM,N
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Un ejemplo trivial para el cual Π MP , es un TM M que simplemente genera n vértices aislados (u otro es un TM que genera K n ). Sin pérdida de generalidad, también podemos pensar en un modelo en el que cada tiempo polinomial TM sobre el alfabeto binario genera un gráfico de referencia: simplemente seleccione los primeros bits de la cinta después de que se detenga e interprete como la matriz de adyacencia de . ΠMPMnKnn 2 G M , nn2GM,n
Marzio De Biasi
Por TM que garantiza que tiene ciclo de Hamilton, entonces supongo no está en . M G M , n Π M PMGM,nΠMP
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Creo que no es cierto: simplemente elija una TM que simplemente construya un ciclo de nodos: para todos los el gráfico de referencia, que tiene un ciclo hamiltoniano, es fácilmente comprobable en tiempo polinómico. Tengo en mente un ejemplo no trivial de un generador (bastante simple) para el que parece difícil demostrar que el problema está enn nnn P ; pero quiero hacer algunas pruebas con nauty antes de agregarlo a la pregunta. P
Marzio De Biasi
1
¿Qué pasa con el GI "Itsy Bitsy" donde para una M y una N fijas tenemos que decidir si las dos gráficas generadas en 1 ^ n son iguales? (Este es un lenguaje unario.)
domotorp

Respuestas:

6

[Esto es más de unos pocos comentarios extendidos que una respuesta.]

1) Si G I P , entonces no hay un límite de polinomio fijo en la complejidad del tiempo de todos Π M , incluso para M que solo toman tiempo, digamos, n 3 : Si para todo el tiempo- n 3 M , Π MD T I M E ( n k ) , entonces el siguiente es un algoritmo de poli-tiempo para GI. En la entrada ( G , H ) , construir una máquina de Turing nunca se ejecuta durante más de n 3 pasos en entradas de tamaño nGIPΠMMn3n3 MΠMDTIME(nk)(G,H) M G con un reloj que asegure que M GMGMGn3n, y tal que M G ( 1 | V ( G ) | ) = G , y luego resuelva Π M G ( H )MG(1|V(G)|)=GΠMG(H) en el tiempo O ( n k ) .O(nk)

2) Dado que para cualquier M , Π M no es más difícil que GI, uno podría pensar que el mejor resultado en la línea de " Π M parece no estar enMΠMΠM P " que uno podría esperar es un resultado de integridad GI. Sin embargo, me parece poco probable que alguien Π M esté completo GI, al menos por las siguientes razones:PΠM

  • Todos los resultados de integridad GI que conozco son para clases bastante grandes de gráficos, en lugar de tener un solo gráfico de cada tamaño. Incluso si elimina por completo el requisito de eficiencia, no conozco ninguna lista de gráficos G 1 , G 2 , ... de tal manera que | V ( G n ) | = n (o incluso p o l y (G1,G2,|V(Gn)|=n n ) ) de modo que la prueba de isomorfismo para G n sea ​​completa con IG.poly(n)Gn

  • En una nota relacionada, la mayoría (¿todos?) Los resultados de completitud GI no son meramente reducciones de muchos, sino que tienen la siguiente forma: hay una función f tal que dada una instancia ( G , H ) de GI, ( f ( G ) , f ( H ) )f(G,H)(f(G),f(H)) es una instancia del otro problema de GI completo. (Estos son solo morfismos poli-temporales de relaciones de equivalencia, o lo que Fortnow y yo llamamos "reducciones de kernel"). Podemos demostrar fácilmente incondicionalmente que no existe tal reducción de GI a cualquier Π M (incluso si modifica la definición para permitir MΠMMpara generar múltiples gráficos). Sugerencia: Obtenga una contradicción al mostrar que cualquier f debe tener su imagen completamente contenida en { G M , n } n 0 .f{GM,n}n0

3) A pesar de que uno podría construir M basado en una TM universal como se sugiere en la pregunta, quizás uno pueda construir un probador eficiente, pero no de manera eficiente. Es decir, tal vez para cada M , Π M está en P / p o l y ?MMΠMP/poly

Joshua Grochow
fuente
1

No tengo respuesta a su pregunta, pero propongo considerar una versión más restringida de Π M para la cual podemos demostrar que se encuentra en P.ΠM

Consideremos solo familias de gráficos de modo que el número de aristas crezca logarítmicamente. Formalizaré esto reformulando la formulación de su problema, también para ver si lo he entendido correctamente.

Un gráfico no dirigido G con n aristas se puede describir con un n 2 - nGn2 cadenas de bits largas, simplemente concatene las entradas de la matriz de adyacencia deGen el triángulo superior. Por lo tanto hay2 n 2 - nn2n2G2 posibles gráficos ennvértices. Se deduce que cualquier funciónf:NNtal que0f(n)<2n2-2n2n2nf:NN n2 para todondescribe una familia de gráficos. Para cualquier funciónfcomputable de manera eficiente,definimosΠfcomo G0f(n)<2n2n2nfΠfΠ fG  es isomorfo a la gráfica descrita por  f ( | V ( G ) | )

GΠfG is isomorph to the graph described by f(|V(G)|)

Para un número natural x sea b 1 ( x ) el número de 1 en su representación binaria. Ahora, consideremos solo Π f para funciones computables de manera eficiente f para las cuales sostiene que b 1 ( f ( n ) ) O ( log nxb1(x)Πff ) que es familias de gráficos para los cuales el número de aristas crece solo logarítmicamente, como se indicó anteriormente .

b1(f(n))O(logn)

Mostramos que Π f para esta clase de funciones está en P.Πf

Sea f una función de este tipo y G una gráfica de entrada con n vértices. Llamemos f ( n ) el gráfico de referencia. Hay como máximo aristas O ( log n ) en el gráfico de referencia. Por lo tanto, cada MCC (componente conectado de manera máxima) puede consistir en un máximo de vértices O ( log n ) de los cuales puede haber un máximo de n . Tenga en cuenta que para cualquier par de gráficos con solo O ( log n )fGnf(n)O(logn)O(logn)nO(logn) vértices podemos verificar trivialmente el isomorfismo en el tiempo polinomialmente wrt nnporque podemos probar todas las permutaciones. Por lo tanto, utilizando un algoritmo codicioso para asignar a cada MCC del gráfico de entrada un MCC en el gráfico de referencia, podemos determinar si los dos gráficos son isomorfos.

John D.
fuente
Si entendí bien su f , si el número de aristas crece solo logarítmicamente wrt n entonces es fácil eliminar los vértices aislados y probar en tiempo polinómico si G es isomorfo al gráfico de referencia. Así que para esta clase restringida, Π fP . fnGΠfP
Marzio De Biasi
De hecho, parece ser un argumento más fácil de lo que pensaba. Lo incorporaré en mi respuesta.
John D.
Teniendo en cuenta que la misma argumentación funciona para GI en general, esto no es realmente satisfactorio. Supongo que sería interesante si uno pudiera mejorar el límite superior en los bordes en la configuración Π f de modo que ya no se pueda demostrar que funciona de manera análoga para GI en general.
John D.
1
Para el argumento que usa la fuerza bruta (todas las permutaciones en cada componente), creo que realmente necesita que cada componente conectado tenga como máximo O ( log n /vértices log log n ) : ( log n ) ! es esencialmente ( log n ) log n = n log log n . Sin embargo, usar el algoritmo GI más conocido que lleva tiempo 2 v log v , puede reemplazarO(logn/loglogn)porO(log2n).
Joshua Grochow