Zählen von Subgraph -Instanzen

Question

Nehmen wir an, ich habe einen großen (mehrere tausend Knoten) gerichteten Diagramm G und ein viel kleinerer (3-5 Knoten) gerichtetes Diagramm g. Ich möchte zählen, wie viele Isomorphismen von g sind in G. Mit anderen Worten, ich möchte wissen, wie viele einzigartige Sätze von Knoten in G passen g. Mir ist klar, dass dies eine Instanz des Problems des Subgraphen-Isomorphismus ist und daher NP-Vervollständigung ist. Angesichts der Tatsache, dass Sie dies jedoch annehmen können g Ist klein, gibt es dafür einen einigermaßen effizienten Algorithmus dafür?

Answer 1

Obwohl das Graph-Isomorphismus im Allgemeinen NP-Vervollständigung ist, sind Probleme, auf die Sie in der realen Welt stoßen, oft ziemlich einfach. Eine einfache Brute-Force sollte ausreichen: Lass es M_i Seien Sie eine Reihe von Karten von den ersten I -Knoten von G bis zu Knoten von G. Beginnen Sie mit m_0 Enthält die leere Karte und erweitern Sie sie jeweils einen Knoten, wobei Sie alle Karten verworfen, die gegen die Einschränkung verstoßen x->y IFF m(x)->m(y).

Sie möchten die Knoten in G bestellen, damit viel Beschneidung früh passiert. Angenommen, Ihre Diagramme sind ziemlich spärlich, möchten Sie eine Bestellung, die so früh wie möglich so früh wie möglich abschließt, vielleicht einen DFS vom Knoten mit höchster Grad.