Problema do isomorfismo de subgrafos

Predefinição:Sem notasEm teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo.

Definição

Isomofismo de Subgrafos $(G_1,G_2)$
Entrada: Dois grafos $G_1$ e $G_2$.
Pergunta: $G_1$ é isomórfico (há um isomorfismo de grafos) a um subgrafo de $G_2$?

Ou, informalmente: tome dois grafos não dirigidos $G_1$ e $G_2$ e verifique se $G_1$ é subgrafo de $G_2$ (a menos de um isomorfismo) ou não. Em outras palavras, o problema verifica se há ou não uma função $f$ que mapeie os vértices de $G_1$ nos vértices de $G_2$ de forma tal que haja uma aresta $\{u,v\}$ em $G_1$ exatamente quando $\{f(u),f(v)\}$ está em $G_2$.

Algumas vezes o nome casamento de subgrafos é usado para o mesmo problema. Este nome dá ênfase à busca de um tal subgrafo, em contraste ao mero problema de decisão.

Classe de Complexidade

A demonstração de que o problema do isomorfismo de subgrafos é NP-completo é simples e baseada na redução ao problema do clique (que se sabe ser NP-completo), mostrando que CLIQUE $\le$ _p isomorfismo de subgrafos. Se o isomorfismo de subgrafos fosse polinomial, poder-se-ia usá-lo para resolver o problema do clique em tempo polinomial. Tome n como o número de arestas em $G$: poder-se-ia então rodar o isomorfismo de subgrafos $n-2$ vezes (com $G_1$ sendo um clique de tamanho 3 até $n$, e $G_2$ sendo $G$) para encontrar o maior clique em $G$.

O isomorfismo de subgrafos é uma generalização do problema potencialmente mais fácil do isomorfismo de grafos; se o problema do isomorfismo de grafos fosse NP-completo, a hierarquia polinomial colapsaria, então suspeita-se que ele não o seja.

Áreas de aplicação

Na área de quimioinformática freqüentemente o termo pesquisa de subestruturas é usado. Tipicamente uma estrutura de consulta é definida como SMARTS, uma extensão de SMILES.

É também de grande importância para gramáticas de grafos.

Bibliografia

• J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
• Predefinição:Citar livro A1.4: GT48, pg.202.