<p>Almost all graphs have trivial automorphism group. So all you need to do is generate a graph uniformly at random (see e.g. <a href="http://en.wikipedia.org/wiki/Random_graph" rel="nofollow">http://en.wikipedia.org/wiki/Random_graph</a>), then compute its automorphism group (or just determine its order). Repeat until you find a graph with trivial automorphism group (also called a rigid graph).</p>

CC BY-SA 2.5
2010-08-26T20:06:35.127Z
What is the complexity of your algorithm? I can't deduce it from this algorithm.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-26T20:35:51.693Z
Given that almost all graphs have a trivial automorphism group, this procedure seems to be dominated by the part that computes the automorphism group.  This is not known to be in P, although it may be quick in practice.  Emil, could you say more?
András Salamon
CC BY-SA 2.5
2010-08-26T23:26:22.427Z
Not only is it quick in practice (see http://cs.anu.edu.au/~bdm/nauty/ for the program and link to the paper), but it can be done on a random graph in average-case linear time (Babai and Kucera, FOCS 1979) http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.8
Joshua Grochow
CC BY-SA 2.5
2010-08-27T00:54:11.130Z
It seems plausible that determining if a graph has trivial automorphism group is at least as hard as Graph Isomorphism.
Emil
CC BY-SA 2.5
2010-08-27T15:18:11.823Z
Although it is indeed plausible that determining if a graph has trivial automorphism group is as hard as Graph Isomorphism (it cannot be harder, since there is already a reduction in one direction), showing it has been an open problem for decades!
Joshua Grochow
CC BY-SA 2.5
2010-08-26T19:51:50.390Z
2010-08-26T19:51:50.390Z
Emil
<p>Let us call a graph "asymmetric" if it has no nontrivial automorphism group. <a href="http://en.wikipedia.org/wiki/Asymmetric_graph" rel="nofollow">http://en.wikipedia.org/wiki/Asymmetric_graph</a>
<a href="http://en.wikipedia.org/wiki/Asymmetric_graph" rel="nofollow"></a>
<a href="http://en.wikipedia.org/wiki/Asymmetric_graph" rel="nofollow"></a></p>

<p>I'm looking for an efficient way to compute a random asymmetric graph on a given number of nodes.</p>

CC BY-SA 2.5
2010-08-26T15:53:42.610Z
you mean a directed graph ? Is your question about generating a random digraph ? If so, merely generate a random undirected graph and direct each edge with a coin toss.
Suresh Venkat
CC BY-SA 2.5
2010-08-26T17:00:04.357Z
I need an algorithm that generate random graph with no non-trivial automorphism.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-26T17:14:32.437Z
Please edit that definition of asymmetry into your question.
Aryabhata
CC BY-SA 2.5
2010-08-26T17:18:49.983Z
yes, because asymmetric doesn't mean what you intend. Your comment is more precise, and that's an interesting question.
Suresh Venkat
CC BY-SA 2.5
2010-08-26T17:59:31.947Z
A better title would be "Can we sample from the set of graphs with no nontrivial automorphism"
Suresh Venkat
<cc.complexity-theory><ds.algorithms><graph-theory><automorphism>
What is the most efficient algorithm to sample graphs with trivial automorphism groups ?
Mohammad Al-Turkistany
# What is the most efficient algorithm to sample graphs with trivial automorphism groups ?

(Asked by: username_0 on 2010-08-26)

Let us call a graph "asymmetric" if it has no nontrivial automorphism group. <http://en.wikipedia.org/wiki/Asymmetric_graph>

I'm looking for an efficient way to compute a random asymmetric graph on a given number of nodes.

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, automorphism

> **Comments:**
> **username_1**: you mean a directed graph ? Is your question about generating a random digraph ? If so, merely generate a random undirected graph and direct each edge with a coin toss.  
> **username_0**: I need an algorithm that generate random graph with no non-trivial automorphism.  
> **username_2**: Please edit that definition of asymmetry into your question.  
> **username_1**: yes, because asymmetric doesn't mean what you intend. Your comment is more precise, and that's an interesting question.  
> **username_1**: A better title would be "Can we sample from the set of graphs with no nontrivial automorphism"  

---

## 1 answers

### Answer by username_3 on 2010-08-26. Score: 3

Almost all graphs have trivial automorphism group. So all you need to do is generate a graph uniformly at random (see e.g. <http://en.wikipedia.org/wiki/Random_graph>), then compute its automorphism group (or just determine its order). Repeat until you find a graph with trivial automorphism group (also called a rigid graph).

> **Comments:**
> **username_0**: What is the complexity of your algorithm? I can't deduce it from this algorithm.  
> **username_4**: Given that almost all graphs have a trivial automorphism group, this procedure seems to be dominated by the part that computes the automorphism group.  This is not known to be in P, although it may be quick in practice.  username_3, could you say more?  
> **username_5**: Not only is it quick in practice (see http://cs.anu.edu.au/~bdm/nauty/ for the program and link to the paper), but it can be done on a random graph in average-case linear time (Babai and Kucera, FOCS 1979) http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.8  
> **username_3**: It seems plausible that determining if a graph has trivial automorphism group is at least as hard as Graph Isomorphism.  
> **username_5**: Although it is indeed plausible that determining if a graph has trivial automorphism group is as hard as Graph Isomorphism (it cannot be harder, since there is already a reduction in one direction), showing it has been an open problem for decades!  

---

