Listing subgraphs of G isomorphic to SubG

Question

If I have an undirected graph G, how could I write a function in Mathematica to obtain a list of subgraphs of G that are isomorphic to some other undirected graph SubG?

I'd like to learn how to program better in Mathematica (unless I explicitly try to prevent it, currently everything I write ends up looking like C code). So please feel free to go heavy on the suggestions of how to approach problems in Mathematica... the "philosophy" of Mathematica programming if you will.

An attempt to show all such graphs is the following:

SubgraphQ[g_,sg_] := Sort[EdgeList[GraphIntersection[g,sg]]]==Sort[EdgeList[sg]]
vertexperm = Thread[#]& /@ 
  ((VertexList[SubG] -> #)& /@ Permutations[VertexList[G],{VertexCount[SubG]}]);
result=Select[vertexperm,SubgraphQ[G,VertexReplace[SubG,#]]&];
HighlightGraph[G,VertexReplace[SubG,#]]& /@ result

I tested it with the following

{G, SubG} = {PetersenGraph[5,2],EdgeAdd[CycleGraph[5],5<->6]};

and the ideas works. Although since the subgraph has some reordering symmetry (even more obvious if using SubG=CycleGraph[5]), it erroneously gives some identical graphs in the output.

I tried testing it on a 16 vertex graph and a 16 vertex subgraph that I built from hand (and should only have one match), but Mathematica refuses to do the permutations since "it has length at least 13 factorial, which is not a machine integer".

---

Note:
This question is a generalization of the question
Cycles of length N in a graph

Looking around, many of the answers that "look nice" in Mathematica seem to just be "produce the set of all possible answers" and then "prune the set to the correct answers". That sounds like it would take much much more memory, and at least as many (if not more) operations than just the iterating "for loops" type method that pops into my mind from doing procedural programming. Consider for instance sorting a list by using Permutations and then pruning with OrderedQ. Sure it may look short and be conceptually simple, but it is an absolutely horrible way to sort. This is also a good example because the straight forward "for loop" approach (bubble sort) is quick to program, but also not a reasonable algorithm for decent sized lists. In this case Mathematica has a built in Sort. Whenever Mathematica doesn't have a built in solution, I feel like I have to choose between wasting tons of memory or writing lots of code that looks like C but with none of the speed advantages if I had just written it in C.

Even if this is an NP hard problem (I hope it isn't) is there some way to save on memory without resorting to a bunch of "for loops"? Maybe a more intelligent iterator or something? But really what I want is to leverage the abstract capabilities of Mathematica to solve what feels like an inherently mathematical problem. It feels like this should be the correct language to use for these types of problems.

Answer 1

Update: I now recommend using the IGraph/M package instead of the R interface. It offers the following functions for finding subgraphs:

• IGSubisomorphicQ tests for subgraph isomorphism, supports multigraphs as well.
• IGVF2FindSubisomorphisms lists all matching subgraphs found, supports vertex and edge coloured graphs.
• IGLADFindSubisomorphisms lists all matching subgraphs founds, supports vertex colouring, supports looking only for induced sugraphs.

---

Daniel is completely correct that this is a hard problem and will usually take a very very long time. However, the igraph library does have a function for it and you can call it through this package. Please read the instructions on how to set up the package, then do this:

{g, subG} = {PetersenGraph[5, 2], EdgeAdd[CycleGraph[5], 5 <-> 6]}

res = IGraph["graph.get.subisomorphisms.vf2"][g, subG];

HighlightGraph[g, Subgraph[g, #]] & /@ Round[res + 1]

Use graph.count.subisomorphisms.vf2 to just count the subgraphs but not retrieve them.

Answer 2

This is a computationally hard problem. Graph isomorphism is not known to be NP (and also not known to be otherwise). But subgraph isomorphism is, I'm pretty sure, NP-complete. And it looks like that is what you are wanting here.

In contrast, finding cycles is probably not much worse than all-pairs shortest paths. But it will take careful coding. Possibly one might instead use Combinatorica's NumberOfKPaths on each vertex. I do not know how it is implemented, hence cannot comment on efficiency or possible lack thereof.

--- edit --- Finding cycles can be, in worst case, exponentially difficult. For the simple reason that there might be exponentially many. I think the correct claim is that it has complexity something like O(l*n*e+c) where l = cycle length, n = #vertices, e = #edges, and c = #cycles. That's just a guess though. The approach I have in mind could be worse insofar as there could be many candidates that get pruned along the way, that is, as the cycles get built. --- end edit ---