Why is IsomorphicGraphQ so very slow (in this instance)

Bug introduced in 10.0 or earlier and persisting through 12.1

Can someone explain why the following code does not complete within a reasonable time?

l = {{208, 108}, {208, 112}, {208, 116}, {208, 120}, {208, 124}, {208, 128}, {208, 132}, {208, 136}, {208, 140}, {208, 144}, {208, 148}, {208, 152}, {212, 211}, {212, 208}, {212, 209}, {212, 210}, {209, 109}, {209, 113}, {209, 117}, {209, 121}, {209, 125}, {209, 129}, {209, 133}, {209, 137}, {209, 141}, {209, 145}, {209, 149}, {209, 153}, {210, 110}, {210, 114}, {210, 118}, {210, 122}, {210, 126}, {210, 130}, {210, 134}, {210, 138}, {210, 142}, {210, 146}, {210, 150}, {210, 154}, {211, 111}, {211, 115}, {211, 119}, {211, 123}, {211, 127}, {211, 131}, {211, 135}, {211, 139}, {211, 143}, {211, 147}, {211, 151}, {211, 155}};

g1 = Graph[DirectedEdge[{10, 53, #1, 91}, {10, 53, #2, 91}] & @@@ l];
g2 = Graph[DirectedEdge[{10, 53, #1, 84}, {10, 53, #2, 84}] & @@@ l];
Print["edges: ", EdgeCount[g1], "  vertices:  ", VertexCount[g1]];
IsomorphicGraphQ[g1, g2]

(* edges: 52  vertices:  53 *)
(* \$Aborted *)

I would expect an execution time of milliseconds, while in reality it does not complete within minutes.

The above code works well for smaller examples with similar structure and IsomorphicGraph works with much larger graphs, as shown below (from the help file):

In[1]:= {g = GridGraph[{10, 10, 10}],h = Graph[RandomSample[VertexList[g], VertexCount[g]], EdgeList[g]]};

In[2]:= IsomorphicGraphQ[g, h] // Timing

Out[2]= {0.002527, True}

In[3]:= {VertexCount[g], EdgeCount[g]}

Out[3]= {1000, 2700}
• I don't know why it is so slow. I'd suggest to try Szabolcs' package "IGraphM"; it contains the method IGIsomorphicQ which immediately yields True on this problem. Commented Mar 21, 2019 at 6:08
• While the algorithm used by IGIsomoprhicQ by default (Bliss) is superior to what I believe Mathematica has (an old version of Nauty), it seems strange that IsomorphicGraphQ would do so badly on such a small tree. I would report this instance to Wolfram. Commented Mar 21, 2019 at 8:02
• All three algorithms currently included in IGraph/M, i.e. Bliss, VF2 and LAD, return very fast on this problem. Even VF2 is very fast despite being one of the less advanced algorithms. Finally, the graphs are very simple: they are symmetric directed trees. The vertices can be matched up very easily even manually, starting from the root. It smells like a bug to me ... Commented Mar 21, 2019 at 8:04

I believe this to be a bug. The graph is too simple, and g1 and g2 are not just isomorphic but completely identical, down to vertex and edge ordering.

Here is a much simpler example:

g = KaryTree[21, 4, DirectedEdges -> True]

Now IsomorphicGraphQ[g, g] does not complete.

Note: This has nothing to do with the well-known brokenness of the output of KaryTree (see e.g. how Graph3D[KaryTree[10], GraphStyle -> "BasicBlue"] does not evaluate) as we can verify by recreating the graph first by g=Uncompress@Compress[g].

IsomorphicGraphQ generally does very very badly on such symmetric directed trees, but not undirected ones.

CanonicalGraph is also affected. I believe IsomorphicGraphQ effectively works by canonicalizing both graphs then comparing them directly.

As Henrik said, the simplest workaround is to use IGraph/M

IGIsomorphicQ[g, g] // RepeatedTiming
(* {0.00020, True} *)

IGBlissCanonicalGraph[g]; // RepeatedTiming
(* {0.00038, Null} *)

The algorithm used by default by IGIsomorphicQ, Bliss, generally outperforms the one currently used by Mathematica (which I believe to be an old version of nauty based on the list of credits in Mathematica's About box). The drawback of using IGraph/M is that the graph needs to be converted to an igraph-compatible format before it can be processed, thus there is an overhead for each function call. For small and simple graphs, this overhead is far larger than the time to check isomorphism. Thus IGIsomorphicQ and IGBlissIsomorphicQ are usually worth using on graphs where IsomorphicGraphQ would take an appreciable amount of time. (Or, of course, graphs that IsomorphicGraphQ does not support such as multigraphs, coloured graphs, etc.)

• Thanks, this helps me a lot as I have a large amount of (large) graphs to match. I looked at the package and was able to get it to work immediately and noticed quite a few useful other algorithms. Commented Mar 22, 2019 at 0:48
• I have reported this to Wolfram. Commented Mar 24, 2019 at 7:23
• @Sander Did you get any response? Commented Apr 25, 2019 at 16:18
• Other than confirmation of receipt below: CASE:4237634 [...] It seems that the issue is not behaving properly. I have filed a issue report to our concerning developer in our team and have included your contact details as well. Thank you once again for bringing this issue into our notice and please do not hesitate to contact us if you have any further issues. Commented Apr 27, 2019 at 11:09