Isomorphism-testing versus automorphism-finding (graphs)

Description

We are interested in establishing relationships between:

• Problems of testing whether two graphs are isomorphic (both arise from a restricted class of graphs)
• Problems of finding a nontrivial automorphism of a graph (subject to some further conditions)
• Problems of finding a generating set for the whole automorphism group of a graph

Here, we outline how we can relate these three problems for various classes of graphs.

Reducing isomorphism-testing to automorphism-finding

The problem is of this kind: we are given two graphs $X_{1}$ and $X_{2}$, both known to satisfy property $p$. We need to find a single graph $X$ such that knowing the automorphism group of $X$ can tell us whether $X_{1}$ and $X_{2}$ are isomorphic as graphs.

The simplest trick is to work with the disjoint union. This works if $X_{1}$ and $X_{2}$ are both connected graphs. The idea is as follows:

• Consider the graph $X$ obtained as the disjoint union of $X_{1}$ and $X_{2}$
• Find a generating set for the automorphism group of $X$
• Take any vertex $v\in V(X_{1})$. Then $X_{1}$ is isomorphic to $X_{2}$ if and only if there exists at least one element of the generating set taking $v$ to inside $V(X_{2})$.

The problem with this is at $X$ itself is no longer a connected graph. Thus, if we want to reduce the problem to the problem of determining an automorphism group of a connected graph, we need to do something more.

Reducing automorphism-finding to isomorphism-testing

Problem of finding an isomorphism acting in a certain way on a subset

The question: given two graphs, is there an isomorphism between them that acts in a certain way on a given subset? That is, can we have an automorphism that sends some of the vertices to fixed destinations (or some of the edges to fixed destinations)? In fact, this problem reduces to the graph isomorphism problem, by means of gadget attachment.

For making sure that vertex $v_{1}\in V(X_{1})$ goes to $v_{2}\in V(X_{2})$, attach a gadget to both $v_{1}$ and $v_{2}$ such that in the graph with the attached gadget:

• Any isomorphism between the new graphs must map $v_{1}$ to $v_{2}$
• Any isomorphism of the original graphs mapping $v_{1}$ to $v_{2}$ must lift uniquely to an isomorphism of the new graphs.

Finding a nontrivial graph automorphism

The idea is very similar to that of finding a satisfying assignment for a CNF formula given the ability to check circuit satisfiability. That is, we determine the isomorphism between the two graphs by means of a decision tree, where at each step, we choose where vertex $i$ of the graph $X_{1}$ goes, having decided where the previous vertices go.

Suppose we have fixed where vertices $1,2,3,\ldots (i-1)$ go, say the images are $12',2',\ldots ,(i-1)'$. Then, we need to find where $i$ could go. For every $j\in V(X)$, check if there is a graph isomorphism between $X$ and $X$ which sends $1$ to $1'$, $2$ to $2'$, and so on, and send $i$ to $j$. We are guaranteed that we will find such a $j$ because there does exist an isomorphism.

Having located such a $j$, fix $j$ as $i'$ and proceed.

Finding a generating set for the automorphism group

Here, instead of finding just one nontrivial graph automorphism, we need to find enough that generate the whole group. The idea is to use the Sims filter trimming concept even as we are constructing the generating set. That is:

• First, for each $j$, we find one automorphism each that sends $1$ to $j$.
• Henceforth, all automorphisms in the generating set must send $1$ to $1$. Try, for every $j>1$, whether there is an automorphism sending 1 to 1 and 2 to $j$.
• Keep proceeding like this. We'll get a generating set with at most $n^{2}$ elements.