problema de isomorfismo de grafos

El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomorfos . ^{[ 1 ]}

No se sabe si el problema es resoluble en tiempo polinomial ni si es NP-completo , por lo que podría pertenecer a la clase de complejidad computacional NP-intermedia . Se sabe que el problema del isomorfismo de grafos se encuentra 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 se reduzca a su segundo nivel. ^{[ 2 ]} Al mismo tiempo, el isomorfismo para muchas clases especiales de grafos puede resolverse en tiempo polinomial, y en la práctica, el isomorfismo de grafos a menudo puede resolverse de manera eficiente. ^{[ 3 ] [ 4 ]}

Este problema es un caso especial del problema de isomorfismo de subgrafos ^{[ 5 ]} , que pregunta si un grafo dado G contiene un subgrafo isomorfo a otro grafo dado H ; se sabe que este problema es NP-completo. También se sabe que es un caso especial del problema del subgrupo oculto no abeliano sobre el grupo simétrico ^{[ 6 ]} .

En el ámbito del reconocimiento de imágenes se conoce como el problema de coincidencia exacta de grafos . ^{[ 7 ]}

En noviembre de 2015, László Babai anunció un algoritmo de tiempo cuasipolinomial para todos los grafos, es decir, uno con tiempo de ejecución${\displaystyle 2^{O((\log n)^{c})}}$para algún fijo${\displaystyle c>0}$. ^{[ 8 ] [ 9 ] [ 10 ] [ 11 ]} El 4 de enero de 2017, Babai se retractó de la afirmación cuasipolinómica y en su lugar declaró una cota de tiempo subexponencial después de que Harald Helfgott descubriera un fallo en la demostración. El 9 de enero de 2017, Babai anunció una corrección (publicada en su totalidad el 19 de enero) y restauró la afirmación cuasipolinómica, con Helfgott confirmando la corrección. ^{[ 12 ] [ 13 ]} Helfgott afirma además que se puede tomar c = 3 , por lo que el tiempo de ejecución es 2 ^{O((log n ) 3 )} . ^{[ 14 ] [ 15 ]} Babai publicó un "informe preliminar" sobre trabajos relacionados en el Simposio de 2019 sobre Teoría de la Computación , describiendo un algoritmo cuasipolinomial para la canonización de grafos , ^{[ 16 ]} pero a partir de 2025La versión completa de estos algoritmos permanece inédita.

Antes de esto, el mejor algoritmo teórico aceptado se debía a Babai y Luks (1983) , y se basaba en el trabajo anterior de Luks (1982) combinado con un algoritmo subfactorial de VN Zemlyachenko ( Zemlyachenko, Korneenko y Tyshkevich 1985 ) . El algoritmo tiene un tiempo de ejecución de 2 ^{O( √ n  log n  )} para grafos con n vértices y se basa en la clasificación de grupos simples finitos . Sin este teorema de clasificación , se obtuvo una cota ligeramente más débil de 2 ^{O( √ n  log 2 n )}  primero para grafos fuertemente regulares por László Babai ( 1980 ) , y luego Babai y Luks (1983) la extendieron a grafos generales . Spielman (1996) mejoró el exponente √ n para grafos fuertemente regulares . Para hipergrafos de rango acotado, Babai y Codenotti (2008) obtuvieron una cota superior subexponencial que coincide con el caso de los grafos . 

Existen varios algoritmos prácticos competitivos para el isomorfismo de grafos, como los de McKay (1981) , Schmidt y Druffel (1976) , Ullman (1976) y Stoichev (2019) . Si bien parecen funcionar bien en grafos aleatorios , una desventaja importante de estos algoritmos es su rendimiento de tiempo exponencial en el peor de los casos . ^{[ 17 ]}

El problema del isomorfismo de grafos es computacionalmente equivalente al problema de calcular el grupo de automorfismos de un grafo, ^{[ 18 ] [ 19 ] [ 20 ]} y es más débil que el problema del isomorfismo de grupos de permutaciones y el problema de la intersección de grupos de permutaciones. Para estos dos últimos problemas, Babai, Kantor y Luks (1983) obtuvieron cotas de complejidad similares a las del isomorfismo de grafos.

Varios casos especiales importantes del problema del isomorfismo de grafos tienen soluciones eficientes en tiempo polinomial:

• Árboles ^{[ 21 ] [ 22 ]}
• Grafos planares ^{[ 23 ]} (De hecho, el isomorfismo de grafos planares está en el espacio logarítmico , ^{[ 24 ]} una clase contenida en P )
• Gráficos de intervalos ^{[ 25 ]}
• Gráficos de permutación ^{[ 26 ]}
• Gráficos circulantes ^{[ 27 ]}
• Gráficos de parámetros acotados
  • Gráficos de ancho de árbol limitado ^{[ 28 ]}
  • Grafos de género acotado ^{[ 29 ]} (Los grafos planares son grafos de género 0.)
  • Grafos de grado acotado ^{[ 30 ]}
  • Gráficos con multiplicidad de valores propios acotada ^{[ 31 ]}
  • Grafos k -contraíbles (una generalización del grado acotado y el género acotado) ^{[ 32 ]}
  • El isomorfismo que preserva el color de ^los grafos coloreados con multiplicidad de color acotada (es decir, como máximo k vértices tienen el mismo color para un k fijo ) está en la clase NC , que es una subclase de P. [ ^{33 ]}

Dado que el problema del isomorfismo de grafos no se conoce como NP-completo ni como tratable, los investigadores han buscado comprender mejor el problema definiendo una nueva clase GI , el conjunto de problemas con una reducción de Turing en tiempo polinomial al problema del isomorfismo de grafos. ^{[ 34 ]} Si, de hecho, el problema del isomorfismo de grafos es resoluble en tiempo polinomial, GI sería igual a P. Por otro lado, si el problema es NP-completo, GI sería igual a NP y todos los problemas en NP serían resolubles en tiempo cuasi-polinomial.

Como es común para las clases de complejidad dentro de la jerarquía de tiempo polinomial , un problema se denomina GI-difícil si existe una reducción de Turing de tiempo polinomial desde cualquier problema en GI a ese problema, es decir, una solución de tiempo polinomial para un problema GI-difícil produciría una solución de tiempo polinomial para el problema de isomorfismo de grafos (y por lo tanto para todos los problemas en GI ).${\displaystyle X}$se denomina completo para GI , o GI-completo , si es a la vez GI-difícil y una solución de tiempo polinomial al problema GI produciría una solución de tiempo polinomial${\displaystyle X}$.

El problema del isomorfismo de grafos está contenido tanto en NP como en co- AM . GI está contenido en y es bajo para Paridad P , así como también está contenido en la clase potencialmente mucho más pequeña SPP . ^{[ 35 ]} Que esté en Paridad P significa que el problema del isomorfismo de grafos 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 caminos de aceptación. GI también está contenido en y es bajo para ZPP ^NP . ^{[ 36 ]} Esto esencialmente significa que un algoritmo eficiente de Las Vegas con acceso a un oráculo NP puede resolver el isomorfismo de grafos tan fácilmente que no gana poder al tener la capacidad de hacerlo en tiempo constante.

Manuel Blum y Sampath Kannan ( 1995 ) demostraron un verificador probabilístico para programas de isomorfismo de grafos. Supongamos que P es un procedimiento que, según se afirma, realiza una comprobación de tiempo polinomial y verifica si dos grafos son isomorfos, pero no es de confianza. Para comprobar si los grafos G y H son isomorfos: 

• Pregúntale a P si G y H son isomorfos.
  • Si la respuesta es "sí":
    • Intenta construir un isomorfismo usando P como subrutina. Marca un vértice u en G y v en H , y modifica los grafos para que sean distintos (con un pequeño cambio local). Pregúntale a P si los grafos modificados son isomorfos. Si no lo son, cambia v por otro vértice. Continúa la búsqueda.
    • O bien se encontrará el isomorfismo (y se podrá verificar), o bien P se contradecirá a sí mismo.
  • Si la respuesta es "no":
    • Realice lo siguiente 100 veces. Elija aleatoriamente G o H y permute aleatoriamente sus vértices. Pregunte a P si el grafo es isomorfo a G y H. (Como en el protocolo AM para la no isomorfía de grafos).
    • Si alguna de las pruebas falla, considere que P es un programa inválido. De lo contrario, responda "no".

Este procedimiento es de tiempo polinomial y da la respuesta correcta si P es un programa correcto para el isomorfismo de grafos. Si P no es un programa correcto, pero responde correctamente en G y H , el verificador dará la respuesta correcta o detectará un comportamiento inválido de P. Si P no es un programa correcto y responde incorrectamente en G y H , el verificador detectará un comportamiento inválido de P con alta probabilidad o responderá incorrectamente con una probabilidad de 2 ⁻¹⁰⁰ .

Cabe destacar que P se utiliza únicamente como una caja negra.

Los grafos se utilizan comúnmente para codificar información estructural en muchos campos, incluyendo la visión por computadora y el reconocimiento de patrones , y la comparación de grafos , es decir, la identificación de similitudes entre grafos, es una herramienta importante en estas áreas. En estas áreas, el problema del isomorfismo de grafos se conoce como comparación exacta de grafos. ^{[ 48 ]}

En quimioinformática y química matemática , la prueba de isomorfismo de grafos se utiliza para identificar un compuesto químico dentro de una base de datos química . ^{[ 49 ]} Además, en química matemática orgánica, la prueba de isomorfismo de grafos es útil para la generación de grafos moleculares y para la síntesis computacional .

La búsqueda en bases de datos químicas es un ejemplo de minería de datos gráfica , donde se suele utilizar el enfoque de canonización de grafos . ^{[ 50 ]} En particular, varios identificadores de sustancias químicas , como SMILES e InChI , diseñados para proporcionar una forma estándar y legible para humanos de codificar información molecular y facilitar la búsqueda de dicha información en bases de datos y en la web, utilizan el paso de canonización en su cálculo, que es esencialmente la canonización del grafo que representa la molécula. ^{[ 51 ]}

En la automatización del diseño electrónico, el isomorfismo de grafos es la base del paso de diseño de circuitos Layout Versus Schematic (LVS), que consiste en verificar si los circuitos eléctricos representados por un esquema de circuito y un diseño de circuito integrado son iguales. ^{[ 52 ]}

• problema de automorfismo de grafos
• Canonización de gráficos