Problema de isomorfismo de grafos

O problema de isomorfismo de grafos é um problema computacional para determinar se dois grafos finitos são isomórficos.

Não é conhecido se o problema pode ser solucionável em tempo polinomial nem se é NP-completo e, portanto, pode estar na classe de complexidade computacional NP-Intermediário. Sabe-se que o problema do isomorfismo do grafo está na baixa hierarquia da classe NP, o que implica que não é NP-completo a menos que a hierarquia de tempo polinomial colapse para o segundo nível.^[1] Ao mesmo tempo, o isomorfismo para muitas classes especiais de grafos pode ser resolvido em tempo polinomial, e na prática o isomorfismo do grafo pode ser resolvido de forma eficiente.^[2]

Além de sua importância prática, o problema do isomorfismo de grafos é uma curiosidade em teoria da complexidade computacional, uma vez que faz parte de um número muito pequeno de problemas pertencentes a classe NP, conhecidos por não poderem serem resolvidos em tempo polinomial e nem em NP-completo: é um de apenas 12 dos problemas listados por Garey e Johnson (1979) e o único dessa lista cuja complexidade continua não resolvida.

Este problema é um caso especial do problema do isomorfismo de subgrafos ^[3], que é conhecido por ser NP-completo. É também conhecido como um caso especial do problema do subgrupo oculto não abeliano sobre o grupo simétrico.^[4]

Estado da arte

O melhor algoritmo teórico atual é atribuído à Babai & Luks (1983), O melhor algoritmo teórico atual é atribuído à Luks (1982) combinado com um algoritmo subfatorial atribuído à Zemlyachenko, Korneenko & Tyshkevich (1985). O algoritmo baseia-se na classificação dos grupos finitos simples. Sem CFSG, um vínculo um pouco mais fraco 2^{O(√n log² n)} foi obtido pela primeira vez para grafos fortemente regulares por László Babai (1980), e depois estendidos para grafos gerais por Babai & Luks (1983). A melhoria do expoente √n é um grande problema em aberto; para grafos fortemente regulares isto foi feito por Spielman (1996). Para hipergrafos de classificação limitada, um limite superior subexponencial correspondendo aos caso dos grafos, foi obtido por Babai & Codenotti (2008).

Em 10 de Novembro, 2015, Babai deu uma palestra durante o qual ele alegou ter encontrado um algoritmo melhor, com o tempo de execução de só um pouco maior do que o polinomial. ^[5]

Em uma nota a parte, o problema do isomorfismo de grafos é computacionalmente equivalente ao problema de computar o grupo automórfico de um grafo e é mais fraco do que o problema do grupo de permutação isomórfico e o problema de interseção de permutações de grupos. Para os dois últimos problemas, Babai, Kantor & Luks (1983) obtiveram complexidade limita semelhante ao usado para isomorfismo gráfico.

Existem vários algoritmos práticos concorrentes para isomorfismo de grafos, atribuído à McKay (1981), Schmidt & Druffel (1976), Ullman (1976), etc. Embora eles parecem ter um bom desempenho em grafos aleatórios, uma grande desvantagem desses algoritmos é o desempenho em tempo exponencial no pior caso.^[6]

Casos especiais resolvidos

Uma série de casos importantes do problema do isomorfismo de grafos especiais têm soluções eficientes e em tempo polinomial:

Árvores^[7]^[8]
Grafos planares ^[9] (Na verdade, isomorfismo de grafos planares está no espaço logarítimo,^[10] uma classe contida em P)
Grafos de intervalo ^[11]
Grafos de permutação ^[12]
Grafos limitado pelo parâmetro
- Grafos de largura de árvore limitada.^[13]
- Grafos de gênero limitados^[14] (Nota: grafos planares são gráficos de gênero 0)
- Grafos de grau limitado ^[15]
- Grafos com multiplicidade limitada de Autovalor (eigenvalue) ^[16]
- Grafos k-contrátil (uma generalização do grau limitado e gênero limitada) ^[17]
- Isomorfismo Cor-preservanda dos grafos coloridos com a multiplicidade de cores limitada (ou seja, na maioria dos vértices k têm a mesma cor para um k fixo) está na classe NC, que é uma subclasse de P ^[18]

Classe de complexidade GI

Desde que o problema do isomorfismo de grafos que não é conhecido por ser NP-completos nem para ser tratável, os pesquisadores procuraram obter clareza sobre o problema através da definição de um nova classe GI, o conjunto de problemas com uma redução de tempo polinomial Turing para o problema do isomorfismo de grafos.^[19] Se de fato o problema do isomorfismo de grafos pode ser resolvido em tempo polinomial, GI seria igual P.

Como é comum para as classes de complexidade dentro da hierarquia de tempo polinomial, um problema é chamado GI-difícil se existir uma redução de tempo polinomial Turing para qualquer problema no GI para este problema, isto é, uma solução em tempo polinomial para um problema GI-difícil renderia uma solução em tempo polinomial para o problema do isomorfismo de grafos (e assim todos os problemas em GI). Um problema X é chamado completo para GI, ou GI-completo, se é tanto GI-difícil e uma solução de tempo polinomial para o problema GI iria produzir uma solução de tempo polinomial a $X$ .

O problema do isomorfismo de grafos está contido em ambos NP e co-AM. GI está contido e baixo para a paridade P, bem como contido na classe SPP, que é a potencialmente muito menor. ^[20] Encontrar-se em paridade P significa que o problema do isomorfismo de grafos não é mais difícil do que determinar se uma Máquina de Turing não determinística de tempo polinomial tem um número par ou ímpar de caminhos de aceitação. GI também está contido e baixo para ZPP^NP.^[21] Isto significa basicamente que um algoritmo Las Vegas eficiente com acesso a um oráculo NP pode resolver o isomorfismo de grafos tão facilmente que ele ganha nenhum poder de ser dada a capacidade de fazê-lo em tempo constante.

GI-completo e problemas GI-difíceis

Isomorfismo de outros objetos

Existe um número de classes de objetos matemáticos para os quais o problema de isomorfismo é um problema GI-completo. Um número deles são gráficos dotados de propriedades adicionais ou restrições: ^[22]

Dígrafos^[22]
Gráficos rotulados, com a condição de que um isomorfismo não é necessário para preservar os rótulos,^[22] mas apenas a relação de equivalência que consiste em pares de vértices com o mesmo rótulo
"Gráficos polarizados" (feitos de um grafo completo Km e um gráfico vazio Kn mais algumas arestas que ligam os dois; seus isomorfismos deve preservar a partição)^[22]
Grafos 2-coloridos^[22]
Estruturas finitas dadas explicitamente^[22]
Multigrafos^[22]
Hipergrafos^[22]
Autômatos Finitos^[22]
Processos de Decisão Markovianos ^[23]
Classe comutativa com 3 semigrupos nilpotentes (ou seja, xyz = 0 para cada elementos x, y, z) ^[22]
Álgebras associativas de ranks finitos sobre um campo fechado algebricamente fixo com zero radicais quadraticos e fator comutativo sobre o radical. ^[22]^[24]
Gramáticas livre do contexto ^[22]
Projeto de blocos balanceados incompletos ^[22]
Reconhecendo isomorfismo combinatorial de politopos convexos representados por incidência vértice-face. ^[25]

Classes de grafos GI-completos

Uma classe de gráficos é chamado GI-completo se o reconhecimento de isomorfismo para grafos a partir desta subclasse é um problema GI-completo. As seguintes classes estão GI-completa: ^[22]

Grafos conectados^[22]
Grafos de diâmetro 2 e raio 1^[22]
Grafos acíclicos dirigidos^[22]
Grafos regulares^[22]
Grafos bipartidos sem subgrafos fortemente regulares não-triviais ^[22]
Grafos Euleriano bipartidos^[22]
Grafos regulares bipartidos^[22]
Grafos Lineares^[22]
Grafos divididos^[26]
Grafos cordais^[22]
Grafos auto-complementares regulares^[22]
Grafos de politopos convexos gerais, simples e politopos convexos simplicial dimensões arbitrárias.^[27]

Muitas classes de dígrafos são também GI-completa.

Outros problemas GI-completos

Existem outros problemas GI-completo não triviais, além de problemas de isomorfismo.

O reconhecimento de auto-complementaridade de um gráfico ou digrafo.^[28]
Um Problema do clique para uma classe dos chamados M-grafos. Mostra-se que encontrar um isomorfismo para gráficos n-vértices vértice é equivalente a encontrar um n-clique num M-grafo de tamanho n². Este fato é interessante porque o problema de encontrar um (n − ε)-clique em um M-grafo de tamanho n² é NP-completo para arbitrariamente pequena ε positivo ε.^[29]
O problema de equivalência topológica de 2-complexos.^[30]

Problemas GI-difícil

O problema de contar o número de isomorfismos entre dois gráficos é em tempo polinomial equivalente para o problema de dizer se existe ainda um.^[31]
O problema de decidir se dois politopos convexos dadas tanto pela descrição V ou descrição H são projetivamente ou afim isomórficos. Esta última significa a existência de um mapa projetivo ou afim entre os espaços que contenham os dois politopos (não necessariamente da mesma dimensão) que induz uma bijeção entre os politopes.^[27]

Verificação do programa

Manuel Blum e Sampath Kannan (1995) mostraram um programa de verificação para o isomorfismo de grafos. Suponha que P é dito como um procedimento de tempo polinomial que verifica se dois gráficos são isomorfos, mas não confiáveis. Para verificar se G e H são isomorfos:

Pergunte a P se G e H são isomorfos.
- Se a resposta for "sim":
  - Tentar construir um isomorfismo usando P como sub-rotina. Marcando um vértice u em G e v em H e modificar os gráficos para torná-los distintos (com uma pequena mudança local). Perguntar a P se os grafos modificados são isomorfos. Se não, mudar v para um vértice diferente. Continue procurando.
  - Ou o isomorfismo será encontrado (e pode ser verificado) ou P irá contradizer a si mesmo..
- Se a resposta for "não":
  - Execute o seguinte 100 vezes. Escolha aleatoriamente G ou H, e permutar aleatoriamente seus vértices. Perguntar a P se o grafo é isomorfo a G e H. (como no protocolo AM para o não isomorfismo do grafo).
  - Se algum dos testes falharem, julga P como um programa inválido. Caso contrário, responda "não".

Este procedimento é de tempo polinomial e dá resposta correta se P é um programa correto para isomorfismo do grafo. Se P não é um programa correto, mas as respostas corretamente em G e H, o verificador vai ou dar a resposta correta, ou detectar comportamento inválido de P. Se P não é um programa correto e respostas incorretamente sobre G e H, o verificador irá detectar comportamento inválido de P com alta probabilidade, ou responder errado com probabilidade 2⁻¹⁰⁰.

Notavelmente, P é usado apenas como uma caixa preta.

Aplicações

Em quimioinformática e em química matemática, teste de isomorfismo do grafo é usado para identificar um composto químico dentro de uma base de dados de química.^[32] Além disso, em química matemática orgânica, o teste de isomorfismo do grafo é útil para a geração de gráficos moleculares]] e para a síntese de computador.

Pesquisa de banco de dados químico é um exemplo de Mineração de dados, onde a abordagem gráfico canonização é usado frequentemente.^[33]. Em particular, um número de identificadores para substâncias químicas, tais como SMILES e InChI, projetado para fornecer uma maneira padrão e legível de codificar a informação molecular e para facilitar a busca de tais informações em bases de dados e na web, usam etapa canonização em seu cálculo, que é essencialmente a canonização do grafo que representa a molécula.

Em projetos eletrônicos de automação, isomorfismo gráfico é o básico do passo de projeto de circuitos do Layout Versus Schematic (LVS), que é uma verificação se os circuitos elétricos representados por um esquema dos circuitos e um layout de circuitos integrados são os mesmos. ^[34]

Veja também

Notas

↑ Schöning (1987).
↑ McKay (1981).
↑ Ullman (1976).
↑ Moore, Russell & Schulman (2008).
↑ "Mathematician claims breakthrough in complexity theory".
↑ Foggia, Sansone & Vento (2001).
↑ Kelly (1957).
↑ Aho, Hopcroft & Ullman (1974).
↑ Hopcroft & Wong (1974).
↑ Datta et al. (2009).
↑ Booth & Lueker (1979).
↑ Colbourn (1981).
↑ Bodlaender (1990).
↑ Miller 1980; Filotti & Mayer 1980.
↑ Luks (1982).
↑ Babai, Grigoryev & Mount (1982).
↑ Miller (1983).
↑ Luks (1986).
↑ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993.
↑ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
↑ Arvind & Köbler (2000).
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s ^t ^u ^v ^w ^x Zemlyachenko, Korneenko & Tyshkevich (1985)
↑ Narayanamurthy & Ravindran (2008).
↑ Grigor'ev (1981).
↑ Johnson (2005); Kaibel & Schwartz (2003).
↑ Chung (1985).
↑ ^a ^b Kaibel & Schwartz (2003).
↑ Colbourn & Colbourn (1978).
↑ Kozen (1978).
↑ Shawe-Taylor & Pisanski (1994).
↑ Mathon (1979); Johnson 2005.
↑ Irniger (2005).
↑ Cook & Holder (2007).
↑ Baird & Cho (1975).

Referências

Aho, Alfred V.; Hopcroft, John; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading, MA: Addison-Wesley .
Arvind, Vikraman; Köbler, Johannes (2000), «Graph isomorphism is low for ZPP(NP) and other lowness results.», Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, ISBN 3-540-67141-2, Lecture Notes in Computer Science, 1770, Springer-Verlag, pp. 431–442, MR 1781752, doi:10.1007/3-540-46541-3_36 .
Arvind, Vikraman; Kurur, Piyush P. (2006), «Graph isomorphism is in SPP», Information and Computation, 204 (5): 835–852, MR 2226371, doi:10.1016/j.ic.2006.02.002 .
Babai, László (1980), «On the complexity of canonical labeling of strongly regular graphs», SIAM Journal on Computing, 9 (1): 212–216, MR 557839, doi:10.1137/0209018 .
Babai, László; Codenotti, Paolo (2008), «Isomorphism of hypergraphs of low rank in moderately exponential time» (PDF), Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), ISBN 978-0-7695-3436-7, IEEE Computer Society, pp. 667–676, doi:10.1109/FOCS.2008.80 .
Babai, László; Grigoryev, D. Yu.; Mount, David M. (1982), «Isomorphism of graphs with bounded eigenvalue multiplicity», Proceedings of the 14th Annual ACM Symposium on Theory of Computing, ISBN 0-89791-070-2, pp. 310–324, doi:10.1145/800070.802206 .
Babai, László; Kantor, William; Luks, Eugene (1983), «Computational complexity and the classification of finite simple groups», Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 162–171, doi:10.1109/SFCS.1983.10 .
Babai, László; Luks, Eugene M. (1983), «Canonical labeling of graphs», Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computin (STOC '83), ISBN 0-89791-099-0, pp. 171–183, doi:10.1145/800061.808746 .
Baird, H. S.; Cho, Y. E. (1975), «An artwork design verification system», Proceedings of the 12th Design Automation Conference (DAC '75), Piscataway, NJ, USA: IEEE Press, pp. 414–420 .
Blum, Manuel; Kannan, Sampath (1995), «Designing programs that check their work», Journal of the ACM, 42 (1): 269–291, doi:10.1145/200836.200880 .
Bodlaender, Hans (1990), «Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees», Journal of Algorithms, 11 (4): 631–643, MR 1079454, doi:10.1016/0196-6774(90)90013-5 .
Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report, CS-77-04, Computer Science Department, University of Waterloo .
Booth, Kellogg S.; Lueker, George S. (1979), «A linear time algorithm for deciding interval graph isomorphism», Journal of the ACM, 26 (2): 183–195, MR 0528025, doi:10.1145/322123.322125 .
Boucher, C.; Loker, D. (2006), Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs (PDF), Technical Report, CS-2006-32, Computer Science Department, University of Waterloo .
Chung, Fan R. K. (1985), «On the cutwidth and the topological bandwidth of a tree», SIAM Journal on Algebraic and Discrete Methods, 6 (2): 268–277, MR 778007, doi:10.1137/0606026 .
Colbourn, C. J. (1981), «On testing isomorphism of permutation graphs», Networks, 11: 13–21, MR 0608916, doi:10.1002/net.3230110103 .
Colbourn, Marlene Jones; Colbourn, Charles J. (1978), «Graph isomorphism and self-complementary graphs», ACM SIGACT News, 10 (1): 25–29, doi:10.1145/1008605.1008608 .
Cook, Diane J.; Holder, Lawrence B. (2007), «Section 6.2.1: Canonical Labeling», Mining Graph Data, ISBN 0-470-07303-9, Wiley, pp. 120–122 .
Datta, S.; Limaye, N.; Nimbhorkar, P.; Thierauf, T.; Wagner, F. (2009), «Planar graph isomorphism is in log-space», 2009 24th Annual IEEE Conference on Computational Complexity, ISBN 978-0-7695-3717-7, p. 203, doi:10.1109/CCC.2009.16 .
Filotti, I. S.; Mayer, Jack N. (1980), «A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus», Proceedings of the 12th Annual ACM Symposium on Theory of Computing, ISBN 0-89791-017-6, pp. 236–243, doi:10.1145/800141.804671 .
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, pp. 188–199 .
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 978-0-7167-1045-5, W. H. Freeman .
Grigor'ev, D. Ju. (1981), «Complexity of "wild" matrix problems and of the isomorphism of algebras and graphs», Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta imeni V. A. Steklova Akademii Nauk SSSR (LOMI) (em russo), 105: 10–17, 198, MR 628981 . English translation in Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
Hopcroft, John; Wong, J. (1974), «Linear time algorithm for isomorphism of planar graphs», Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 172–184, doi:10.1145/800119.803896 .
Irniger, Christophe-André Mario (2005), Graph Matching: Filtering Databases of Graphs Using Machine Learning, ISBN 1-58603-557-6, Dissertationen zur künstlichen Intelligenz, 293, AKA .
Kaibel, Volker; Schwartz, Alexander (2003), «On the complexity of polytope isomorphism problems», Graphs and Combinatorics, 19 (2): 215–230, MR 1996205, consultado em 11 de dezembro de 2015, cópia arquivada em |arquivourl= requer |arquivodata= (ajuda) 🔗 .
Kelly, Paul J. (1957), «A congruence theorem for trees», Pacific Journal of Mathematics, 7: 961–968, MR 0087949 .
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), «Graph isomorphism is low for PP», Computational Complexity, 2 (4): 301–330, MR 1215315, doi:10.1007/BF01200427 .
Kozen, Dexter (1978), «A clique problem equivalent to graph isomorphism», ACM SIGACT News, 10 (2): 50–52, doi:10.1145/990524.990529 .
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, MR 0685360, doi:10.1016/0022-0000(82)95009-5 .
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, MR 526453, doi:10.1016/0020-0190(79)95004-8 .
McKay, Brendan D. (1981), «Practical graph isomorphism», 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), Congressus Numerantium, 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, ISBN 0-89791-017-6, pp. 225–235, doi:10.1145/800141.804670 .
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, 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, Alexander; Schulman, Leonard J. (2008), «The symmetric group defies strong Fourier sampling», SIAM Journal on Computing, 37 (6): 1842–1864, MR 2386215, arXiv:quant-ph/0501056, doi:10.1137/050644896 .
Narayanamurthy, S. M.; Ravindran, B. (2008), «On the hardness of finding symmetries in Markov decision processes» (PDF), Proceedings of the Twenty-fifth International Conference on Machine Learning (ICML 2008), pp. 688–696 .
Schmidt, Douglas C.; Druffel, Larry E. (1976), «A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices», Journal of the ACM, 23 (3): 433–445, MR 0411230, doi:10.1145/321958.321963 .
Schöning, Uwe (1987), «Graph isomorphism is in the low hierarchy», Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, pp. 114–124 ; also Journal of Computer and System Sciences 37: 312–323, 1988.
Shawe-Taylor, John; Pisanski, Tomaž (1994), «Homeomorphism of 2-complexes is graph isomorphism complete», SIAM Journal on Computing, 23 (1): 120–132, MR 1258998, doi:10.1137/S0097539791198900 .
Spielman, Daniel A. (1996), «Faster isomorphism testing of strongly regular graphs», Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing (STOC '96), ISBN 978-0-89791-785-8, ACM, pp. 576–584 .
Ullman, Julian R. (1976), «An algorithm for subgraph isomorphism», Journal of the ACM, 23: 31–42, MR 0495173, doi:10.1145/321921.321925 .

Enquetes e monografias

Read, Ronald C.; Corneil, Derek G. (1977), «The graph isomorphism disease», Journal of Graph Theory, 1 (4): 339–363, MR 0485586, doi:10.1002/jgt.3190010410 .
Gati, G. (1979), «Further annotated bibliography on the isomorphism disease», Journal of Graph Theory, 3: 95–109 .
Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), «Graph isomorphism problem», Journal of Mathematical Sciences, 29 (4): 1426–1481, doi:10.1007/BF02104746 . (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118, pp. 83–158, 1982.)
Arvind, V.; Torán, Jacobo (2005), «Isomorphism testing: Perspectives and open problems» (PDF), Bulletin of the European Association for Theoretical Computer Science, 86: 66–84 . (A brief survey of open questions related to the isomorphism problem for graphs, rings and groups.)
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, ISBN 978-0-8176-3680-7, Birkhäuser . (From the book cover: The books focuses on the issue of the computational complexity of the problem and presents several recent results that provide a better understanding of the relative position of the problem in the class NP as well as in other complexity classes.)
Johnson, David S. (2005), «The NP-Completeness Column», ACM Transactions on Algorithms, 1 (no. 1): 160–176, doi:10.1145/1077464.1077476 . (Esta 24ª edição da Column discute o estado da arte dos problemas em aberto do livro Computers and Intractability e edições anteriores, em particular, para Isomorfismo Gráfico.)
Torán, Jacobo; Wagner, Fabian (2009), «The complexity of planar graph isomorphism» (PDF), Bulletin of the European Association for Theoretical Computer Science, 97, consultado em 11 de dezembro de 2015, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 .

Programas

Graph Isomorphism, review of implementations, The Stony Brook Algorithm Repository.

[FOOTNOTESchöning1987-1] Schöning (1987).

[FOOTNOTEMcKay1981-2] McKay (1981).

[FOOTNOTEUllman1976-3] Ullman (1976).

[FOOTNOTEMooreRussellSchulman2008-4] Moore, Russell & Schulman (2008).

[5] "Mathematician claims breakthrough in complexity theory".

[FOOTNOTEFoggiaSansoneVento2001-6] Foggia, Sansone & Vento (2001).

[FOOTNOTEKelly1957-7] Kelly (1957).

[FOOTNOTEAhoHopcroftUllman1974-8] Aho, Hopcroft & Ullman (1974).

[FOOTNOTEHopcroftWong1974-9] Hopcroft & Wong (1974).

[FOOTNOTEDattaLimayeNimbhorkarThierauf2009-10] Datta et al. (2009).

[FOOTNOTEBoothLueker1979-11] Booth & Lueker (1979).

[FOOTNOTEColbourn1981-12] Colbourn (1981).

[FOOTNOTEBodlaender1990-13] Bodlaender (1990).

[14] Miller 1980; Filotti & Mayer 1980.

[FOOTNOTELuks1982-15] Luks (1982).

[FOOTNOTEBabaiGrigoryevMount1982-16] Babai, Grigoryev & Mount (1982).

[FOOTNOTEMiller1983-17] Miller (1983).

[FOOTNOTELuks1986-18] Luks (1986).

[19] Booth & Colbourn 1977; Köbler, Schöning & Torán 1993.

[20] Köbler, Schöning & Torán 1992; Arvind & Kurur 2006

[FOOTNOTEArvindKöbler2000-21] Arvind & Köbler (2000).

[zkt-22] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s ^t ^u ^v ^w ^x Zemlyachenko, Korneenko & Tyshkevich (1985)

[FOOTNOTENarayanamurthyRavindran2008-23] Narayanamurthy & Ravindran (2008).

[FOOTNOTEGrigor'ev1981-24] Grigor'ev (1981).

[25] Johnson (2005); Kaibel & Schwartz (2003).

[FOOTNOTEChung1985-26] Chung (1985).

[FOOTNOTEKaibelSchwartz2003-27] Kaibel & Schwartz (2003).

[FOOTNOTEColbournColbourn1978-28] Colbourn & Colbourn (1978).

[FOOTNOTEKozen1978-29] Kozen (1978).

[FOOTNOTEShawe-TaylorPisanski1994-30] Shawe-Taylor & Pisanski (1994).

[31] Mathon (1979); Johnson 2005.

[FOOTNOTEIrniger2005-32] Irniger (2005).

[FOOTNOTECookHolder2007-33] Cook & Holder (2007).

[FOOTNOTEBairdCho1975-34] Baird & Cho (1975).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]