Fast uniform generation of regular graphs

An algorithm is presented which randomly selects a labelled graph with specified vertex degrees from a distribution which is arbitrarily close to uniform. The algorithm is based on simulation of a rapidly convergent stochastic process, and runs in polynomial time for a wide class of degree sequences, including all regular sequences and all n-vertex sequences with no degree exceeding √n/2. The algorithm can be extended to cover the selection of a graph with given degree sequence which avoids a specified set of edges. One consequence of this extension is the existence of a polynomial-time algorithm for selecting an f-factor in a sufficiently dense graph. A companion algorithm for counting degree-constrained graphs is also presented; this algorithm has exactly the same range of validity as the one for selection.

Authors

• Mark Jerrum
• Alistair Sinclair

Keywords

No keywords are indexed for this paper.