Generating r-Regular Random Graph in Parallel

Question

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!

Answer 1

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

Answer 2

The Wormald method (alluded to in @Daniel's answer) is an application of the "configuration model" introduced by Bollobas (look in his "Random Graphs") It does not work (not in finite time) for graphs of degree greater than around 4. There has been more recent work on this by Kim and Vu (see http://dl.acm.org/citation.cfm?id=780576, there is presumably an arxiv version also), but be forewarned that it is of more theoretical than practical value (it is not clear how large a graph needs to be before the distribution is "close enough" to uniform). Interestingly, while the Wormald algorithm is morally parallel (you generate a configuration at once, then throw it out if it is not a simple graph), the algorithm Kim/Vu analyze (the algorithm is not due to them, and goes back to the ancients, the analysis is theirs) does it one vertex at a time, so "parallelism" is quite expensive, to get back to the OP's original question.