Problema del isomorfismo de grafos

El problema del isomorfismo gráfico es el problema computacional para determinar si dos gráficos finitos son isomórficos.

No se sabe que el problema se pueda resolver en tiempo polinomial ni que sea NP-completo y, por lo tanto, puede estar en la clase de complejidad computacional NP-intermedia. Se sabe que el problema de isomorfismo gráfico está en la'jerarquía baja de la clase NP, lo que implica que no es NP completo a menos que la jerarquía de tiempo polinomial colapse a su segundo nivel. Al mismo tiempo, el isomorfismo para muchas clases especiales de gráficos se puede resolver en tiempo polinomial, y en la práctica el isomorfismo gráfico a menudo se puede resolver de manera eficiente.

Este problema es un caso especial del problema de isomorfismo subgráfico' que pregunta si un gráfico dado G contiene un subgráfico que es isomorfo a otro gráfico dado H y que se sabe que es NP-completo. También se sabe que es un caso especial del problema del subgrupo oculto no abeliano sobre el grupo simétrico.

En el área de reconocimiento de imágenes se conoce como la coincidencia gráfica exacta.

Estado del arte

El mejor algoritmo teórico actualmente aceptado se debe a Babai y Luks (1983), y se basa en el trabajo anterior de Luks (1982) combinado con un algoritmo subfactorial de V. N. Zemlyachenko (Zemlyachenko, Korneenko y Tyshkevich 1985). El algoritmo ha ejecutado el tiempo 2^{O(√n log n)} para gráficos con n vértices y se basa en la clasificación de grupos finitos simples. Sin CFSG, László Babai (1980) obtuvo primero un límite 2^{O (√n log2 n)} ligeramente más débil, y Babai & Luks (1983) lo extendió a los gráficos generales. La mejora del exponente √n es un gran problema abierto; para gráficos fuertemente regulares esto fue hecho por Spielman (1996). Para hipergrafos de rango limitado, Babai y Codenotti (2008) obtuvieron un límite superior subexponencial que coincide con el caso de los gráficos.

En noviembre de 2015, Babai anunció un algoritmo de tiempo quasipolynomial para todos los gráficos, es decir, uno con tiempo de ejecución $2^{O((\log n)^{c})}$ para algunos arreglados $c>0$ . El 4 de enero de 2017, Babai se retractó del reclamo cuasi-polinomial y declaró un límite de tiempo sub-exponencial en su lugar después de Harald Helfgott descubrió un defecto en la prueba. El 9 de enero de 2017, Babai anunció una corrección (publicada en su totalidad el 19 de enero) y restauró el reclamo cuasi polinomial, con Helfgott confirmando la solución. Helfgott afirma además que uno puede tomar c = 3, por lo que el tiempo de ejecución es 2^{O((log n) 3)}. La nueva prueba aún no ha sido revisada por completo.

Existen varios algoritmos prácticos competitivos para el isomorfismo gráfico, como los debidos a McKay (1981), Schmidt y Druffel (1976) y Ullman (1976). Si bien parecen funcionar bien en gráficos aleatorios, una desventaja importante de estos algoritmos es su rendimiento de tiempo exponencial en el peor de los casos.

El problema de isomorfismo gráfico es computacionalmente equivalente al problema de calcular el grupo de automorfismo de un gráfico, y es más débil que el problema de isomorfismo del grupo de permutación y el problema de intersección del grupo de permutación. Para los últimos dos problemas, Babai, Kantor y Luks (1983) obtuvieron límites de complejidad similares a los del isomorfismo gráfico.

Casos especiales resueltos

Varios casos especiales importantes del problema del isomorfismo gráfico tienen soluciones eficientes de tiempo polinomial:

• Árboles

• Gráficos planos (De hecho, el isomorfismo gráfico plano está en el espacio de registro, una clase contenida en P)

• Gráficos de intervalo

• Gráficos de permutación

• Gráficos circulares

• Gráficos de parámetros acotados

• Gráficos de ancho de árbol delimitado

• Gráficos del genus delimitado (Nota: los gráficos planos son gráficos del género 0)

• Gráficos de grado limitado

• Gráficos con multiplicidad de autovalores acotada

• k-Gráficos contractibles (una generalización de grado limitado y género acotado)

• El isomorfismo de conservación del color de los gráficos de colores con multiplicidad de colores delimitados (es decir, como mucho k vértices tienen el mismo color para un k fijo) está en la clase NC, que es una subclase de P

Clase de complejidad GI

Dado que el problema del isomorfismo gráfico no se sabe que sea NP-completo ni conocido como tratable, los investigadores han tratado de comprender el problema definiendo un nuevo GI de clase, el conjunto de problemas con una reducción de Turing en tiempo polinomial al isomorfismo gráfico problema. Si, de hecho, el problema de isomorfismo gráfico es solucionable en tiempo polinomial, GI sería igual a P.

Como es común para las clases de complejidad dentro de la jerarquía de tiempo polinomial, un problema se llama GI-hard si hay una reducción de Turing en tiempo polinomial desde cualquier problema en GI a ese problema, es decir, una solución de tiempo polinomial a un problema GI-hard produciría una solución de tiempo polinomial al problema del isomorfismo gráfico (y por lo tanto todos los problemas en GI). Un problema $X$ se llama completo para GI, o GI-complete, si es tanto GI-hard y una solución de tiempo polinomial al problema GI produciría una solución de tiempo polinomial para $X$.

El problema del isomorfismo gráfico está contenido tanto en NP como en co-AM. GI está contenido en y bajo para Parity P, así como también está contenido en el SPP de clase potencialmente mucho más pequeño. Que se encuentre en la Paridad P significa que el problema del isomorfismo gráfico no es más difícil que determinar si una máquina de Turing no determinista de tiempo polinomial tiene un número par o impar de rutas de aceptación. GI también está contenido en y bajo para ZPP^NP. Esto esencialmente significa que un algoritmo eficiente de Las Vegas con acceso a un oráculo de NP puede resolver el isomorfismo gráfico tan fácilmente que no obtiene poder de poder hacerlo en tiempo constante.

Problemas GI-completos y GI-difícil

Isomorfismo de otros objetos

Hay una serie de clases de objetos matemáticos para los que el problema del isomorfismo es un problema GI completo. Algunos de ellos son gráficos dotados de propiedades o restricciones adicionales:

• dígrafos

• gráficos etiquetados, con la condición de que no se requiera un isomorfismo para conservar las etiquetas, sino solo la relación de equivalencia que consiste en pares de vértices con la misma etiqueta

• "gráficos polarizados" (hechos de un gráfico completo K_m y un gráfico vacío K_n más algunos bordes que conectan los dos; su isomorfismo debe preservar la partición)

• Gráficos de 2 colores

• estructuras finitas explícitamente dadas

• multigrafos

• hipergramas

• autómatas finitos

• Procesos de decisión de Markov

• clase conmutable 3 nilpotente (es decir, xyz = 0 para cada elemento x, y, z) semigrupos

• Algebras asociativas de rango finito sobre un campo fijo algebraicamente cerrado con radical cuadrado cero y factor conmutativo sobre el radical.

• gramáticas libres de contexto

• diseños de bloques incompletos equilibrados

• Reconociendo el isomorfismo combinatorio de politopes convexos representados por incidencias de facetas en los vértices.

GI: completa clases de gráficos

Una clase de gráficos se llama GI-complete si el reconocimiento de isomorfismo para los gráficos de esta subclase es un problema de GI-complete. Las siguientes clases son GI-completas:

• gráficos conectados

• gráficos de diámetro 2 y radio 1

• gráficos acíclicos dirigidos

• gráficos regulares

• gráficos bipartitos sin subgrafos muy regulares no triviales

• Gráficos eulerianos bipartitos

• gráficos regulares bipartitos

• gráficos de línea

• gráficos divididos

• gráficos de cordal

• gráficas autocomplementarias regulares

• gráficos politopales de politopos convexos generales, simples y simpliciales en dimensiones arbitrarias.

Muchas clases de dígrafos son también GI-completas.

Otros problemas GI-completos

Hay otros problemas no triviales de GI-complete además de los problemas de isomorfismo.

• El reconocimiento de la autocomplementariedad de un gráfico o un dígrafo.

• Un problema de camarilla para una clase de los llamados M-gráficos. Se muestra que encontrar un isomorfismo para los gráficos de n-vértice es equivalente a encontrar una n-camarilla en un M-gráfico de tamaño n². Este hecho es interesante porque el problema de encontrar una (n - ε) -clique en un M-gráfico de tamaño n² es NP-completo para arbitrariamente pequeño ε positivo.

• El problema del homeomorfismo de 2 complejos.

Problemas GI-hard

• El problema de contar el número de isomorfismos entre dos gráficos es el tiempo polinomial equivalente al problema de saber si existe uno.

• El problema de decidir si dos politopos convexos dados por la descripción V o la descripción H son isomorfos de forma proyectiva o afín. Esto último significa la existencia de un mapa descriptivo o afín entre los espacios que contienen los dos politopos (no necesariamente de la misma dimensión) que induce una biyección entre los politopos.

Comprobación del programa

Manuel Blum y Sampath Kannan (1995) han mostrado un verificador probabilístico para programas de isomorfismo gráfico. Supongamos que P es un procedimiento reclamado de tiempo polinomial que verifica si dos gráficos son isomorfos, pero no es de confianza. Para verificar si G y H son isomorfos:

• Pregunte a P si G y H son isomorfos.

• Si la respuesta es 'sí':

• Intente construir un isomorfismo usando P como subrutina. Marque un vértice u en G y v en H, y modifique los gráficos para que sean distintivos (con un pequeño cambio local). Pregunte a P si los gráficos modificados son isomorfos. Si no, cambie v a un vértice diferente. Continúa buscando

• O el isomorfismo se encontrará (y se podrá verificar), o P se contradirá a sí mismo.

• Si la respuesta es "no":

• Realice las siguientes 100 veces. Elija aleatoriamente G o H, y permute aleatoriamente sus vértices. Pregunte a P si el gráfico es isomorfo a G y H. (Como en el protocolo AM para el gráfico no isomorfismo).

• Si alguna de las pruebas falla, juzgue a P como un programa inválido. De lo contrario, responda "no".

Este procedimiento es polinomial y da la respuesta correcta si P es un programa correcto para el isomorfismo gráfico. Si P no es un programa correcto, pero responde correctamente en G y H, el verificador dará la respuesta correcta o detectará el comportamiento no válido de P. Si P no es un programa correcto y responde incorrectamente en G y H, el verificador detectará el comportamiento inválido de P con alta probabilidad, o responderá incorrectamente con probabilidad 2^-100.

En particular, P se usa solo como caja negra.

• Datos: Q3738036