Ver el código de «Problema del isomorfismo de grafos»

El '''problema del isomorfismo gráfico''' es el [[problema computacional]] para determinar si dos [[Gráfica|gráficos]] finitos son [[Isomorfismo|isomórficos.]]

No se sabe que el problema se pueda resolver en [[P (clase de complejidad)|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<sup>O(√n log n)</sup> 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<sup>O (√n log2</sup> <sup>n)</sup> 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 [[Hipergrafo|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 <math>2^{O((\log n)^c)}</math> para algunos arreglados <math>c > 0</math> . 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<sup>O((log n) 3)</sup>. 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 simétrico|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:

* [[Árbol (informática)|Á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áfico circular|Gráficos circulares]]

* Gráficos de parámetros acotados

* Gráficos de ancho de árbol delimitado

* Gráficos del [[Genus (matemáticas)|genus]] delimitado (Nota: los gráficos planos son gráficos del género 0)

* Gráficos de [[Grado (teoría de grafos)|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 (clase de complejidad)|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 P y NP|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 [[P (clase de complejidad)|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 <math> X</math> 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 <math> X</math>.

El problema del isomorfismo gráfico está contenido tanto en '''NP''' como en co-[[AM]]. GI está contenido en y bajo para [[Party Poison|Parity P]], así como también está contenido en el [[Especie|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 [[Zope|ZPP]]<sup>NP</sup>.  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ígrafo|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<sub>m</sub> y un '''gráfico vacío''' K<sub>n</sub> más algunos bordes que conectan los dos; su isomorfismo debe preservar la partición) 

* Gráficos de 2 colores 

* [[Estructura|estructuras]] finitas explícitamente dadas

* [[Multigrafo|multigrafos]] 

* '''hipergramas'''

* [[Autómata finito|autómatas finitos]]

* '''Procesos de decisión de Markov'''

* clase '''conmutable''' 3 [[nilpotente]] (es decir, ''xyz'' = 0 para cada elemento ''x'', ''y'', ''z'') [[Semigrupo|semigrupos]] 

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

* [[Gramática libre de contexto|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 (geometría)|radio]] 1

* '''gráficos acíclicos dirigidos'''

* '''gráficos regulares''' 

* '''gráficos bipartitos''' sin '''subgrafos muy regulare'''s 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''<sup>2</sup>. Este hecho es interesante porque el problema de encontrar una (''n - ε'') -clique en un ''M''-gráfico de tamaño ''n''<sup>2</sup> 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<sup>-100</sup>.

En particular, ''P'' se usa solo como caja negra.
{{Control de autoridades}}
[[Categoría:Algoritmos]]
[[Categoría:Grafos]]
[[Categoría:Problemas computacionales]]
[[Categoría:Problemas no resueltos de las ciencias de la computación]]
[[Categoría:Morfismos]]