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.
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.
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.
La mejora del exponente √n es un gran problema abierto; para gráficos fuertemente regulares esto fue hecho por Spielman (1996).
Para los últimos dos problemas, Babai, Kantor y Luks (1983) obtuvieron límites de complejidad similares a los del isomorfismo gráfico.
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
El problema del isomorfismo gráfico está contenido tanto en NP como en co-AM.
Manuel Blum y Sampath Kannan (1995) han mostrado un verificador probabilístico para programas de isomorfismo gráfico.
Para verificar si G y H son isomorfos: 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.