Counting Subgraph Instances

Question

Let's say I have a large (several thousand node) directed graph G and a much smaller (3-5 node) directed graph g. I want to count how many isomorphisms of g are in G. In other words, I want to know how many unique sets of nodes in G match g. I realize that this is an instance of the subgraph isomorphism problem and is therefore NP-complete. However, given that you may assume that g is small, is there any reasonably efficient algorithm for doing this?

Answer 1

Although graph isomorphism is NP-complete in general, problems you come across in the real world are often pretty easy. A simple brute-force should suffice: Let M_i be a set of maps from the first i nodes of g to nodes of G. Start with m_0 containing the empty map and extend it one node at a time, discarding any maps which violate the constraint x->y iff m(x)->m(y).

You'll want to order the nodes in g so that lots of pruning happens early. Assuming your graphs are pretty sparse, you'll want an order that completes as many edges as early as possible, maybe a dfs from the highest degree node.