Uniform generation of random regular graphs

2015/11/04 by Pu Gao, Gao, Pu, Nicholas Wormald +1
Computer Science · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1511.01175

openalex publication_date 2015/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for d-regular graphs. REG can be implemented such that each graph is generated in expected time O(nd³), provided that d=o(n^1/2). Our result significantly improves the previously best uniform sampler, which works efficiently only when d=O(n^1/3), with essentially the same running time for the same d. We also give a linear-time approximate sampler REG*, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d=o(n^1/2).

Related

• Fast uniform generation of random graphs with given degree sequences
• Uniform generation of random graphs with power-law degree sequences
• Generating graphs randomly
• Uniform generation of spanning regular subgraphs of a dense graph
• Uniform random sampling of planar graphs in linear time