Uniform Generation of Spanning Regular Subgraphs of a Dense Graph

Abstract

Let $H_n$ be a graph on $n$ vertices and let $\overline{H_n}$ denote the complement of $H_n$. Suppose that $\Delta = \Delta(n)$ is the maximum degree of $\overline{H_n}$. 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 $E(\overline{H_n})$ 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)d\Delta = 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 $\overline{H_n}$. The second algorithm applies when $H_n$ is regular and $d^2+\Delta^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+\Delta^2 = o(n)$.