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.
$\begingroup$
$\endgroup$
5
asked Aug 26, 2010 at 15:24
-
$\begingroup$ 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. $\endgroup$– Suresh VenkatAug 26, 2010 at 15:53
-
$\begingroup$ I need an algorithm that generate random graph with no non-trivial automorphism. $\endgroup$– Mohammad Al-TurkistanyAug 26, 2010 at 17:00
-
$\begingroup$ Please edit that definition of asymmetry into your question. $\endgroup$– AryabhataAug 26, 2010 at 17:14
-
$\begingroup$ yes, because asymmetric doesn't mean what you intend. Your comment is more precise, and that's an interesting question. $\endgroup$– Suresh VenkatAug 26, 2010 at 17:18
-
2$\begingroup$ A better title would be "Can we sample from the set of graphs with no nontrivial automorphism" $\endgroup$– Suresh VenkatAug 26, 2010 at 17:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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).
-
$\begingroup$ What is the complexity of your algorithm? I can't deduce it from this algorithm. $\endgroup$ Aug 26, 2010 at 20:06
-
1$\begingroup$ 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? $\endgroup$ Aug 26, 2010 at 20:35
-
4$\begingroup$ Not only is it quick in practice (see 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) doi.ieeecomputersociety.org/10.1109/SFCS.1979.8 $\endgroup$ Aug 26, 2010 at 23:26
-
$\begingroup$ It seems plausible that determining if a graph has trivial automorphism group is at least as hard as Graph Isomorphism. $\endgroup$– EmilAug 27, 2010 at 0:54
-
1$\begingroup$ 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! $\endgroup$ Aug 27, 2010 at 15:18