2
$\begingroup$

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism:

(1) Decision problem: Graph isomorphism. Instance: Graphs $G$ and $H$. Question: Is $G \cong H$?

(2) Decision problem: Nontrivial automorphism group. Instance: A graph $G$. Question: Is $Aut(G)>1$.

An article I'm reading ([P. J. Cameron, "Automorphisms of graphs,'' Chapter 5, Topics in Algebraic Graph Theory]) says that if we can solve (1), then we can solve (2) "by attaching distinctive `gadgets' at each vertex and checking whether any pair of the resulting graphs are isomorphic.''

For example, if $G$ is the 4-cycle graph on vertices $a,b,c,d$, then, we can attach the cycle graphs $C_5, C_6, C_7, C_8$ to $a,b,c,d$, respectively, to get a graph $G'$. We can attach $C_7, C_6, C_5, C_8$, to $a,b,c,d$, respectively, to get a graph $G''$. If $G' \cong G''$, then $(a,c)$ is an automorphism of $G$.

It seems to me that to solve (2) the number of pairs to check for isomorphism is superexponential and on the order of $n!$ at first thought, where $n$ is the number of vertices of $G$. Is it true that (2) does not have the same complexity as (1), at least given just this proof of attaching gadgets?

$\endgroup$
1
$\begingroup$

Take an "appropriate" gadget $X$ and for a vertex $v \in V(G)$, let $H_v$ be the graph you obtain by attaching $X$ at $v$.

A nontrivial automorphism of $G$ exists if and only if there are $u, v \in V(G)$ and $v \ne u$ with $H_v \cong H_u$. You need only run the isomorphism algorithm at most $O(|V(G)|^2)$ times to get your answer.

So, if the first problem is polynomial so is the second.

$\endgroup$
  • $\begingroup$ I agree with the "if" part of your statement but do not see why the "only if" should be true. It seems to me a nontrivial automorphism of $G$ can't be detected by your method of $|V|-1$ isomorphism tests if that initial vertex $v$ is an orbit of length 1 (under the action of $Aut(G)$ on $V(G)$). For example, take $G$ to be the path graph with edge set $\{12, 23, 34, 45, 46\}$ that has a unique nontrivial automorphism $(5,6)$, and take $v=1$. Attach some gadget $X$ to vertex v to obtain $H$. Then, $H_u$ will be nonisomorphic to $H$, for every $u \ne v$, but $Aut(G)>1$. $\endgroup$ – AG. Dec 14 '13 at 2:39
  • $\begingroup$ I guess you are right. But it is easy to fix though. $\endgroup$ – hbm Dec 14 '13 at 2:43
  • $\begingroup$ Yes, the permutation $(u,v,\ldots)\cdots$ is an automorphism of the graph iff there exists an isomorphism from $H_u$ to $H_v$. So, at most ${|V(G)| \choose 2}$ isomorphism tests should suffice to detect if the graph has a nontrivial automorphism. $\endgroup$ – AG. Dec 15 '13 at 6:37

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.