<p>Finding the generators of the automorphism group of a graph is in fact GI-complete (under poly-time Turing reductions) - goes back to <a href="https://doi.org/10.1016/0020-0190(79)90004-8" rel="nofollow noreferrer">Mathon '79</a> and the proof is not hard.</p>
<p>Canonization is not known to be equivalent to deciding isomorphism, but in many cases isomorphism algorithms have been upgraded to canonization using similar techniques as the isomorphism algorithm. (For more on the relationship between deciding equivalence vs computing a canonical form, see: <a href="https://cstheory.stackexchange.com/q/9341/129">What is the most efficient algorithm for deciding if an element is the least in its orbit?</a> and <a href="https://cstheory.stackexchange.com/q/10702/129">Example where equivalence is easy but finding class representative is hard</a>.)</p>

CC BY-SA 4.0
2024-07-23T16:29:40.930Z
Thanks for another fantastic answer, Joshua! (: So GI-completeness implies that Babai's 2016 GI algorithm allows us to find the generators of a graph's automorphism group in quasi-polynomial time (+ the same for the graph automorphism problem)?
Julius Kunze
CC BY-SA 4.0
2024-07-23T16:30:50.380Z
Yes. (It does not give you canonization, but Babai had a follow-up paper in STOC the following year (IIRC) where he upgraded his algorithm to a canonization algorithm.)
Joshua Grochow
CC BY-SA 4.0
2024-07-23T16:44:42.773Z
Wow. In that case, it looks like the wiki articles on [graph automorphisms](https://en.wikipedia.org/wiki/Graph_automorphism) and [canonization](https://en.wikipedia.org/wiki/Graph_canonization) are seriously outdated.
Julius Kunze
CC BY-SA 4.0
2024-07-23T17:08:46.747Z
Found your reference: [Canonical Form for Graphs in Quasipolynomial Time](https://par.nsf.gov/servlets/purl/10179675). Babai seems to like keeping things "preliminary". (:
Julius Kunze
CC BY-SA 4.0
2024-07-23T15:34:25.800Z
2024-07-23T15:34:25.800Z
Joshua Grochow
<p>Given a generating set for the automorphism group of a graph, can we efficiently find a canonical labeling? What about the other way around?</p>
<p>Both problems of finding a graph automorphism group and graph canonization are GI-hard. Can we reduce one of the two to the other, and if so at what complexity?</p>
<p>For context: The <code>nauty</code> and <code>bliss</code> libraries can heuristically solve both simultaneously, while <code>saucy</code> solves the former but not canonization.</p>

<complexity-classes><gr.group-theory>
Complexity of finding graph automorphism group vs. canonization
Julius Kunze
# Complexity of finding graph automorphism group vs. canonization

(Asked by: username_0 on 2024-07-23)

Given a generating set for the automorphism group of a graph, can we efficiently find a canonical labeling? What about the other way around?

Both problems of finding a graph automorphism group and graph canonization are GI-hard. Can we reduce one of the two to the other, and if so at what complexity?

For context: The `nauty` and `bliss` libraries can heuristically solve both simultaneously, while `saucy` solves the former but not canonization.

**Tags:** complexity-classes, gr.group-theory


---

## 1 answers

### Answer by username_1 on 2024-07-23. Score: 4 | Accepted answer

Finding the generators of the automorphism group of a graph is in fact GI-complete (under poly-time Turing reductions) - goes back to [Mathon '79](https://doi.org/10.1016/0020-0190(79)90004-8) and the proof is not hard.

Canonization is not known to be equivalent to deciding isomorphism, but in many cases isomorphism algorithms have been upgraded to canonization using similar techniques as the isomorphism algorithm. (For more on the relationship between deciding equivalence vs computing a canonical form, see: [What is the most efficient algorithm for deciding if an element is the least in its orbit?](https://cstheory.stackexchange.com/q/9341/129) and [Example where equivalence is easy but finding class representative is hard](https://cstheory.stackexchange.com/q/10702/129).)

> **Comments:**
> **username_0**: Thanks for another fantastic answer, Joshua! (: So GI-completeness implies that Babai's 2016 GI algorithm allows us to find the generators of a graph's automorphism group in quasi-polynomial time (+ the same for the graph automorphism problem)?  
> **username_1**: Yes. (It does not give you canonization, but Babai had a follow-up paper in STOC the following year (IIRC) where he upgraded his algorithm to a canonization algorithm.)  
> **username_0**: Wow. In that case, it looks like the wiki articles on [graph automorphisms](https://en.wikipedia.org/wiki/Graph_automorphism) and [canonization](https://en.wikipedia.org/wiki/Graph_canonization) are seriously outdated.  
> **username_0**: Found your reference: [Canonical Form for Graphs in Quasipolynomial Time](https://par.nsf.gov/servlets/purl/10179675). Babai seems to like keeping things "preliminary". (:  

---

