Problema de isomorfismo do gráfico - Graph isomorphism problem

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

O problema não é conhecido por ser solucionável em tempo polinomial nem por ser NP-completo e, portanto, pode estar na classe de complexidade computacional NP-intermediária . Sabe-se que o problema de isomorfismo de grafos está na baixa hierarquia da classe NP , o que implica que não é NP-completo a menos que a hierarquia de tempo polinomial entre em colapso para seu 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 de grafos pode frequentemente ser resolvido de forma eficiente.

Este problema é um caso especial do problema de isomorfismo do subgrafo , que pergunta se um dado grafo G contém um subgrafo que é isomorfo a outro dado grafo H ; este problema é conhecido como NP-completo. Também é conhecido por ser um caso especial do problema do subgrupo oculto não abeliano sobre o grupo simétrico .

Na área de reconhecimento de imagem , é conhecido como correspondência exata de gráfico .

Estado da arte

Em novembro de 2015, László Babai anunciou um algoritmo de tempo quase - lipolinomial para todos os gráficos, ou seja, um com tempo de execução para alguns fixo . Em 4 de janeiro de 2017, Babai retirou a afirmação quase polinomial e declarou um limite de tempo subexponencial depois que Harald Helfgott descobriu uma falha na prova. Em 9 de janeiro de 2017, Babai anunciou uma correção (publicada na íntegra em 19 de janeiro) e restaurou a reivindicação quase polinomial, com Helfgott confirmando a correção. Helfgott afirma ainda que se pode tomar c = 3 , então o tempo de execução é 2 ^{O ((log n ) 3 )} . ${\ displaystyle 2 ^ {O ((\ log n) ^ {c})}}$${\ displaystyle c> 0}$

Antes disso, o algoritmo teórico mais aceito atualmente foi devido a Babai & Luks (1983) , e é baseado no trabalho anterior de Luks (1982) combinado com um algoritmo subfatorial de VN Zemlyachenko ( Zemlyachenko, Korneenko & Tyshkevich 1985 ). O algoritmo tem tempo de execução 2 ^{O ( √ n  log  n )} para gráficos com n vértices e se baseia na classificação de grupos simples finitos . Sem este teorema de classificação, um limite ligeiramente mais fraco 2 ^{O ( √ n  log 2  n )} foi obtido primeiro para gráficos fortemente regulares por László Babai  ( 1980 ), e então estendido para gráficos gerais por Babai & Luks (1983) . A melhoria do expoente √ n é um grande problema em aberto; para gráficos fortemente regulares, isso foi feito por Spielman (1996) . Para hipergrafos de classificação limitada, um limite superior subexponencial correspondente ao caso dos gráficos foi obtido por Babai & Codenotti (2008) .

Existem vários algoritmos práticos concorrentes para isomorfismo de grafos, como os devidos a McKay (1981) , Schmidt & Druffel (1976) e Ullman (1976) . Embora pareçam ter um bom desempenho em gráficos aleatórios , uma grande desvantagem desses algoritmos é seu desempenho de tempo exponencial no pior caso .

O problema de isomorfismo de grafo é computacionalmente equivalente ao problema de cálculo do grupo de automorfismo de um grafo, e é mais fraco do que o problema de isomorfismo do grupo de permutação e o problema de interseção do grupo de permutação. Para os dois últimos problemas, Babai, Kantor & Luks (1983) obtiveram limites de complexidade semelhantes aos do isomorfismo de grafos.

Casos especiais resolvidos

Vários casos especiais importantes do problema de isomorfismo de grafos têm soluções eficientes em tempo polinomial:

• Arvores
• Grafos planos (na verdade, o isomorfismo dos grafos planares está no espaço de log , uma classe contida em P )
• Gráficos de intervalo
• Gráficos de permutação
• Gráficos circulantes
• Gráficos de parâmetros limitados
  • Gráficos de largura da árvore limitada
  • Gráficos do gênero limitado (os gráficos planares são gráficos do gênero 0.)
  • Gráficos de grau limitado
  • Gráficos com multiplicidade de autovalores limitada
  • k -Grafos contráteis (uma generalização de grau limitado e gênero limitado)
  • O isomorfismo de preservação de cor de gráficos coloridos com multiplicidade de cores limitada (ou seja, no máximo k vértices têm a mesma cor para um k fixo ) está na classe NC , que é uma subclasse de P

Classe de complexidade GI

Uma vez que o problema de isomorfismo de grafos não é conhecido como NP-completo nem tratável, os pesquisadores buscaram obter um insight sobre o problema definindo uma nova classe GI , o conjunto de problemas com uma redução de Turing em tempo polinomial para o isomorfismo de grafos problema. Se de fato o problema gráfico isomorfismo pode ser resolvido em tempo polinomial, GI seria igual a P . Por outro lado, se o problema for NP-completo, GI seria igual a NP e todos os problemas em NP seriam solucionáveis ​​em tempo quase polinomial.

Como é comum para classes de complexidade dentro da hierarquia de tempo polinomial , um problema é chamado de GI difícil se houver uma redução de Turing em tempo polinomial de qualquer problema em GI para esse problema, ou seja, uma solução em tempo polinomial para um problema GI difícil resultaria em uma solução em tempo polinomial para o problema de isomorfismo de grafos (e assim todos os problemas em GI ). Um problema é chamado de completo para GI , ou GI-completo , se for GI-hard e uma solução em tempo polinomial para o problema GI renderia uma solução em tempo polinomial para . ${\ displaystyle X}$${\ displaystyle X}$

O problema do isomorfismo de grafos está contido tanto em NP quanto em co- AM . GI está contido e baixo para Paridade P , bem como contido na classe SPP potencialmente muito menor . O fato de estar na 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 em tempo polinomial tem um número par ou ímpar de caminhos de aceitação. GI também está contido e baixo para ZPP ^NP . Isso significa essencialmente que um algoritmo eficiente de Las Vegas com acesso a um oráculo NP pode resolver o isomorfismo de grafo tão facilmente que não ganha força por ter a capacidade de fazê-lo em tempo constante.

Problemas GI completos e GI difíceis

Isomorfismo de outros objetos

Existem várias classes de objetos matemáticos para os quais o problema de isomorfismo é um problema GI completo. Vários deles são gráficos dotados de propriedades ou restrições adicionais:

• dígrafos
• gráficos rotulados , com a ressalva de que não é necessário um isomorfismo para preservar os rótulos, mas apenas a relação de equivalência composta por pares de vértices com o mesmo rótulo
• "grafos polarizados" (feitos de um grafo completo K _m e um grafo vazio K _n mais algumas arestas conectando os dois; seu isomorfismo deve preservar a partição)
• Gráficos de 2 cores
• estruturas finitas explicitamente dadas
• multigrafos
• hipergrafos
• autômatos finitos
• Processos de decisão de Markov
• classe comutativa 3 nilpotente (ou seja, xyz = 0 para todos os elementos x , y , z ) semigrupos
• álgebras associativas de classificação finita sobre um campo algebricamente fechado com radical zero ao quadrado e fator comutativo sobre o radical.
• gramáticas livres de contexto
• projetos de blocos incompletos balanceados
• Reconhecer o isomorfismo combinatório de politopos convexos representados por incidências de facetas de vértices.

Classes de gráficos de GI completo

Uma classe de gráficos é chamada de GI-completo se o reconhecimento de isomorfismo para gráficos dessa subclasse for um problema de GI-completo. As seguintes classes são GI-completas:

• gráficos conectados
• gráficos de diâmetro 2 e raio 1
• gráficos acíclicos dirigidos
• gráficos regulares
• grafos bipartidos sem subgráficos não triviais fortemente regulares
• gráficos eulerianos bipartidos
• gráficos regulares bipartidos
• gráficos de linha
• gráficos de divisão
• gráficos de cordas
• gráficos autocomplementares regulares
• gráficos de politopos de politopos convexos gerais, simples e simpliciais em dimensões arbitrárias.

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

Outros problemas de GI-completo

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

• O reconhecimento da auto-complementaridade de um gráfico ou dígrafo.
• Um problema de clique para uma classe dos chamados gráficos - M . É mostrado que encontrar um isomorfismo para gráficos de n- vértices é equivalente a encontrar um n -clique em um gráfico M de tamanho n ² . Este fato é interessante porque o problema de encontrar uma ( n  -  ε ) -clique em um gráfico M de tamanho n ² é NP-completo para ε positivo arbitrariamente pequeno.
• O problema do homeomorfismo de 2 complexos.

Problemas difíceis de GI

• O problema de contar o número de isomorfismos entre dois gráficos é equivalente em tempo polinomial ao problema de dizer se existe um.
• O problema de decidir se dois politopos convexos dados pela descrição V ou pela descrição H são projetiva ou afinamente isomórficos. Este último significa a existência de um mapa projetivo ou afim entre os espaços que contêm os dois politopos (não necessariamente da mesma dimensão) que induz uma bijeção entre os politopos.

Verificação de programa

Manuel Blum e Sampath Kannan ( 1995 ) mostraram um verificador probabilístico para programas de isomorfismo de grafos. Suponha que P seja um procedimento de tempo polinomial reivindicado que verifica se dois gráficos são isomórficos, mas não é confiável. Para verificar se G e H são isomórficos:

• Pergunte a P se G e H são isomórficos.
  • Se a resposta é sim":
    • Tente construir um isomorfismo usando P como sub-rotina. Marcar um vértice u em G e v em H , e modificar os gráficos para torná-los distintivo (com uma pequena mudança local). Pergunte a P se os gráficos modificados são isomórficos. Se não, mude v para um vértice diferente. Continue procurando.
    • Ou o isomorfismo será encontrado (e pode ser verificado), ou P irá se contradizer.
  • Se a resposta for "não":
    • Execute as seguintes 100 vezes. Escolha aleatoriamente G ou H , e permute aleatoriamente seus vértices. Peça P se o gráfico é isomorfa a G e H . (Como no protocolo AM para nonisomorfismo de gráfico).
    • Se algum dos testes falhar, julgue P como programa inválido. Caso contrário, responda "não".

Este procedimento é em tempo polinomial e fornece a resposta correta se P for um programa correto para isomorfismo de grafos. Se P não é um programa correto, mas responde corretamente em G e H , o verificador irá quer dar a resposta correta, ou detectar comportamento inválido de P . Se P não for um programa correto e responder incorretamente em G e H , o verificador detectará o comportamento inválido de P com alta probabilidade ou responderá errado com probabilidade 2 ⁻¹⁰⁰ .

Notavelmente, P é usado apenas como uma caixa preta.

Formulários

Os gráficos são comumente usados ​​para codificar informações estruturais em muitos campos, incluindo visão computacional e reconhecimento de padrões , e a correspondência de gráficos , ou seja, a identificação de semelhanças entre gráficos, é uma ferramenta importante nessas áreas. Nessas áreas, o problema de isomorfismo de gráfico é conhecido como correspondência exata de gráfico.

Em quiminformática e em química matemática , o teste de isomorfismo de gráfico é usado para identificar um composto químico em um banco de dados químico . Além disso, em química orgânica, o teste de isomorfismo de gráfico é útil para a geração de gráficos moleculares e para a síntese de computador .

A pesquisa de banco de dados químico é um exemplo de mineração de dados gráficos , onde a abordagem de canonização de gráfico é frequentemente usada. Em particular, uma série de identificadores para substâncias químicas , como SMILES e InChI , projetados para fornecer uma forma padrão e legível para codificar informações moleculares e facilitar a busca por tais informações em bancos de dados e na web, usam a etapa de canonização em seu cálculo, que é essencialmente a canonização do gráfico que representa a molécula.

Na automação do projeto eletrônico, o isomorfismo do gráfico é a base da etapa de projeto do circuito Layout Versus Schematic (LVS), que é uma verificação se os circuitos elétricos representados por um esquema de circuito e um layout de circuito integrado são iguais.

Veja também

• Problema de automorfismo de gráfico
• Canonização de grafos

Notas

Referências