We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise $epsilon$-close to the uniform distribution, in an emph{amortized-efficient} fashion. We consider the adjacency list query model, where access to a graph $G$ is given via degree and neighbor queries. The problem of sampling a single edge in this model has been raised by Eden and Rosenbaum (SOSA 18). Let $n$ and $m$ denote the number of vertices and edges of $G$, respectively. Eden and Rosenbaum provided upper and lower bounds of $Theta^*(n/sqrt m)$ for sampling a single edge in general graphs (where $O^*(cdot)$ suppresses $textrm{poly}(1/epsilon)$ and $textrm{poly}(log n)$ dependencies). We ask whether the query complexity lower bound for sampling a single edge can be circumvented when multiple samples are required. That is, can we get an improved amortized per-sample cost if we allow a preprocessing phase? We answer in the affirmative. We present an algorithm that, if one knows the number of required samples $q$ in advance, has an overall cost that is sublinear in $q$, namely, $O^*(sqrt q cdot(n/sqrt m))$, which is strictly preferable to $O^*(qcdot (n/sqrt m))$ cost resulting from $q$ invocations of the algorithm by Eden and Rosenbaum. Subsequent to a preliminary version of this work, Tv{e}tek and Thorup (arXiv, preprint) proved that this bound is essentially optimal.
Download