16

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

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
DurgaDatta
  • 1,281
  • 6
  • 18
  • 6
    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
  • 2
    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

1 Answers1

11

I believe all known GI-completeness results are functorial (definition in the paper), and Babai has recently shown (ITCS 2014, free author's copy) - based on bounds on the structure of automorphism groups of strongly regular graphs - that there is no functorial reduction from GI to strongly regular GI.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228