# Strongly Regular Graph and GI-Completeness

It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (Similar to the belief that GI may not be NP-Complete).

• I personally believe that the problem is strictly easier than GI, because of Spielman's algorithm for SRGs, which has a smaller exponent than the one by Luks for general graphs. There just seems like there's so much more structure! (which ultimately might mean nothing) – Timothy Sun Sep 24 '12 at 10:01
• While I tend to agree with @TimothySun, I don't really know formal reasons to think that SRGI is strictly easier than GI. E.g., if there is a $O(n)$ reduction from GI to SRGI then that would yield a better algorithm for GI than currently known, but if the reduction blows up the number of vertices even to $O(n^{3/2})$ then it would not have that surprising consequence. As to your 2nd q., I doubt there are any complexity consequences of any problem (known to reduce to GI) being GI-complete, since it's so unrelated to most other complexity classes (unlike the fact that GI being NPC collapses PH). – Joshua Grochow Sep 27 '12 at 19:47