16
$\begingroup$

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

$\endgroup$
  • 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 Sun Sep 24 '12 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 Grochow Sep 27 '12 at 19:47
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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