2
$\begingroup$

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.

$\endgroup$
  • $\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 Venkat Aug 26 '10 at 15:53
  • $\begingroup$ I need an algorithm that generate random graph with no non-trivial automorphism. $\endgroup$ – Mohammad Al-Turkistany Aug 26 '10 at 17:00
  • $\begingroup$ Please edit that definition of asymmetry into your question. $\endgroup$ – Aryabhata Aug 26 '10 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 Venkat Aug 26 '10 at 17:18
  • 2
    $\begingroup$ A better title would be "Can we sample from the set of graphs with no nontrivial automorphism" $\endgroup$ – Suresh Venkat Aug 26 '10 at 17:59
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ What is the complexity of your algorithm? I can't deduce it from this algorithm. $\endgroup$ – Mohammad Al-Turkistany Aug 26 '10 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$ – András Salamon Aug 26 '10 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$ – Joshua Grochow Aug 26 '10 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$ – Emil Aug 27 '10 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$ – Joshua Grochow Aug 27 '10 at 15:18

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.