Contando instâncias de subgrafias

Question

Digamos que eu tenha um gráfico direcionado de vários milhares de milhares) G e um gráfico direcionado muito menor (3-5) g. Eu quero contar quantos isomorfismos de g estão dentro G. Em outras palavras, quero saber quantos conjuntos de nós exclusivos em G Combine g. Percebo que esta é uma instância do problema do isomorfismo do subgrafismo e, portanto, é NP-completo. No entanto, dado que você pode assumir que g É pequeno, existe algum algoritmo razoavelmente eficiente para fazer isso?

Answer 1

Embora o isomorfismo gráfico seja premiado em NP em geral, os problemas que você encontra no mundo real geralmente são muito fáceis. Uma força bruta simples deve ser suficiente: deixe M_i Seja um conjunto de mapas desde o primeiro I nós de G até os nós de G. Comece com m_0 contendo o mapa vazio e estendê -lo um nó de cada vez, descartando qualquer mapa que viole a restrição x->y iff m(x)->m(y).

Você vai querer pedir os nós em G para que muita poda aconteça mais cedo. Supondo que seus gráficos sejam bastante escassos, você desejará um pedido que complete o maior número possível de arestas, talvez um DFS do nó mais alto.