Uniform generation of spanning regular subgraphs of a dense graph

zbMATH Open1427.05218arXiv1807.00964MaRDI QIDQ2335698FDOQ2335698

Authors: Pu Gao, Catherine Greenhill 

Publication date: 15 November 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $H_n$ be a graph on $n$ vertices and let $$ denote the complement of $H_n$. Suppose that $Delta=Delta(n)$ is the maximum degree of $$. We analyse three algorithms for sampling $d$-regular subgraphs ($d$-factors) of $H_n$. This is equivalent to uniformly sampling $d$-regular graphs which avoid a set $$ 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 $H_n$ in expected runtime which is linear in $n$ and low-degree polynomial in $d$ and $Delta$. The first algorithm applies when $(d+Delta)dDelta=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 $$. The second algorithm applies when $H_n$ is regular and $d^2+Delt{a}^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 $H_n$ in time $O(dn)$. Here the output distribution differs from uniform by $o(1)$ in total variation distance, provided that $d^2+Delt{a}^2=o(n)$.

Full work available at URL: https://arxiv.org/abs/1807.00964

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Uniform generation of random regular graphs
• Fast uniform generation of regular graphs
• Uniform generation of \(d\)-factors in dense host graphs
• Generating Random Regular Graphs Quickly
• Uniform generation of random regular graphs of moderate degree

zbMATH Keywords

enumerationswitching methoduniform generation\(d\)-factors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42)

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Fast uniform generation of regular graphs
• Approximating the Permanent
• The asymptotic number of labeled graphs with given degree sequences
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration by degree sequence of graphs of high degree
• Subgraphs of dense random graphs with specified degrees
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Uniform generation of \(d\)-factors in dense host graphs
• Generating Random Regular Graphs Quickly
• Title not available (Why is that?)
• Generating random regular graphs
• Uniform generation of random regular graphs of moderate degree
• Sampling Regular Graphs and a Peer-to-Peer Network
• A sequential algorithm for generating random graphs
• Uniform generation of random graphs with power-law degree sequences
• Sampling regular graphs and a peer-to-peer network
• Uniform generation of random regular graphs
• Title not available (Why is that?)

Cited In (2)

• Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
• Uniform generation of \(d\)-factors in dense host graphs

This page was built for publication: Uniform generation of spanning regular subgraphs of a dense graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2335698)