# 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. 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 2$^{O(√nlog2n)}$ 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.
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. 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. 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}$. 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:
* Dígrafos
* Gráficos rotulados, com a condição de que um isomorfismo não é necessário para preservar os rótulos, 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)
* Grafos 2-coloridos
* Estruturas finitas dadas explicitamente
* Multigrafos
* Hipergrafos
* Autômatos Finitos
* Processos de Decisão Markovianos
* Classe comutativa com 3 semigrupos nilpotentes (ou seja, xyz = 0 para cada elementos x, y, z)
* Álgebras associativas de ranks finitos sobre um campo fechado algebricamente fixo com zero radicais quadraticos e fator comutativo sobre o radical.
* Gramáticas livre do contexto
* Projeto de blocos balanceados incompletos
* Reconhecendo isomorfismo combinatorial de politopos convexos representados por incidência vértice-face.

#### 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:
* Grafos conectados
* Grafos de diâmetro 2 e raio 1
* Grafos acíclicos dirigidos
* Grafos regulares
* Grafos bipartidos sem subgrafos fortemente regulares não-triviais
* Grafos Euleriano bipartidos
* Grafos regulares bipartidos
* Grafos Lineares
* Grafos divididos
* Grafos cordais
* Grafos auto-complementares regulares
* 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 n$^2$. Este fato é interessante porque o problema de encontrar um (n − ε)-clique em um M-grafo de tamanho n$^2$ é 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.
* 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.
Pesquisa de banco de dados químico é um exemplo de Mineração de dados, onde a abordagem gráfico canonização é usado frequentemente.. 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.

## Veja também

* Problema Grafo automórfico
* Canonização de grafos