2018/07/03 by Pu Gao, Gao, Pu, Catherine Greenhill +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1807.00964
openalex publication_date 2018/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let Hn be a graph on n vertices and let \berHn denote the complement of Hn. Suppose that Δ= Δ(n) is the maximum degree of \berHn. We analyse three algorithms for sampling d-regular subgraphs (d-factors) of Hn. This is equivalent to uniformly sampling d-regular graphs which avoid a set E(\berHn) of forbidden edges. Here d=d(n) is a positive integer which may depend on n. Two of these algorithms produce a uniformly random d-factor of Hn in expected runtime which is linear in n and low-degree polynomial in d and Δ. The first algorithm applies when (d+Δ)dΔ= o(n). This improves on an earlier algorithm by the first author, which required constant d and at most a linear number of edges in \berHn. The second algorithm applies when Hn is regular and d2+Δ2 = o(n), adapting an approach developed by the first author together with Wormald. The third algorithm is a simplification of the second, and produces an approximately uniform d-factor of Hn in time O(dn). Here the output distribution differs from uniform by o(1) in total variation distance, provided that d2+Δ2 = o(n).