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).
$\begingroup$
$\endgroup$
2
-
6$\begingroup$ 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) $\endgroup$– Timothy SunSep 24, 2012 at 10:01
-
2$\begingroup$ 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). $\endgroup$– Joshua GrochowSep 27, 2012 at 19:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Oct 7, 2014 at 19:49