Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
3  
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
add comment

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

share|improve this answer
    
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. –  Tobi Lehman 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. –  billisphere 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
add comment

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]

enter image description here

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.