Uniform generation of spanning regular subgraphs of a dense graph (Q2335698)

Summary: 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 [Graphs Comb. 30, No. 3, 581--589 (2014; Zbl 1294.05108)], 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)\).