# Listing subgraphs of G isomorphic to SubG

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]]
((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<->6]};


and the ideas works. Although since the subgraph has some reordering symmetry (even more obvious if using SubG=CycleGraph), 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.

• You should probably be aware that IsomorphicGraphQ is buggy – Szabolcs Mar 9 '12 at 8:24
• IsomorphicGraphQ is not buggy any more in version 9. – Szabolcs May 2 '13 at 20:48
• Subgraphs are determined by vertex subsets. For a given size you can test each subgraph of that size against your specified graph. This would use the standard IsomorphicGraphQ, hence require no permutations. – Daniel Lichtblau May 2 '13 at 21:52

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 <-> 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.

• It seems that graph.get.subisomorphisms.vf2 here returns induced subgraphs in your example. Is it a coincidence? As in the document, only lad method has the option to return induced subgraphs. – Han Xiao Nov 14 '15 at 7:23
• @HanXiao For this example there is no match which is not an induced subgraph, so yes, it's a coincidence. VF2 does not support searching only for induced subgraphs. BTW consider using IGraphM instead of the R interface. – Szabolcs Nov 14 '15 at 10:32
• Thanks for the quick reply. BTW, I have been waiting for a interface like IGraphM for a long time! – Han Xiao Nov 14 '15 at 11:09

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 ---

• This is true, but @WideEyed wasn't asking about the efficiency or computational complexity of the problem, even if the problem is NP-complete, it can be solved, just slowly. – tlehman Mar 9 '12 at 18:06
• I know. But my remarks were a bit more than I wanted to put in a comment. Especially as I don't know how to make more than one paragraph without the comment posting itself. – Daniel Lichtblau Mar 9 '12 at 18:47
• I think you meant that GI is not known to be NP-complete, as it is known to be in NP. – William Mar 10 '12 at 21:16
• Yes, NP-complete is the unknown for graph isomorphism. Me, I'm betting against it. – Daniel Lichtblau Mar 11 '12 at 3:53
• Subgraph isomorphism (the language $\{ \langle G, H \rangle : H \subseteq G \}$ is trivially in NP (witness a set of vertices and a permutation), and is easily seen to be NP-complete by reducing from Clique. – wchargin Nov 26 '17 at 3:04