Problema de isomorfismo de grafos

Fonte: testwiki
Saltar para a navegação Saltar para a pesquisa

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.Predefinição:Sfnp 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.Predefinição:Sfnp

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 Predefinição:Sfnp, 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.Predefinição:Sfnp

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. [1]

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.Predefinição:Sfnp

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:

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.[3] 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. [4] 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.Predefinição:Sfnp 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: [5]

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:  [5]

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.Predefinição:Sfnp
  • 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 ε.Predefinição:Sfnp
  • O problema de equivalência topológica de 2-complexos.Predefinição:Sfnp

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.[7]
  • 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.Predefinição:Sfnp

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.Predefinição:Sfnp 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.Predefinição:Sfnp. 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. Predefinição:Sfnp

Veja também

Notas

Predefinição:Reflist

Referências

Predefinição:Refbegin

Enquetes e monografias

Programas

Predefinição:Refend

  1. ↑ "Mathematician claims breakthrough in complexity theory".
  2. ↑ Predefinição:Harvnb; Predefinição:Harvnb.
  3. ↑ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993.
  4. ↑ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
  5. ↑ 5,00 5,01 5,02 5,03 5,04 5,05 5,06 5,07 5,08 5,09 5,10 5,11 5,12 5,13 5,14 5,15 5,16 5,17 5,18 5,19 5,20 5,21 5,22 5,23 Zemlyachenko, Korneenko & Tyshkevich (1985)
  6. ↑ Johnson (2005); Kaibel & Schwartz (2003).
  7. ↑ Mathon (1979); Johnson 2005.
Obtida de "https://pt.wiki.beta.math.wmflabs.org/w/index.php?title=Problema_de_isomorfismo_de_grafos&oldid=6892"