Contare le istanze del sottografo

Question

Diciamo che ho un grafico diretto (diverse migliaia di nodi) G e un grafico diretto molto più piccolo (3-5 nodo) g. Voglio contare quanti isomorfismi di g sono dentro G. In altre parole, voglio sapere quanti set di nodi unici G incontro g. Mi rendo conto che questa è un'istanza del problema dell'isomorfismo del sottografo ed è quindi completa NP. Tuttavia, dato che potresti supporre che questo g È piccolo, c'è qualche algoritmo ragionevolmente efficiente per farlo?

Answer 1

Sebbene l'isomorfismo grafico sia completo NP in generale, i problemi che si incontrano nel mondo reale sono spesso abbastanza facili. Una semplice forza bruta dovrebbe essere sufficiente: lascia M_i essere un insieme di mappe dal primo I nodi di G ai nodi di G. Inizia con m_0 contenente la mappa vuota ed estenderla un nodo alla volta, scartando eventuali mappe che violano il vincolo x->y Iff m(x)->m(y).

Ti consigliamo di ordinare i nodi in G in modo che molta potatura avvenga presto. Supponendo che i tuoi grafici siano piuttosto scarsi, vorrai un ordine che completa il maggior numero possibile di bordi, forse un DFS dal nodo di massima laurea.