patternMinor
Graph isomorphism and the automorphism group
Viewed 0 times
thegraphgroupautomorphismandisomorphism
Problem
A common approach to decide whether two given graphs are isomorphic is to compute the so-called canonical label (alternatively, canonical graph) of each graph and to check whether those match or not.
Tools such as Nauty compute the canonical graph via search trees that are pruned using some clever ideas that rely, among other, on graph automorphisms. Because of this, Nauty allows one to compute a generator of the graph automorphism group. However, as far as I understood the idea behind Nauty, the computation of the canonical graph does not require one to compute a generator of the graph automorphism group in general.
My question is therefore: is there a formal complexity-theoretical relation between GI and the computation of a generator set of the graph automorphism group?
Many thanks.
Tools such as Nauty compute the canonical graph via search trees that are pruned using some clever ideas that rely, among other, on graph automorphisms. Because of this, Nauty allows one to compute a generator of the graph automorphism group. However, as far as I understood the idea behind Nauty, the computation of the canonical graph does not require one to compute a generator of the graph automorphism group in general.
My question is therefore: is there a formal complexity-theoretical relation between GI and the computation of a generator set of the graph automorphism group?
Many thanks.
Solution
As the comments suggest there can be confusion over what you call "GI". But the idea here is correct. It is polynomial-time equivalent to find generators of an automorphism group as it is to find an isomorphism between two groups. The idea is "classical" in that it appears in early work such as Luks' Group Isomorphism in bounded valence is in polynomial-time, and even there I think the idea was considered "well-known".
Claim. Let $G$ and $H$ be connected graphs. Then $G\cong H$ if, and only if, every generating set $S$ of $\mathrm{Aut}(G\sqcup H)$ contains an element $g\in S$ such that $G^g=H$.
Remark Important here is that every generating set exchange the graphs as otherwise you would sometimes compute generators that don't solve the problem. So for example, isomorphism of two groups does not so easily yield in this way. That is because not all generating sets of $\mathrm{Aut}(G\times H)$ will interchange $G$ and $H$ when $G\cong H$. instead they can go to diagonal copies. That situation can be fixed, but it requires a stronger argument. So the approach here is not one that applies in all categories.
Proof. For the converse if every (or even if one) generating set of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$ then $G\cong H$ by the restriction of that function to $G$. So this is all about the forward direction. (But I mention this because the proof is by contrapositive so it can look like I'm about to go the same direction.)
Suppose $\mathrm{Aut}(G\sqcup H)$ is generated by a set $S$ all of whose elements send $G$ to $G$, and $H$ to $H$, (note by connectivity assumption if one vertex of $G$ is sent to one vertex of $H$ then the entire graph $G$ is sent to $H$ and so by pigeon hole some vertex in $H$ will be sent to $G$ and so $|G|=|H|$ and we will have interchanged the two graphs). Since $S$ sends $G$ to $G$, then every composition of functions in $S$ sends $G$ to $G$, and so do inverses of these functions. So every word in $S$ sends $G$ to $G$ (and also $H$ to $H$). So no element of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$.
Finally if $G\cong H$ then an isomorphism $\phi:G\to H$ affords an automorphism $\phi\sqcup \phi^{-1}$ of $G\sqcup H$. So the absence of elements in $\mathrm{Aut}(G\sqcup H)$ to interchange $G$ and $H$ implies $G\not\cong H$. The result follows. $\Box$
But now the point to be clear on is that going from decision (Is $G\cong H$?) to search (Give me $\phi:G\to H$ or a certificate that $G\not\cong H$) has still to be argued (and can be). Also from one isomorphism to generators of automorphisms is another argument (individualize the graphs and repeat the isomorphism test). So all told you have a couple pages of argument to make these equivalences. None will show canonical labeling though. That is much harder (NP-hard if I recall). Even though NAutY and Traces handle many examples quickly.
Claim. Let $G$ and $H$ be connected graphs. Then $G\cong H$ if, and only if, every generating set $S$ of $\mathrm{Aut}(G\sqcup H)$ contains an element $g\in S$ such that $G^g=H$.
Remark Important here is that every generating set exchange the graphs as otherwise you would sometimes compute generators that don't solve the problem. So for example, isomorphism of two groups does not so easily yield in this way. That is because not all generating sets of $\mathrm{Aut}(G\times H)$ will interchange $G$ and $H$ when $G\cong H$. instead they can go to diagonal copies. That situation can be fixed, but it requires a stronger argument. So the approach here is not one that applies in all categories.
Proof. For the converse if every (or even if one) generating set of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$ then $G\cong H$ by the restriction of that function to $G$. So this is all about the forward direction. (But I mention this because the proof is by contrapositive so it can look like I'm about to go the same direction.)
Suppose $\mathrm{Aut}(G\sqcup H)$ is generated by a set $S$ all of whose elements send $G$ to $G$, and $H$ to $H$, (note by connectivity assumption if one vertex of $G$ is sent to one vertex of $H$ then the entire graph $G$ is sent to $H$ and so by pigeon hole some vertex in $H$ will be sent to $G$ and so $|G|=|H|$ and we will have interchanged the two graphs). Since $S$ sends $G$ to $G$, then every composition of functions in $S$ sends $G$ to $G$, and so do inverses of these functions. So every word in $S$ sends $G$ to $G$ (and also $H$ to $H$). So no element of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$.
Finally if $G\cong H$ then an isomorphism $\phi:G\to H$ affords an automorphism $\phi\sqcup \phi^{-1}$ of $G\sqcup H$. So the absence of elements in $\mathrm{Aut}(G\sqcup H)$ to interchange $G$ and $H$ implies $G\not\cong H$. The result follows. $\Box$
But now the point to be clear on is that going from decision (Is $G\cong H$?) to search (Give me $\phi:G\to H$ or a certificate that $G\not\cong H$) has still to be argued (and can be). Also from one isomorphism to generators of automorphisms is another argument (individualize the graphs and repeat the isomorphism test). So all told you have a couple pages of argument to make these equivalences. None will show canonical labeling though. That is much harder (NP-hard if I recall). Even though NAutY and Traces handle many examples quickly.
Context
StackExchange Computer Science Q#91736, answer score: 3
Revisions (0)
No revisions yet.