Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time

Hendrik Fichtenberger, Mingze Gao, Pan Peng

We present a simple sublinear-time algorithm for sampling an arbitrary subgraph $H$ \emph{exactly uniformly} from a graph $G$ with $m$ edges, to which the algorithm has access by p…