Problema de isomorfismo gráfico

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

Problema no resuelto en informática :

¿Se puede resolver el problema del isomorfismo gráfico 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 isomórficos .

No se sabe que el problema tenga solución 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 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 colapse a su segundo nivel. ^[1] Al mismo tiempo, el isomorfismo de muchas clases especiales de gráficos se puede resolver en tiempo polinomial y, en la práctica, el isomorfismo de gráficos a menudo se puede resolver de manera eficiente. ^{[2] [3]}

Este problema es un caso especial del problema de isomorfismo de subgrafos , ^[4] que pregunta si un gráfico dado G contiene un subgrafo que es isomorfo a otro gráfico dado H ; Se sabe que este problema es NP-completo. También se sabe que es un caso especial del problema de subgrupos ocultos no abelianos sobre el grupo simétrico . ^[5]

En el ámbito del reconocimiento de imágenes, esto se conoce como coincidencia gráfica exacta. ^[6]

Lo último

En noviembre de 2015, László Babai anunció un algoritmo de tiempo cuasi polinómico para todos los gráficos, es decir, uno con tiempo de ejecución para algunos fijos . ^{[7] [8] [9] [10]} El 4 de enero de 2017, Babai se retractó de la afirmación cuasi polinómica y en su lugar declaró un límite de tiempo subexponencial 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 polinómica, y Helfgott confirmó la solución. ^{[11] [12]} Helfgott afirma además que se puede tomar c = 3 , por lo que el tiempo de ejecución es 2 ^{O((log n ) 3 )} . ^{[13] [14]} ${\displaystyle 2^{O((\log n)^{c})}}$ ${\displaystyle c>0}$

Antes de esto, el algoritmo teórico mejor aceptado fue el de 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 gráficos 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 gráficos fuertemente regulares ^{, y luego  Babai y  Luks (} 1983  ) lo extendieron a gráficos generales. Spielman (1996) mejoró el exponente √ n para gráficos fuertemente regulares. Para hipergráficos de rango acotado, Babai y Codenotti (2008) obtuvieron un límite superior subexponencial que coincide con el caso de los gráficos.

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

El problema de isomorfismo de grafos es computacionalmente equivalente al problema de calcular el grupo de automorfismo de un gráfico, ^{[16] [17]} y es más débil que el problema de isomorfismo de grupos de permutaciones y el problema de intersección de grupos de permutaciones. 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 ^{[18] [19]}
• Gráficos planos ^[20] (De hecho, el isomorfismo del gráfico plano está en el espacio logarítmico , ^[21] una clase contenida en P )
• Gráficos de intervalos ^[22]
• Gráficos de permutación ^[23]
• Gráficos circulantes ^[24]
• Gráficos de parámetros acotados
  • Gráficos de ancho de árbol acotado ^[25]
  • Gráficas de género acotado ^[26] (Las gráficas planas son gráficas de género 0.)
  • Gráficas de grado acotado ^[27]
  • Gráficos con multiplicidad de valores propios acotada ^[28]
  • k -Gráficos contraíbles (una generalización de grado y género acotados) ^[29]
  • El isomorfismo que preserva el color de los gráficos coloreados con multiplicidad de color limitada (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 ^[30]

Clase de complejidad GI

Dado que no se sabe que el problema del isomorfismo gráfico sea NP-completo ni que sea manejable, los investigadores han tratado de comprender mejor el problema definiendo una nueva clase GI , el conjunto de problemas con una reducción de Turing en tiempo polinomial al isomorfismo gráfico. problema. ^[31] Si, de hecho, el problema de isomorfismo gráfico se puede resolver en tiempo polinómico, 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 un tiempo cuasipolinomial.

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

El problema del isomorfismo gráfico está contenido tanto en NP como en co- AM . GI está contenido en la paridad P y es bajo , así como también en la clase potencialmente mucho más pequeña SPP . ^[32] 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 caminos de aceptación. El IG también está contenido en ZPP ^NP y es bajo . ^[33] Esto esencialmente significa que un algoritmo eficiente de Las Vegas con acceso a un oráculo NP puede resolver el isomorfismo gráfico tan fácilmente que no obtiene ningún 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 de isomorfismo es un problema GI completo. Varios de ellos son gráficos dotados de propiedades o restricciones adicionales: ^[34]

• dígrafos ^[34]
• gráficos etiquetados , con la condición de que no se requiere un isomorfismo para preservar las etiquetas, ^[34] sino solo la relación de equivalencia que consta de 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) ^[34]
• Gráficos de 2 colores ^[34]
• estructuras finitas dadas explícitamente ^[34]
• multigrafos ^[34]
• hipergrafías ^[34]
• autómatas finitos ^[34]
• Procesos de decisión de Markov ^[35]
• Semigrupos nilpotentes de clase conmutativa 3 (es decir, xyz = 0 para cada elemento x , y , z ) ^[34]
• álgebras asociativas de rango finito sobre un campo algebraicamente cerrado fijo con radical cero al cuadrado y factor conmutativo sobre el radical. ^{[34] [36]}
• gramáticas libres de contexto ^[34]
• juegos en forma normal ^[37]
• diseños de bloques incompletos equilibrados ^[34]
• Reconocimiento del isomorfismo combinatorio de politopos convexos representados por incidencias vértice-faceta. ^[38]

Clases de gráficos GI-completas

Una clase de gráficos se llama GI-completo si el reconocimiento del isomorfismo para gráficos de esta subclase es un problema de GI-completo. Las siguientes clases son GI-completa: ^[34]

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

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

Otros problemas gastrointestinales completos

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

• El reconocimiento de la autocomplementariedad de un gráfico o dígrafo. ^[40]
• Un problema de camarilla para una clase de los llamados M -grafos. Se muestra que encontrar un isomorfismo para n -gráficos de vértices es equivalente a encontrar una n -clique en un gráfico M de tamaño n ² . Este hecho es interesante porque el problema de encontrar una camarilla de orden (1 −  ε ) n en un gráfico M de tamaño n ² es NP-completo para ε positivo arbitrariamente pequeño. ^[41]
• El problema del homeomorfismo de 2 complejos. ^[42]
• El problema de la definibilidad de 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. ^[43]

Problemas gastrointestinales difíciles

• El problema de contar el número de isomorfismos entre dos gráficos es equivalente en tiempo polinómico al problema de saber si existe uno. ^[44]
• El problema de decidir si dos politopos convexos dados por la descripción V o la descripción H son proyectiva o afínmente isomórficos. Esto último significa la existencia de un mapa proyectivo 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. ^[39]

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 procedimiento de tiempo polinomial que verifica si dos gráficas son isomorfas, pero no es confiable. Para comprobar si los gráficos G y H son isomorfos:

• Pregunte a P si G y H son isomorfos.
  • Si la respuesta es sí":
    • Intente construir un isomorfismo utilizando P como subrutina. Marque un vértice u en G y v en H y modifique las gráficas para hacerlas distintivas (con un pequeño cambio local). Pregúntele a P si las gráficas modificadas son isomorfas. Si no, cambie v a un vértice diferente. Continuar buscando.
    • O se encontrará el isomorfismo (y podrá verificarse), o P se contraderá.
  • 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 la gráfica es isomorfa a G y H. (Como en el protocolo AM para el no isomorfismo gráfico).
    • Si alguna de las pruebas falla, juzgue P como programa no válido. En caso 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 ⁻¹⁰⁰ .

En particular, P se utiliza sólo como caja negra.

Aplicaciones

Los gráficos se utilizan comúnmente para codificar información estructural en muchos campos, incluida la visión por computadora 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 de isomorfismo gráfico se conoce como coincidencia exacta de gráficos. ^[45]

En quimioinformática y química matemática , las pruebas de isomorfismo gráfico se utilizan para identificar un compuesto químico dentro de una base de datos química . ^[46] Además, en química matemática orgánica, las pruebas de isomorfismo de gráficos son útiles para la generación de gráficos 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áficos , donde a menudo se utiliza el enfoque de canonización de gráficos . ^[47] En particular, varios identificadores de sustancias químicas , como SMILES e InChI , diseñados para proporcionar una forma estándar y legible por humanos para codificar información molecular y facilitar la búsqueda de dicha información en bases de datos y en la web, utilizan 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 circuito Diseño versus esquema (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. ^[48]

Ver también

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

Notas

1. Schöning (1987).
2. 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.
3. McKay (1981).
4. Ullman (1976).
5. Moore, Russell y Schulman (2008).
6. Endika Bengoetxea, "Coincidencia de gráficos inexactos mediante estimación de algoritmos de distribución", Ph. D., 2002, Capítulo 2: El problema de coincidencia de gráficos (consultado el 28 de junio de 2017)
7. "Un matemático afirma un gran avance en la teoría de la complejidad". Ciencia . 10 de noviembre de 2015.
8. Babai (2015)
9. Vídeo de la primera conferencia de 2015 vinculado desde la página de inicio de Babai
10. "El problema del isomorfismo gráfico". Comunicaciones de la ACM . Consultado el 4 de mayo de 2021 .
11. Babai, László (9 de enero de 2017), Actualización de isomorfismo gráfico
12. Erica Klarreich (14 de enero de 2017). "El isomorfismo gráfico vencido - otra vez". Revista Quanta .
13. 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
14. Doña, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (12 de octubre de 2017). "Graficar isomorfismos en tiempo cuasipolinomial". arXiv : 1710.04574 [matemáticas.GR].
15. Foggia, Sansone y Vento (2001).
16. Luks, Eugene (1 de septiembre de 1993). "Grupos de permutación y cálculo de tiempo polinómico". Serie DIMACS en Matemática Discreta e Informática 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.
17. Algeboy (https://cs.stackexchange.com/users/90177/algeboy), Isomorfismo gráfico y grupo de automorfismo, URL (versión: 2018-09-20): https://cs.stackexchange.com/q/ 97575
18. Kelly (1957).
19. Aho, Hopcroft y Ullman (1974), pág. 84-86.
20. Hopcroft y Wong (1974).
21. Datta y otros. (2009).
22. Booth y Lueker (1979).
23. Colbourn (1981).
24. Muzychuk (2004).
25. Bodlaender (1990).
26. Molinero 1980; Filotti y Mayer 1980.
27. Luks (1982).
28. Babai, Grigoryev y Mount (1982).
29. Molinero (1983).
30. Luks (1986).
31. Stand y Colbourn 1977; Köbler, Schöning y Torán 1993.
32. Köbler, Schöning y Torán 1992; Arvind y Kurur 2006
33. Arvind y Kobler (2000).
34. Zemlyachenko, Korneenko y Tyshkevich (1985)
35. Narayanamurthy y Ravindran (2008).
36. Grigor'ev (1981).
37. 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 .
38. Johnson (2005); Kaibel y Schwartz (2003).
39. Kaibel y Schwartz (2003).
40. Colbourn y Colbourn (1978).
41. Kozen (1978).
42. Shawe-Taylor y Pisanski (1994).
43. Arenas y Díaz (2016).
44. Mathón (1979); Johnson 2005.
45. Endika Bengoetxea, Ph.D., Resumen
46. Irniger (2005).
47. Cocinero y titular (2007).
48. Baird y Cho (1975).

Referencias

• Ah, 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 gráfico es bajo para ZPP (NP) y otros resultados de bajeza". Actas del 17º Simposio anual sobre aspectos teóricos de la informática, 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, señor  1781752.
• Arvind, Vikraman; Kurur, Piyush P. (2006), "El isomorfismo gráfico 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 lógica de primer orden", Transacciones ACM en sistemas de bases de datos , 41 (2): 13:1-13:14, doi :10.1145/2886095.
• Babai, László (1980), "Sobre la complejidad del etiquetado canónico de gráficos fuertemente regulares", SIAM Journal on Computing , 9 (1): 212–216, doi :10.1137/0209018, SEÑOR  0557839.
• Babai, László ; Codenotti, Paolo (2008), "Isomorfismo de hipergrafías de bajo rango en tiempo moderadamente exponencial" (PDF) , Actas del 49º Simposio anual del IEEE sobre los fundamentos de la informática (FOCS 2008) , IEEE Computer Society, págs. doi :10.1109/FOCS.2008.80, ISBN 978-0-7695-3436-7, S2CID  14025744.
• Babai, László ; Grigoriev, D. Yu. ; Mount, David M. (1982), "Isomorfismo de gráficos con multiplicidad de valores propios acotada", Actas del 14º Simposio anual ACM sobre teoría de la informática , págs. 310–324, doi :10.1145/800070.802206, ISBN 0-89791-070-2, S2CID  12837287.
• Babai, László ; Kantor, William ; Luks, Eugene (1983), "Complejidad computacional y 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 gráficos", Actas del decimoquinto simposio anual ACM sobre teoría de la informática (STOC '83) , págs. 171-183, doi : 10.1145/800061.808746 , ISBN 0-89791-099-0, S2CID  12572142.
• Babai, László (2015), Isomorfismo gráfico en tiempo cuasipolinomial , arXiv : 1512.03547 , Bibcode :2015arXiv151203547B
• Baird, SA; Cho, YE (1975), "Un sistema de verificación de diseño de obras de arte", Actas de la 12ª Conferencia de Automatización del Diseño (DAC '75) , Piscataway, Nueva Jersey, EE. UU.: IEEE Press, págs..
• Blum, Manuel ; Kannan, Sampath (1995), "Diseño de programas que verifican 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 polinómicos para isomorfismo de gráficos e índice cromático en k parciales ", Journal of Algorithms , 11 (4): 631–643, doi :10.1016/0196-6774(90)90013-5, Señor  1079454.
• Stand, Kellogg S.; Colbourn, CJ (1977), Problemas polinómicamente equivalentes al isomorfismo gráfico , Informe técnico, vol. CS-77-04, Departamento de Ciencias de la Computación, Universidad de Waterloo.
• Stand, Kellogg S.; Lueker, George S. (1979), "Un algoritmo de tiempo lineal para decidir el isomorfismo del gráfico 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 gráficos para gráficos perfectos y subclases de gráficos 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", Revista SIAM sobre métodos algebraicos y discretos , 6 (2): 268–277, doi :10.1137/0606026, MR  0778007.
• Colbourn, CJ (1981), "Sobre la prueba de isomorfismo de 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 gráficos y gráficos autocomplementarios", ACM SIGACT News , 10 (1): 25–29, doi :10.1145/1008605.1008608, S2CID  35157300.
• Cocinero, 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 del gráfico plano está en el espacio logarítmico", 24ª Conferencia Anual del IEEE sobre Complejidad Computacional de 2009 , p. 203, arXiv : 0809.2319 , doi : 10.1109/CCC.2009.16, ISBN 978-0-7695-3717-7, S2CID  14836820.
• Filotti, ES; 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 ACM sobre teoría de la computación, págs. 236–243, doi :10.1145/800141.804671, ISBN 0-89791-017-6, S2CID  16345164.
• Foggia, P.; Sansone, C.; Vento, M. (2001), "Una comparación de rendimiento de cinco algoritmos para el isomorfismo de gráficos" (PDF) , Proc. 3.er taller IAPR-TC15 Representaciones basadas en gráficos en el reconocimiento de patrones , págs. 188-199.
• Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la integridad NP , 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  0628981. Traducción al inglés en Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
• Hopcroft, John ; Wong, J. (1974), "Algoritmo de tiempo lineal para isomorfismo de gráficos planos", Actas del Sexto Simposio Anual 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), "Graph isomorphism is low for PP", Computational Complexity, 2 (4): 301–330, doi:10.1007/BF01200427, MR 1215315, S2CID 8542603.
• Kozen, Dexter (1978), "A clique problem equivalent to graph isomorphism", ACM SIGACT News, 10 (2): 50–52, doi:10.1145/990524.990529, S2CID 52835766.
• Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", 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), "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science, pp. 292–302.
• Mathon, Rudolf (1979), "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (3): 131–132, doi:10.1016/0020-0190(79)90004-8, MR 0526453.
• McKay, Brendan D. (1981), "Practical graph isomorphism", 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), Congressus Numerantium, vol. 30, pp. 45–87, MR 0635936.
• Miller, Gary (1980), "Isomorphism testing for graphs of bounded genus", Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 225–235, doi:10.1145/800141.804670, ISBN 0-89791-017-6, S2CID 13647304.
• Miller, Gary L. (1983), "Isomorphism testing and canonical forms for k-contractable graphs (a generalization of bounded valence and bounded genus)", Proc. Int. Conf. on Foundations of Computer Theory, Lecture Notes in Computer Science, vol. 158, pp. 310–327, doi:10.1007/3-540-12689-9_114. Full paper in Information and Control 56 (1–2): 1–20, 1983.
• Moore, Cristopher ; Russell, Alejandro; Schulman, Leonard J. (2008), "El grupo simétrico desafía el fuerte muestreo 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 al problema del isomorfismo para gráficos circulantes", Proc. Matemáticas de Londres. Soc. , 88 : 1–41, doi : 10.1112/s0024611503014412, SEÑOR  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 XXIV Conferencia Internacional sobre Aprendizaje Automático (ICML 2008) , págs..
• Schmidt, Douglas C.; Druffel, Larry E. (1976), "Un algoritmo de retroceso rápido para probar el isomorfismo de 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 gráficos está en la jerarquía baja", Actas del cuarto simposio anual sobre aspectos teóricos de la informática , págs.; también Journal of Computer and System Sciences 37 : 312–323, 1988.
• Shawe-Taylor, John; Pisanski, Tomaž (1994), "El homeomorfismo de 2 complejos es un isomorfismo gráfico 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 gráficos fuertemente regulares", Actas del vigésimo octavo simposio anual de ACM sobre teoría de la informática (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

• Leer, 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, Nuevo México; Tyshkevich, RI (1985), "Problema de isomorfismo gráfico", 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 Informática Teórica , 86 : 66–84. (Un breve resumen de preguntas abiertas relacionadas con el problema de isomorfismo para gráficas, 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 integridad NP", Transacciones ACM sobre algoritmos , 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, del isomorfismo de gráficos).
• Torán, Jacobo; Wagner, Fabian (2009), "La complejidad del isomorfismo del gráfico plano" (PDF) , Boletín de la Asociación Europea de Ciencias de la Computación Teórica , 97 , archivado desde el original (PDF) el 20 de septiembre de 2010 , consultado el 6 de junio de 2010. 03.
• Stoichev, Stoicho D. (2019), "Nuevos algoritmos exactos y heurísticos para el grupo de automorfismo de gráficos y el isomorfismo de gráficos", Journal of Experimental Algorithmics , 24 : 1–27, doi :10.1145/3333250, S2CID  202676274.

Software

• Isomorfismo de gráficos, revisión de implementaciones, The Stony Brook Algorithm Repository.