8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ We can determine if $G$ and $H$ are isomorphic via the automorphism group of $G \cup H$. Going the other way, I'm not sure---perhaps there's a simple way to canonically label a graph given its automorphism group. $\endgroup$ – Rebecca J. Stones Jul 26 '18 at 13:30
  • $\begingroup$ @RebeccaJ.Stones, is that the same question, though? Unless Wikipedia is out of date, it's not known whether graph isomorphism and graph canonicalisation are polynomial-time equivalent, so I don't think that an algorithm to canonically label a graph from the automorphism group would tell you anything useful about the relationship between computing the group and GI. $\endgroup$ – Peter Taylor Jul 26 '18 at 14:01
2
$\begingroup$

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.

$\endgroup$

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.