Problema de isomorfismo de grafos

Problema no resuelto en la teoría de la complejidad computacional

Problema sin resolver en informática :

¿Puede el problema del isomorfismo de grafos resolverse en tiempo polinomial?

(más problemas sin resolver en informática)

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

No se sabe que el problema sea solucionable 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 de grafos 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. ^[2] Al mismo tiempo, el isomorfismo para muchas clases especiales de grafos se puede resolver en tiempo polinomial y, en la práctica, el isomorfismo de grafos a menudo se puede resolver 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 que es 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 de subgrupo oculto no abeliano sobre el grupo simétrico ^[6] .

En el área de reconocimiento de imágenes se le conoce como correspondencia gráfica exacta. ^[7]

Lo último

En noviembre de 2015, László Babai anunció un algoritmo de tiempo cuasi-polinomial para todos los grafos, es decir, uno con tiempo de ejecución para algún fijo . ^{[8] [9] [10] [11]} El 4 de enero de 2017, Babai se retractó de la afirmación cuasi-polinomial y declaró un límite de tiempo sub-exponencial en su lugar después de que Harald Helfgott descubriera una falla en la prueba. El 9 de enero de 2017, Babai anunció una corrección (publicada en su totalidad el 19 de enero) y restauró la afirmación cuasi-polinomial, con Helfgott confirmando la corrección. ^{[12] [13]} Helfgott afirma además que uno puede tomar c = 3 , por lo que el tiempo de ejecución es 2 ^{O((log n ) 3 )} . ^{[14] [15]} ${\displaystyle 2^{O((\log n)^{c})}}$ ${\displaystyle c>0}$

Antes de esto, el algoritmo teórico mejor aceptado se debió a Babai y Luks (1983), y se basó 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 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 , László Babai (1980) obtuvo primero un límite ligeramente más débil 2 O ( √ n log 2 n ) para grafos ^{fuertemente regulares ,  y luego  Babai y} Luks (1983) lo extendieron a grafos generales. Spielman (1996) realizó  la mejora del exponente √ n para grafos fuertemente regulares. Para los hipergrafos de rango acotado, Babai y Codenotti (2008) obtuvieron un límite superior subexponencial que coincide con el caso de los grafos.

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

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

Casos especiales resueltos

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

• Árboles ^{[20] [21]}
• Grafos planares ^[22] (De hecho, el isomorfismo de grafos planares está en el espacio logarítmico , ^[23] una clase contenida en P )
• Gráficas de intervalos ^[24]
• Gráficos de permutación ^[25]
• Gráficas circulantes ^[26]
• Gráficos de parámetros acotados
  • Gráficas de árboles con anchos acotados ^[27]
  • Gráficas de género acotado ^[28] (Las gráficas planas son gráficas de género 0.)
  • Gráficas de grado acotado ^[29]
  • Gráficos con multiplicidad de valores propios acotados ^[30]
  • Grafos k -contráctiles (una generalización de grado acotado y género acotado) ^[31]
  • El isomorfismo que preserva el color de los gráficos coloreados con multiplicidad de colores 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 ^[32]

Clase de complejidad GI

Dado que no se sabe si el problema del isomorfismo de grafos es NP-completo ni si es manejable, 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 de isomorfismo de grafos. ^[33] Si, de hecho, el problema del isomorfismo de grafos se puede resolver 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 se podrían resolver 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-hard si hay una reducción de Turing en tiempo polinomial de cualquier problema en GI a ese problema, es decir, una solución en tiempo polinomial a un problema GI-hard produciría una solución en tiempo polinomial al problema de isomorfismo de grafos (y por lo tanto todos los problemas en GI ). Un problema se denomina completo para GI , o GI-completo , si es tanto GI-hard como una solución en tiempo polinomial al problema GI produciría una solución en tiempo polinomial a . ${\displaystyle X}$ ${\displaystyle X}$

El problema del isomorfismo de grafos está contenido tanto en NP como en co- AM . GI está contenido en y bajo para Paridad P , así como contenido en la clase potencialmente mucho más pequeña SPP . ^[34] Que se encuentre 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 bajo para ZPP ^NP . ^{[35] Esto significa esencialmente que un} algoritmo Las Vegas eficiente 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.

Problemas GI-completos y GI-difíciles

Isomorfismo de otros objetos

Hay varias clases de objetos matemáticos para los cuales el problema del isomorfismo es un problema GI-completo. Algunos de ellos son grafos dotados de propiedades o restricciones adicionales: ^[36]

• dígrafos ^[36]
• grafos etiquetados , con la condición de que no se requiere un isomorfismo para preservar las etiquetas, ^[36] sino solo la relación de equivalencia que consiste en pares de vértices con la misma etiqueta
• "grafos polarizados" (formados por un grafo completo K _m y un grafo vacío K _n más algunas aristas que conectan los dos; su isomorfismo debe preservar la partición) ^[36]
• 2- gráficos de colores ^[36]
• estructuras finitas dadas explícitamente ^[36]
• multigrafos ^[36]
• hipergrafías ^[36]
• autómatas finitos ^[36]
• Procesos de decisión de Markov ^[37]
• Semigrupos conmutativos de clase 3 nilpotentes (es decir, xyz = 0 para cada elemento x , y , z ) ^[36]
• álgebras asociativas de rango finito sobre un campo algebraicamente cerrado fijo con radical cuadrado cero y factor conmutativo sobre el radical. ^{[36] [38]}
• gramáticas libres de contexto ^[36]
• juegos de forma normal ^[39]
• diseños de bloques incompletos equilibrados ^[36]
• Reconocimiento del isomorfismo combinatorio de politopos convexos representados por incidencias vértice-faceta. ^[40]

Clases de gráficos GI-completas

Una clase de grafos se denomina GI-completa si el reconocimiento de isomorfismo para grafos de esta subclase es un problema GI-completo. Las siguientes clases son GI-completas: ^[36]

• grafos conectados ^[36]
• gráficas de diámetro 2 y radio 1 ^[36]
• grafos acíclicos dirigidos ^[36]
• gráficos regulares ^[36]
• grafos bipartitos sin subgrafos fuertemente regulares no triviales ^[36]
• grafos eulerianos bipartitos ^[36]
• grafos regulares bipartitos ^[36]
• gráficos de líneas ^[36]
• gráficos divididos ^[24]
• grafos cordales ^[36]
• grafos autocomplementarios regulares ^[36]
• grafos politópicos de politopos convexos generales, simples y simpliciales en dimensiones arbitrarias. ^[41]

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

Otros problemas de GI-completo

Existen otros problemas GI-completos no triviales además de los problemas de isomorfismo.

• Encontrar el grupo de automorfismos de un grafo . ^[17]
• Contando automorfismos de un grafo. ^[17]
• El reconocimiento de la autocomplementariedad de un grafo o dígrafo. ^[42]
• Problema de camarilla para una clase de los llamados M -grafos. Se demuestra que encontrar un isomorfismo para grafos de n -vértices es equivalente a encontrar una camarilla n en un M -grafo de tamaño n ² . Este hecho es interesante porque el problema de encontrar una camarilla de orden (1 −  ε ) n en un M -grafo de tamaño n ² es NP-completo para valores arbitrariamente pequeños de ε positivos. ^[43]
• El problema del homeomorfismo de los complejos 2. ^[44]
• El problema de definibilidad para la lógica de primer orden. La entrada de este problema es una instancia de base de datos relacional I y una relación R , y la pregunta a responder es si existe una consulta de primer orden Q (sin constantes) tal que Q evaluada en I dé R como respuesta. ^[45]

Problemas GI-hard

• El problema de contar el número de isomorfismos entre dos gráficos es equivalente en tiempo polinomial al problema de decir si existe siquiera uno. ^[46]
• El problema de decidir si dos politopos convexos dados por la descripción V o la descripción H son proyectivamente o afínmente isomorfos. Esto último significa la existencia de una función proyectiva 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. ^[41]

Comprobación del programa

Manuel Blum y Sampath Kannan (1995) han mostrado un verificador probabilístico para programas de isomorfismo de grafos. Supongamos que P es un supuesto procedimiento de tiempo polinómico que verifica si dos grafos son isomorfos, pero no es confiable. Para verificar si los grafos G y H son isomorfos:

• Pregúntele a P si G y H son isomorfos.
  • Si la respuesta es "sí":
    • Intenta construir un isomorfismo utilizando P como subrutina. Marca un vértice u en G y v en H y modifica los gráficos para que sean distintivos (con un pequeño cambio local). Pregunta a P si los gráficos modificados son isomorfos. Si no, cambia v por un vértice diferente. Continúa buscando.
    • O bien se encontrará el isomorfismo (y podrá verificarse), o P se contradecirá.
  • Si la respuesta es "no":
    • Realice lo siguiente 100 veces. Elija aleatoriamente G o H y permute aleatoriamente sus vértices. Pregúntele a P si el gráfico es isomorfo a G y H (como en el protocolo AM para el no isomorfismo de gráficos).
    • Si alguna de las pruebas falla, considere que P es un programa no vá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 no válido de P. Si P no es un programa correcto y responde incorrectamente en G y H , el verificador detectará un comportamiento no válido de P con alta probabilidad o responderá incorrectamente con una probabilidad de 2 ⁻¹⁰⁰ .

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

Aplicaciones

Los gráficos se utilizan comúnmente para codificar información estructural en muchos campos, incluidos la visión artificial y el reconocimiento de patrones , y la comparación de gráficos , es decir, la identificación de similitudes entre gráficos, es una herramienta importante en estas áreas. En estas áreas, el problema del isomorfismo de gráficos se conoce como comparación exacta de gráficos. ^[47]

En quimioinformática y en 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 . ^[48] 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 por computadora .

La búsqueda en bases de datos químicas es un ejemplo de minería de datos gráfica , donde a menudo se utiliza el enfoque de canonización de gráficos . ^[49] En particular, varios identificadores de sustancias químicas , como SMILES e InChI , diseñados para proporcionar una forma estándar y legible por 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 gráfico que representa la molécula.

En la automatización del diseño electrónico, el isomorfismo gráfico es la base del paso de diseño de circuitos Layout Versus Schematic (LVS), que es una verificación de si los circuitos eléctricos representados por un esquema de circuito y un diseño de circuito integrado son los mismos. ^[50]

Véase también

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

Notas

1. Kobler, Johannes; Schöning, Uwe; Torán, Jacobo (2012). El problema del isomorfismo de grafos: su complejidad estructural . Springer Science & Business Media. p. 1.
2. Schöning (1987).
3. Babai, László; Erdős, Paul; Selkow, Stanley M. (1 de agosto de 1980). "Isomorfismo de gráficos aleatorios". Revista SIAM de Computación . 9 (3): 628–635. doi :10.1137/0209047. ISSN  0097-5397.
4. McKay (1981).
5. Ullman (1976).
6. Moore, Russell y Schulman (2008).
7. Endika Bengoetxea, "Inexact Graph Matching Using Estimation of Distribution Algorithms", Ph. D., 2002, Capítulo 2: El problema de la correspondencia de grafos (consultado el 28 de junio de 2017)
8. "Matemático afirma haber logrado un gran avance en la teoría de la complejidad". Science . 10 de noviembre de 2015.
9. Babai (2015)
10. Vídeo de la primera conferencia de 2015 con enlace desde la página de inicio de Babai
11. "El problema del isomorfismo de grafos". Comunicaciones de la ACM . Consultado el 4 de mayo de 2021 .
12. Babai, László (9 de enero de 2017), Actualización de isomorfismo gráfico
13. Erica Klarreich (14 de enero de 2017). "El isomorfismo gráfico ha sido derrotado, una vez más". Quanta Magazine .
14. Helfgott, Harald (16 de enero de 2017), Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...) , arXiv : 1701.04372 , Bibcode :2017arXiv170104372A
15. Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (12 de octubre de 2017). "Isomorfismos de grafos en tiempo cuasi-polinomial". arXiv : 1710.04574 [math.GR].
16. Foggia, Sansone y Vento (2001).
17. abcMathon (1979).
18. Luks, Eugene (1 de septiembre de 1993). "Grupos de permutación y cálculo en tiempo polinomial". Serie DIMACS en Matemática discreta y ciencia de la computación teórica . Vol. 11. Providence, Rhode Island: Sociedad matemática estadounidense. págs. 139-175. doi :10.1090/dimacs/011/11. ISBN. 978-0-8218-6599-6. ISSN  1052-1798.
19. Algeboy (https://cs.stackexchange.com/users/90177/algeboy), Isomorfismo de grafos y grupo de automorfismos, URL (versión: 2018-09-20): https://cs.stackexchange.com/q/97575
20. Kelly (1957).
21. Aho, Hopcroft y Ullman (1974), págs. 84-86.
22. Hopcroft y Wong (1974).
23. Datta y otros (2009).
24. Booth y Lueker (1979).
25. Colbourn (1981).
26. Muzychuk (2004).
27. Bodlaender (1990).
28. Miller 1980; Filotti y Mayer 1980.
29. Luks (1982).
30. Babai, Grigoryev y Mount (1982).
31. Miller (1983).
32. Luks (1986).
33. Booth y Colbourn 1977; Köbler, Schöning y Torán 1993.
34. Köbler, Schöning y Torán 1992; Arvind y Kurur 2006
35. Arvind y Köbler (2000).
36. Zemliachenko, Korneenko y Tyshkevich (1985)
37. Narayanamurthy y Ravindran (2008).
38. Grigoriev (1981).
39. Gabarró, Joaquim; García, Alina; Serna, María (2011). "La complejidad del isomorfismo del juego". Informática Teórica . 412 (48): 6675–6695. doi :10.1016/j.tcs.2011.07.022. hdl : 2117/91166 .
40. Johnson (2005); Kaibel y Schwartz (2003).
41. Kaibel y Schwartz (2003).
42. Colbourn y Colbourn (1978).
43. Kozen (1978).
44. Shawe-Taylor y Pisanski (1994).
45. Arenas & Díaz (2016).
46. Mathon (1979); Johnson 2005.
47. Endika Bengoetxea, Ph.D., Resumen
48. Irniger (2005).
49. Cocinero y Holder (2007).
50. Baird y Cho (1975).

Referencias

• Aho, Alfred V. ; Hopcroft, John ; Ullman, Jeffrey D. (1974), El diseño y análisis de algoritmos informáticos , Reading, MA: Addison-Wesley.
• Arvind, Vikraman; Köbler, Johannes (2000), "El isomorfismo de grafos es bajo para ZPP(NP) y otros resultados de baja calidad.", Actas del 17.° Simposio Anual sobre Aspectos Teóricos de la Ciencia de la Computación, Lecture Notes in Computer Science , vol. 1770, Springer-Verlag, págs. 431–442, doi :10.1007/3-540-46541-3_36, ISBN 3-540-67141-2, Sr.  1781752.
• Arvind, Vikraman; Kurur, Piyush P. (2006), "El isomorfismo de grafos está en SPP", Información y Computación , 204 (5): 835–852, doi : 10.1016/j.ic.2006.02.002 , MR  2226371.
• Arenas, Marcelo; Diaz, Gonzalo I. (2016), "La complejidad exacta del problema de definibilidad de la lógica de primer orden", ACM Transactions on Database Systems , 41 (2): 13:1-13:14, doi :10.1145/2886095.
• Babai, László (1980), "Sobre la complejidad del etiquetado canónico de grafos fuertemente regulares", SIAM Journal on Computing , 9 (1): 212–216, doi :10.1137/0209018, MR  0557839.
• Babai, László ; Codenotti, Paolo (2008), "Isomorfismo de hipergrafos de bajo rango en tiempo moderadamente exponencial" (PDF) , Actas del 49.º Simposio anual IEEE sobre fundamentos de la informática (FOCS 2008) , IEEE Computer Society, págs. 667–676, doi :10.1109/FOCS.2008.80, ISBN 978-0-7695-3436-7, Número de identificación del sujeto  14025744.
• Babai, László ; Grigoryev, D. Yu.; Mount , David M. (1982), "Isomorfismo de grafos con multiplicidad de valores propios acotados", Actas del 14.º Simposio anual de la ACM sobre teoría de la computación , págs. 310-324, doi :10.1145/800070.802206, ISBN 0-89791-070-2, Número de identificación del sujeto  12837287.
• Babai, László ; Kantor, William ; Luks, Eugene (1983), "Complejidad computacional y la clasificación de grupos finitos simples", Actas del 24.° Simposio anual sobre fundamentos de la informática (FOCS) , págs. 162-171, doi :10.1109/SFCS.1983.10, S2CID  6670135.
• Babai, László ; Luks, Eugene M. (1983), "Etiquetado canónico de grafos", Actas del Decimoquinto Simposio Anual de la ACM sobre Teoría de la Computación (STOC '83) , págs. 171–183, doi : 10.1145/800061.808746 , ISBN 0-89791-099-0, Número de identificación del sujeto  12572142.
• Babai, László (2015), Isomorfismo de grafos en tiempo cuasipolinomial , arXiv : 1512.03547 , Bibcode :2015arXiv151203547B
• Baird, HS; Cho, YE (1975), "Un sistema de verificación de diseño de ilustraciones", Actas de la 12.ª Conferencia de Automatización del Diseño (DAC '75) , Piscataway, NJ, EE. UU.: IEEE Press, págs. 414-420.
• Blum, Manuel ; Kannan, Sampath (1995), "Diseño de programas que comprueban su trabajo", Journal of the ACM , 42 (1): 269–291, CiteSeerX  10.1.1.38.2537 , doi :10.1145/200836.200880, S2CID  52151779.
• Bodlaender, Hans (1990), "Algoritmos polinomiales para isomorfismo de grafos e índice cromático en árboles k parciales ", Journal of Algorithms , 11 (4): 631–643, doi :10.1016/0196-6774(90)90013-5, MR  1079454.
• Booth, Kellogg S.; Colbourn, CJ (1977), Problemas polinomialmente equivalentes al isomorfismo de grafos , Informe técnico, vol. CS-77-04, Departamento de Ciencias de la Computación, Universidad de Waterloo.
• Booth, Kellogg S.; Lueker, George S. (1979), "Un algoritmo de tiempo lineal para decidir el isomorfismo de gráficos de intervalos", Journal of the ACM , 26 (2): 183–195, doi : 10.1145/322123.322125 , MR  0528025, S2CID  18859101.
• Boucher, C.; Loker, D. (2006), Completitud del isomorfismo de grafos para grafos perfectos y subclases de grafos perfectos (PDF) , Informe técnico, vol. CS-2006-32, Departamento de Ciencias de la Computación, Universidad de Waterloo.
• Chung, Fan RK (1985), "Sobre el ancho de corte y el ancho de banda topológico de un árbol", SIAM Journal on Algebraic and Discrete Methods , 6 (2): 268–277, doi :10.1137/0606026, MR  0778007.
• Colbourn, CJ (1981), "Sobre la prueba del isomorfismo de los gráficos de permutación", Networks , 11 : 13–21, doi :10.1002/net.3230110103, MR  0608916.
• Colbourn, Marlene Jones; Colbourn, Charles J. (1978), "Isomorfismo de grafos y grafos autocomplementarios", ACM SIGACT News , 10 (1): 25–29, doi :10.1145/1008605.1008608, S2CID  35157300.
• Cook, Diane J.; Holder, Lawrence B. (2007), "Sección 6.2.1: Etiquetado canónico", Mining Graph Data , Wiley, págs. 120-122, ISBN 978-0-470-07303-2.
• Datta, S.; Limaye, N.; Nimbhorkar, P.; Thierauf, T.; Wagner, F. (2009), "El isomorfismo de grafos planos está en el espacio logarítmico", 24.ª Conferencia Anual IEEE sobre Complejidad Computacional de 2009 , pág. 203, arXiv : 0809.2319 , doi : 10.1109/CCC.2009.16, ISBN 978-0-7695-3717-7, Número de identificación del sujeto  14836820.
• Filotti, IS; Mayer, Jack N. (1980), "Un algoritmo de tiempo polinomial para determinar el isomorfismo de gráficos de género fijo", Actas del 12.º Simposio Anual de la ACM sobre Teoría de la Computación, págs. 236-243, doi :10.1145/800141.804671, ISBN 0-89791-017-6, Número de identificación del sujeto  16345164.
• Foggia, P.; Sansone, C.; Vento, M. (2001), "A performance comparison of five algorithms for graph isomorphism" (PDF) , Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition , págs. 188–199, archivado desde el original (PDF) el 2015-09-24 , consultado el 2009-12-18.
• Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, ISBN 978-0-7167-1045-5.
• Grigor'ev, D. Ju. (1981), "Complejidad de problemas matriciales 'salvajes' y del isomorfismo de álgebras y gráficos", Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Imeni VA Steklova Akademii Nauk SSSR (LOMI) (en ruso), 105 : 10-17, 198 , señor  0628981Traducción al inglés en Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
• Hopcroft, John y Wong, J. (1974), "Algoritmo de tiempo lineal para isomorfismo de grafos planares", Actas del Sexto Simposio Anual de la ACM sobre Teoría de la Computación , págs. 172-184, doi :10.1145/800119.803896, S2CID  15561884.
• Irniger, Christophe-André Mario (2005), Coincidencia de gráficos: filtrado de bases de datos de gráficos mediante aprendizaje automático , Dissertationen zur künstlichen Intelligenz, vol. 293, también conocido como ISBN 1-58603-557-6.
• Kaibel, Volker; Schwartz, Alexander (2003), "Sobre la complejidad de los problemas de isomorfismo de politopos", Graphs and Combinatorics , 19 (2): 215–230, arXiv : math/0106093 , doi :10.1007/s00373-002-0503-y, MR  1996205, S2CID  179936, archivado desde el original el 21 de julio de 2015.
• Kelly, Paul J. (1957), "Un teorema de congruencia para árboles", Pacific Journal of Mathematics , 7 : 961–968, doi : 10.2140/pjm.1957.7.961 , MR  0087949.
• Köbler, Johannes; Schöning, Uwe ; Torán, Jacobo (1992), "El isomorfismo de grafos es bajo para PP", Computational Complexity , 2 (4): 301–330, doi :10.1007/BF01200427, MR  1215315, S2CID  8542603.
• Kozen, Dexter (1978), "Un problema de camarilla equivalente al isomorfismo de grafos", ACM SIGACT News , 10 (2): 50–52, doi : 10.1145/990524.990529 , S2CID  52835766.
• Luks, Eugene M. (1982), "El isomorfismo de gráficos de valencia acotada se puede probar en tiempo polinomial", Journal of Computer and System Sciences , 25 : 42–65, doi : 10.1016/0022-0000(82)90009-5 , MR  0685360, S2CID  2572728.
• Luks, Eugene M. (1986), "Algoritmos paralelos para grupos de permutación e isomorfismo de grafos", Proc. IEEE Symp. Foundations of Computer Science , págs. 292–302.
• Mathon, Rudolf (1979), "Una nota sobre el problema de conteo de isomorfismos de grafos", Information Processing Letters , 8 (3): 131–132, doi :10.1016/0020-0190(79)90004-8, MR  0526453.
• McKay, Brendan D. (1981), "Isomorfismo gráfico práctico", 10.ª Conferencia de Manitoba sobre Matemáticas numéricas y computación (Winnipeg, 1980) , Congressus Numerantium, vol. 30, págs. 45–87, MR  0635936.
• Miller, Gary (1980), "Prueba de isomorfismo para gráficos de género acotado", Actas del 12º Simposio Anual de la ACM sobre Teoría de la Computación , págs. 225-235, doi : 10.1145/800141.804670 , ISBN 0-89791-017-6, Número de identificación del sujeto  13647304.
• Miller, Gary L. (1983), "Prueba de isomorfismo y formas canónicas para grafos k -contráctiles (una generalización de valencia acotada y género acotado)", Proc. Int. Conf. on Foundations of Computer Theory , Lecture Notes in Computer Science , vol. 158, págs. 310–327, doi :10.1007/3-540-12689-9_114Artículo completo en Información y Control 56 (1–2): 1–20, 1983.
• Moore, Cristopher ; Russell, Alexander; Schulman, Leonard J. (2008), "El grupo simétrico desafía el muestreo fuerte de Fourier", SIAM Journal on Computing , 37 (6): 1842–1864, arXiv : quant-ph/0501056 , doi :10.1137/050644896, MR  2386215, S2CID  9550284.
• Muzychuk, Mikhail (2004), "Una solución del problema del isomorfismo para grafos circulantes", Proc. London Math. Soc. , 88 : 1–41, doi :10.1112/s0024611503014412, MR  2018956, S2CID  16704931.
• Narayanamurthy, SM; Ravindran, B. (2008), "Sobre la dificultad de encontrar simetrías en los procesos de decisión de Markov" (PDF) , Actas de la Vigésima Quinta Conferencia Internacional sobre Aprendizaje Automático (ICML 2008) , págs. 688–696.
• Schmidt, Douglas C.; Druffel, Larry E. (1976), "Un algoritmo de retroceso rápido para probar el isomorfismo en gráficos dirigidos utilizando matrices de distancia", Journal of the ACM , 23 (3): 433–445, doi : 10.1145/321958.321963 , MR  0411230, S2CID  6163956.
• Schöning, Uwe (1987), "El isomorfismo de grafos está en la jerarquía baja", Actas del 4º Simposio Anual sobre Aspectos Teóricos de la Ciencia de la Computación , págs. 114-124; también Revista de Ciencias de la Computación y Sistemas 37 : 312–323, 1988.
• Shawe-Taylor, John; Pisanski, Tomaž (1994), "El homeomorfismo de los complejos 2 es un isomorfismo de grafos completo", SIAM Journal on Computing , 23 (1): 120–132, doi :10.1137/S0097539791198900, MR  1258998.
• Spielman, Daniel A. (1996), "Pruebas de isomorfismo más rápidas de grafos fuertemente regulares", Actas del vigésimo octavo simposio anual de la ACM sobre teoría de la computación (STOC '96) , ACM, págs. 576-584, ISBN 978-0-89791-785-8.
• Ullman, Julian R. (1976), "Un algoritmo para el isomorfismo de subgrafos" (PDF) , Journal of the ACM , 23 : 31–42, CiteSeerX  10.1.1.361.7741 , doi :10.1145/321921.321925, MR  0495173, S2CID  17268751.

Encuestas y monografías

• Read, Ronald C.; Corneil, Derek G. (1977), "La enfermedad del isomorfismo de grafos", Journal of Graph Theory , 1 (4): 339–363, doi :10.1002/jgt.3190010410, MR  0485586, S2CID  26589776.
• Gati, G. (1979), "Bibliografía adicional comentada sobre la enfermedad del isomorfismo", Journal of Graph Theory , 3 (2): 95–109, doi :10.1002/jgt.3190030202.
• Zemlyachenko, VN; Korneenko, NM; Tyshkevich, RI (1985), "Problema de isomorfismo de grafos", Journal of Mathematical Sciences , 29 (4): 1426–1481, doi : 10.1007/BF02104746 , S2CID  121818465. (Traducido de Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. VA Steklova AN SSSR (Registros de seminarios del Departamento de Leningrado del Instituto Steklov de Matemáticas de la Academia de Ciencias de la URSS ), Vol. 118, págs. 83-158, 1982.)
• Arvind, V.; Torán, Jacobo (2005), "Pruebas de isomorfismo: perspectivas y problemas abiertos" (PDF) , Boletín de la Asociación Europea de Ciencias de la Computación Teórica , 86 : 66–84. (Un breve estudio de cuestiones abiertas relacionadas con el problema del isomorfismo para gráficos, anillos y grupos).
• Kobler, Johannes; Schöning, Uwe ; Torán, Jacobo (1993), El problema del isomorfismo de grafos: su complejidad estructural , Birkhäuser, ISBN 978-0-8176-3680-7. ( De la portada del libro : El libro se centra en la cuestión de la complejidad computacional del problema y presenta varios resultados recientes que proporcionan una mejor comprensión de la posición relativa del problema en la clase NP así como en otras clases de complejidad).
• Johnson, David S. (2005), "La columna de completitud NP", ACM Transactions on Algorithms , 1 (1): 160–176, doi :10.1145/1077464.1077476, S2CID  12604799. (Esta 24.ª edición de la Columna analiza el estado del arte de los problemas abiertos del libro Computers and Intractability y columnas anteriores, en particular, para el Isomorfismo de grafos).
• Torán, Jacobo; Wagner, Fabian (2009), "La complejidad del isomorfismo de grafos planos" (PDF) , Boletín de la Asociación Europea de Ciencias Informáticas Teóricas , 97 , archivado desde el original (PDF) el 20 de septiembre de 2010 , consultado el 3 de junio de 2010.
• Stoichev, Stoicho D. (2019), "Nuevos algoritmos exactos y heurísticos para el grupo de automorfismo de grafos y el isomorfismo de grafos", Journal of Experimental Algorithmics , 24 : 1–27, doi :10.1145/3333250, S2CID  202676274.

Software

• Isomorfismo de gráficos, revisión de implementaciones, El repositorio de algoritmos de Stony Brook.