Maneira fácil de determinar se um determinado gráfico é subgrafo de algum outro gráfico?

Question

Estou procurando um algoritmo para verificar se um determinado gráfico é subgrafo de outro gráfico.

Tenho poucas condições para tornar esse problema NP completo um pouco mais viável.

• Os gráficos têm aproximadamente <20 vértices.
• Os gráficos são DAG.
• Todos os vértices não são rotulados de forma exclusiva, e os vértices correspondentes no gráfico principal e no subgrafo devem ter o mesmo rótulo.Não sei se estou usando as terminologias corretas (porque não fiz curso de teoria dos grafos...).Será algo como:

O gráfico de linha A--B é subgrafo de A--B--A, mas A--A não é um subgrafo de A--B--A.

Qualquer sugestão está bem.Esta não é uma questão de dever de casa, aliás.:D

Answer 1

Se os rótulos forem únicos, para um gráfico de tamanho N, existem O(N^2) arestas, assumindo que não há loops auto ou múltiplas bordas entre cada par de vértices. Vamos usar E Para o número de arestas.

Se você hash as bordas do conjunto no gráfico pai, poderá passar pelas bordas do subgraf, verificando se cada uma estiver na tabela de hash (e na quantidade correta, se desejado). Você está fazendo isso uma vez para cada vantagem, portanto, O(E).

Vamos chamar o gráfico G (com N vértices) e o possível subgraf G_1 (com M vértices), e você quer encontrar G_1 is in G.

Como os rótulos não são únicos, você pode, com programação dinâmica, construir os subproblemas como tal - em vez de ter O(2^N) Subproblemas, um para cada subcágrafo, você tem O(M 2^N) subproblemas - um para cada vértice em G_1 (com M vértices) com cada um dos possíveis subgrafos.

G_1 is in G = isSubgraph( 0, empty bitmask)

E os estados são criados como tal:

isSubgraph( index, bitmask ) =
   for all vertex in G
       if G[vertex] is not used (check bitmask)
          and G[vertex]'s label is equal to G_1[index]'s label
          and isSubgraph( index + 1, (add vertex to bitmask) )
               return true
   return false

com o caso base sendo index = M, e você pode verificar a igualdade nas bordas, dada a máscara (e um mapeamento implícito de etiquetas). Como alternativa, você também pode fazer a verificação na instrução IF - basta verificar se dado a corrente index, o subgrafal atual G_1[0..index] é igual a G[bitmask] (com o mesmo mapeamento de etiqueta implícito) antes de se repetir.

Por N = 20, isso deve ser rápido o suficiente.

(Adicione seu memorando, ou você pode reescrever isso usando o fundo de baixo para cima).

Answer 2

Ok, eu tenho que fazer a pergunta óbvia. 1. Você tem vinte vértices. Caminhe cada gráfico em profundidade primeiro, ordem alfabética entre os irmãos para obter cordas. 2. Um gráfico é um subgraf de outra string iff uma em outra.

Então, o que mais está se escondendo na especificação do problema para tornar isso inviável?

Answer 3

Você pode ver isso como um problema de alinhamento.Basicamente você quer criar um mapeamento injetivo a que mapeia cada vértice em V_1 para um vértice em V_2.Um mapa de alinhamento a pode ser pontuado da seguinte forma:

s(a) = \sum_{(v,w) \in E_1} \sigma(v, w, a(v), a(w)),

onde \sigma(v, w, a(v), a(w)) = 1, se (a(v), a(w)) \in E_2 caso contrário é 0.

Acho que isso pode ser formulado na forma de um programa linear inteiro.