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. 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.
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 , 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.
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 2O(√n log2 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. "Mathematician claims breakthrough in complexity theory"
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.
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 Grafos planares (Na verdade, isomorfismo de grafos planares está no espaço logarítimo, uma classe contida em P) Grafos de intervalo Grafos de permutação Grafos limitado pelo parâmetro Grafos de largura de árvore limitada. Grafos de gênero limitados; . (Nota: grafos planares são gráficos de gênero 0) Grafos de grau limitado Grafos com multiplicidade limitada de Autovalor (eigenvalue) Grafos k-contrátil (uma generalização do grau limitado e gênero limitada) 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
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.Booth & Colbourn 1977; Köbler, Schöning & Torán 1993. 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 .
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. Köbler, Schöning & Torán 1992; Arvind & Kurur 2006 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 ZPPNP. 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: Zemlyachenko, Korneenko & Tyshkevich (1985) DígrafosZemlyachenko, Korneenko & Tyshkevich (1985) Gráficos rotulados, com a condição de que um isomorfismo não é necessário para preservar os rótulos,Zemlyachenko, Korneenko & Tyshkevich (1985) 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)Zemlyachenko, Korneenko & Tyshkevich (1985) Grafos 2-coloridosZemlyachenko, Korneenko & Tyshkevich (1985) Estruturas finitas dadas explicitamenteZemlyachenko, Korneenko & Tyshkevich (1985) MultigrafosZemlyachenko, Korneenko & Tyshkevich (1985) HipergrafosZemlyachenko, Korneenko & Tyshkevich (1985) Autômatos FinitosZemlyachenko, Korneenko & Tyshkevich (1985) Processos de Decisão Markovianos Classe comutativa com 3 semigrupos nilpotentes (ou seja, xyz = 0 para cada elementos x, y, z) Zemlyachenko, Korneenko & Tyshkevich (1985) Álgebras associativas de ranks finitos sobre um campo fechado algebricamente fixo com zero radicais quadraticos e fator comutativo sobre o radical. Zemlyachenko, Korneenko & Tyshkevich (1985) Gramáticas livre do contexto Zemlyachenko, Korneenko & Tyshkevich (1985) Projeto de blocos balanceados incompletos Zemlyachenko, Korneenko & Tyshkevich (1985) Reconhecendo isomorfismo combinatorial de politopos convexos representados por incidência vértice-face. Johnson (2005); Kaibel & Schwartz (2003).
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: Zemlyachenko, Korneenko & Tyshkevich (1985) Grafos conectadosZemlyachenko, Korneenko & Tyshkevich (1985) Grafos de diâmetro 2 e raio 1Zemlyachenko, Korneenko & Tyshkevich (1985) Grafos acíclicos dirigidosZemlyachenko, Korneenko & Tyshkevich (1985) Grafos regularesZemlyachenko, Korneenko & Tyshkevich (1985) Grafos bipartidos sem subgrafos fortemente regulares não-triviais Zemlyachenko, Korneenko & Tyshkevich (1985) Grafos Euleriano bipartidosZemlyachenko, Korneenko & Tyshkevich (1985) Grafos regulares bipartidosZemlyachenko, Korneenko & Tyshkevich (1985) Grafos LinearesZemlyachenko, Korneenko & Tyshkevich (1985) Grafos divididos Grafos cordaisZemlyachenko, Korneenko & Tyshkevich (1985) Grafos auto-complementares regularesZemlyachenko, Korneenko & Tyshkevich (1985) Grafos de politopos convexos gerais, simples e politopos convexos simplicial dimensões arbitrárias. 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. 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 n2. Este fato é interessante porque o problema de encontrar um (n − ε)-clique em um M-grafo de tamanho n2 é NP-completo para arbitrariamente pequena ε positivo ε. O problema de equivalência topológica de 2-complexos.
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.Mathon (1979); Johnson 2005. 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.
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−100.
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. 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.