# Generating r-Regular Random Graph in Parallel

Goal:

I want to generate a r-regular graph with n vertices. rn = 2m.

Current best:

(1) take n vertices; randomly pick a vertex v of degree < r.
(2) S = set of all vertices of degree < r, and not a neighbor of v.
(3) create an edge between v and a random element of S.
(4) repeat.


Question:

Is there a more parallel way to do this?

Clarification:

Suppose I wanted to randomly pick an element in [1...n]. I could do it sequentially like:

take 1 w/ prob 1/n
else take 2 w/ prob 1/n-1
else take 3 w/ prob 1/n-2
...


Or I could do it "one shot" by generating a random element between [1...n].

Similarly, I want to generate a r-regular graph "one shot" rather than an single edge at a time.

Goal:

This is to build mental intuition of what it means to "uniformly pick a r-regular graph."

Thanks!

-
What sorts of random entities are available? Specifically, can you generate a random permutation? Part of my reason for asking is that the special case $r=2$ of your question is pretty close to asking for a random permutation. Another part is that conversely, for general $r$, by thinking of each vertex as having $r$ half-edges already attached, your problem becomes one of pairing up these half-edges, which looks similar to finding a random permutation of the set of half-edges (though you'd have to do something to avoid loops and multiple edges). –  Andreas Blass Aug 26 '11 at 3:43

This question is more difficult that it seems.

Firstly, there is a difference between picking edges of a graph uniformly, and picking a $r$-regular graph uniformly.

Let $G_{r,n}$ be the set of $r$-regular graphs on $n$ nodes. By "uniformly pick a $r$-regular graph", you need to create an algorithm that chooses $G \in G_{r,n}$ with probability $1/|G_{r,n}|$. There are probabilistic methods to do this, perhaps they even lend themselves to parallelization.

See the section on algorithms for generation of random regular graphs here. In particular,B. McKay and N. Wormald, Uniform Generation of Random Regular Graphs of Moderate Degree, Journal of Algorithms, Vol. 11 (1990), pp 52-67

-