Generating random regular graphs

ABSTRACT

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [9] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d=O(n^1/3-ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd²). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author.Besides being perhaps the only algorithm which works for relatively large d in practical time, our result also has a significant theoretical value, as it can be used to derive many properties of uniform random regular graphs.

REFERENCES

• 1: B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1 (1980), no. 4, 311--316.
• 2: E. Bender and R. Canfield, The asymptotic number of labeled graphs with given degree sequences, J. Combinatorial Theory Ser. A 24 (1978), no. 3, 296--307.
• 3: J. Friedman, A proof of Alon's second eigenvalue conjecture, preprint.
• 4: M. Jerrum , A. Sinclair, Fast uniform generation of regular graphs, Theoretical Computer Science, v.73 n.1, p.91-100, June 1990 [doi>10.1016/0304-3975(90)90164-D]
• 5: J. H. Kim and V. H. Vu, Concentration of multivariate polynomials and its applications, Combinatorica 20 (2000), no. 3, 417--434.
• 6: J. H. Kim and V. H. Vu, Sandwitching random graphs, submitted.
• 7: B. McKay and N. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2), Combinatorica 11 (1991), no. 4, 369--382.
• 8: A. Rucinski and N. Wormald, Random graph processes with degree restrictions, Combin. Probab. Comput. 1 (1992), no. 2, 169--180.
• 9: A. Steger , N. C. Wormald, Generating Random Regular Graphs Quickly, Combinatorics, Probability and Computing, v.8 n.4, p.377-396, July 1999 [doi>10.1017/S0963548399003867]
• 10: V. H. Vu, Concentration of non-Lipschitz functions and applications, Random Structures & Algorithms, v.20 n.3, p.262-316, May 2002 [doi>10.1002/rsa.10032]
• 11: N. Wormald, Models of random regular graphs. Surveys in combinatorics, 1999 (Canterbury), 239--298, London Math. Soc. Lecture Note Ser., 267, Cambridge Univ. Press, Cambridge, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms

Keywords:
concentration, configuration model, inequality, random regular graph