Sampling hypergraphs with given degrees

There is a well-known connection between hypergraphs and bipartite graphs, obtained by treating the incidence matrix of the hypergraph as the biadjacency matrix of a bipartite graph. We use this connection to describe and analyse a rejection sampling algorithm for sampling simple uniform hypergraphs...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2021-11, Vol.344 (11), p.112566-14, Article 112566
Main Authors: Dyer, Martin, Greenhill, Catherine, Kleer, Pieter, Ross, James, Stougie, Leen
Format: Article
Language:English
Subjects:
Algorithm
Computer Science
Degree sequence
Hypergraph
Markov chain
Sampling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:There is a well-known connection between hypergraphs and bipartite graphs, obtained by treating the incidence matrix of the hypergraph as the biadjacency matrix of a bipartite graph. We use this connection to describe and analyse a rejection sampling algorithm for sampling simple uniform hypergraphs with a given degree sequence. Our algorithm uses, as a black box, an algorithm A for sampling bipartite graphs with given degrees, uniformly or nearly uniformly, in (expected) polynomial time. The expected runtime of the hypergraph sampling algorithm depends on the (expected) runtime of the bipartite graph sampling algorithm A, and the probability that a uniformly random bipartite graph with given degrees corresponds to a simple hypergraph. We give some conditions on the hypergraph degree sequence which guarantee that this probability is bounded below by a positive constant.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2021.112566