<p>Upon request of Marzio De Biasi I'm converting my comment into an answer.</p>

<p>A graph is asymmetric (some authors refer to it as rigid) if it has a unique automorphism, i.e., the identity. As pointed out by Chad Brewbacker, most graphs are asymmetric. However the following two questions are open:</p>

<p>1) Is isomorphism of asymmetric graphs in P? </p>

<p>2) Can isomorphism of general graphs be reduced to isomorphism of asymmetric graphs?</p>

<p>Question 1) has received a lot of attention in quantum computing due to the fact that the isomorphism of asymetric graphs can be reduced to the <a href="http://arxiv.org/abs/quant-ph/0511148">nonabelian hidden subgroup problem</a>  and to the <a href="http://arxiv.org/abs/quant-ph/0510185">non abelian hidden shift problem</a>. However the results are negative, showing that one needs to prepare at least $\Omega(n\log n)$ hidden subgroup states or hidden shift states to have enough information to solve the isomorphism problem. </p>

CC BY-SA 3.0
2014-04-13T17:51:26.730Z
2014-04-13T20:42:39.340Z
2014-04-13T20:42:39.340Z
Mateus de Oliveira Oliveira
<p>While reading the question <a href="https://cstheory.stackexchange.com/q/22093/3247">Examples where the uniqueness of the solution makes it easier to find</a>, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) problem is in $P$.</p>

<blockquote>
But what happens if we assume that both $G_1$ and $G_2$ are asymmetric (i.e. both have only the trivial (identity) automorphism) ? Does the problem become easier (polynomial time)? 
</blockquote>

<p>Note: the problem cannot be harder than Graph Automorphism ($GA$), because there is a quick reduction: just use $GA$ on $G_1 \cup G_2$, if the answer is yes then the two graphs are isomorphic (see also Johannes Köbler, Uwe Schöning, Jacobo Torán: <a href="http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/gi-low.pdf" rel="nofollow noreferrer">Graph Isomorphism is Low for PP</a>. 401-411).</p>

CC BY-SA 3.0
2014-04-13T00:31:26.637Z
With probability approaching 1 as n grows, your graph has only the trival automorphoism by Kolmogorov complexity.
Chad Brewbaker
CC BY-SA 3.0
2014-04-13T07:52:52.807Z
+1 Nice question, your question potentially leads to an attack on P vs NP. Try to prove that no Turing reduction exist from $GA$ to your problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-04-13T14:53:06.717Z
This problem is known as the rigid graph isomorphism problem. If it can be solved in polynomial time or not is widely open. There is some work trying to attack it via quantum algorithms, for instance, by reducing it to the hidden shift problem ( http://arxiv.org/abs/quant-ph/0510185) but the results are mostly negative showing that the tried techniques don't work.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2014-04-13T15:34:58.937Z
@MateusdeOliveiraOliveira: thanks! you can convert your comment to an answer ... if nobody gives more insights I'll accept it in a few days.
Marzio De Biasi
CC BY-SA 3.0
2014-04-13T16:09:56.700Z
It is possible to rigidify any graph so that it has only a single endomorphism (and hence automorphism), by attaching mutually rigid graphs to each vertex.  This implies a Turing reduction from GI to deciding isomorphism of asymmetric graphs.  Alas, it is not polynomial.
András Salamon
CC BY-SA 3.0
2014-04-13T16:20:28.717Z
It is unfortunate that Childs/Wocjan used "rigid" to mean "asymmetric" when "rigid" has a long usage as "has only the trivial endomorphism".
András Salamon
CC BY-SA 3.0
2014-04-13T17:59:43.890Z
Well Childs/Wocjan are not alone in using rigid to denote graphs with a single automorphism. There is a survey from Babai from 1994 that already poits that the terminology is not that standard www.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf‎ . Also in modern times it rigid has been used in this sense by Jacobo Toran (https://www.uni-ulm.de/fileadmin/website_uni_ulm/.../toran/hard.pdf‎). So it seems that is a matter of whether the author cares about embeddings or not. But I used asymmetric in my answer to avoid confusion.
Mateus de Oliveira Oliveira
<reference-request><graph-isomorphism>
Testing isomorphism of asymmetric graphs
Marzio De Biasi
# Testing isomorphism of asymmetric graphs

(Asked by: username_0 on 2014-04-12)

While reading the question [Examples where the uniqueness of the solution makes it easier to find](https://cstheory.stackexchange.com/q/22093/3247), a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) problem is in $P$.

> But what happens if we assume that both $G\_1$ and $G\_2$ are asymmetric (i.e. both have only the trivial (identity) automorphism) ? Does the problem become easier (polynomial time)?

Note: the problem cannot be harder than Graph Automorphism ($GA$), because there is a quick reduction: just use $GA$ on $G\_1 \cup G\_2$, if the answer is yes then the two graphs are isomorphic (see also Johannes Köbler, Uwe Schöning, Jacobo Torán: [Graph Isomorphism is Low for PP](http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/gi-low.pdf). 401-411).

**Tags:** reference-request, graph-isomorphism
> **Comments:**
> **username_1**: With probability approaching 1 as n grows, your graph has only the trival automorphoism by Kolmogorov complexity.  
> **username_2**: +1 Nice question, your question potentially leads to an attack on P vs NP. Try to prove that no Turing reduction exist from $GA$ to your problem.  
> **username_3**: This problem is known as the rigid graph isomorphism problem. If it can be solved in polynomial time or not is widely open. There is some work trying to attack it via quantum algorithms, for instance, by reducing it to the hidden shift problem ( http://arxiv.org/abs/quant-ph/0510185) but the results are mostly negative showing that the tried techniques don't work.  
> **username_0**: @MateusdeOliveiraOliveira: thanks! you can convert your comment to an answer ... if nobody gives more insights I'll accept it in a few days.  
> **username_4**: It is possible to rigidify any graph so that it has only a single endomorphism (and hence automorphism), by attaching mutually rigid graphs to each vertex.  This implies a Turing reduction from GI to deciding isomorphism of asymmetric graphs.  Alas, it is not polynomial.  
> **username_4**: It is unfortunate that Childs/Wocjan used "rigid" to mean "asymmetric" when "rigid" has a long usage as "has only the trivial endomorphism".  
> **username_3**: Well Childs/Wocjan are not alone in using rigid to denote graphs with a single automorphism. There is a survey from Babai from 1994 that already poits that the terminology is not that standard www.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf‎ . Also in modern times it rigid has been used in this sense by Jacobo Toran (https://www.uni-ulm.de/fileadmin/website_uni_ulm/.../toran/hard.pdf‎). So it seems that is a matter of whether the author cares about embeddings or not. But I used asymmetric in my answer to avoid confusion.  

---

## 1 answers

### Answer by username_3 on 2014-04-13. Score: 11 | Accepted answer

Upon request of Marzio De Biasi I'm converting my comment into an answer.

A graph is asymmetric (some authors refer to it as rigid) if it has a unique automorphism, i.e., the identity. As pointed out by Chad Brewbacker, most graphs are asymmetric. However the following two questions are open:

1) Is isomorphism of asymmetric graphs in P?

2) Can isomorphism of general graphs be reduced to isomorphism of asymmetric graphs?

Question 1) has received a lot of attention in quantum computing due to the fact that the isomorphism of asymetric graphs can be reduced to the [nonabelian hidden subgroup problem](http://arxiv.org/abs/quant-ph/0511148) and to the [non abelian hidden shift problem](http://arxiv.org/abs/quant-ph/0510185). However the results are negative, showing that one needs to prepare at least $\Omega(n\log n)$ hidden subgroup states or hidden shift states to have enough information to solve the isomorphism problem.


---

