Graph automorphism

[1][2] Constructing the automorphism group of a graph, in the form of a list of generators, is polynomial-time equivalent to the graph isomorphism problem, and therefore solvable in quasi-polynomial time, that is with running time

[5][8] While no worst-case polynomial-time algorithms are known for the general Graph Automorphism problem, finding the automorphism group (and printing out an irredundant set of generators) for many large graphs arising in applications is rather easy.

Several open-source software tools are available for this task, including NAUTY,[9] BLISS[10] and SAUCY.

However, BLISS and NAUTY can also produce Canonical Labeling, whereas SAUCY is currently optimized for solving Graph Automorphism.

An important observation is that for a graph on n vertices, the automorphism group can be specified by no more than

It also appears that the total support (i.e., the number of vertices moved) of all generators is limited by a linear function of n, which is important in runtime analysis of these algorithms.

Practical applications of Graph Automorphism include graph drawing and other visualization tasks, solving structured instances of Boolean Satisfiability arising in the context of Formal verification and Logistics.