Uniform generation of spanning regular subgraphs of a dense graph

MaRDI QIDQ2335698zbMATH OpenFDO

Authors Pu Gao, Catherine Greenhill

Publication date 15 November 2019

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

Full work available at URL https://arxiv.org/abs/1807.00964, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p28

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

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)

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)$.

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

Cites work

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

Cited in

(2)

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

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)