<p>I believe all known GI-completeness results are <em>functorial</em> (definition in the paper), and Babai has recently shown (<a href="https://doi.org/10.1145/2554797.2554830" rel="nofollow noreferrer">ITCS 2014</a>, <a href="http://people.cs.uchicago.edu/~laci/papers/14itcs.pdf" rel="nofollow noreferrer">free author's copy</a>) - 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.</p>

CC BY-SA 4.0
2014-10-07T19:49:31.767Z
2024-07-22T16:38:25.433Z
2024-07-22T16:38:25.433Z
Joshua Grochow
<p>It is not known if graph isomorphism (GI) for <a href="http://en.wikipedia.org/wiki/Strongly_regular_graph">strongly regular graphs</a> (SRGs) is in <strong>P</strong>. Are there any hints that it might or might not be <strong>GI</strong>-Complete? Are there any strong consequences in such cases? (Similar to the <em>belief</em> that GI may not be NP-Complete).</p>

CC BY-SA 3.0
2012-09-24T10:01:52.600Z
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
CC BY-SA 3.0
2012-09-27T19:47:44.683Z
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
<cc.complexity-theory><graph-theory><graph-algorithms><graph-isomorphism><structural-complexity>
Strongly Regular Graph and GI-Completeness
DurgaDatta
# Strongly Regular Graph and GI-Completeness

(Asked by: username_0 on 2012-09-24)

It is not known if graph isomorphism (GI) for [strongly regular graphs](http://en.wikipedia.org/wiki/Strongly_regular_graph) (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).

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, graph-isomorphism, structural-complexity
> **Comments:**
> **username_1**: 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)  
> **username_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).  

---

## 1 answers

### Answer by username_2 on 2014-10-07. Score: 11

I believe all known GI-completeness results are *functorial* (definition in the paper), and Babai has recently shown ([ITCS 2014](https://doi.org/10.1145/2554797.2554830), [free author's copy](http://people.cs.uchicago.edu/~laci/papers/14itcs.pdf)) - 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.


---

