A Perfect Sampler for Hypergraph Independent Sets

05/04/2022
by   Guoliang Qiu, et al.
0

The problem of uniformly sampling hypergraph independent sets is revisited. We design an efficient perfect sampler for the problem under a similar condition to the asymmetric Lovász Local Lemma. When specialized to d-regular k-uniform hypergraphs on n vertices, our sampler terminates in expected O(nlog n) time provided d≤ c· 2^k/2 where c>0 is a constant, matching the rapid mixing condition for Glauber dynamics in [HSZ19]. The analysis of our algorithm is simple and clean.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset