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 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 considered 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 poly(1/\epsilon) and 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 more costly 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 of O^*(\sqrt q \cdot(n/\sqrt m)), which is strictly preferable to O^*(q\cdot (n/\sqrt m)) cost resulting from q invocations of the algorithm by Eden and Rosenbaum . More generally, for an input parameter x>1, our algorithm has a preprocessing phase with O^*(n/(x\cdot d_{avg)) cost, which then allows an O(x/\epsilon) per-sample cost, where d_{avg} denotes the average degree of the graph} .
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 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 poly(1/\epsilon) and 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^*(q\cdot (n/\sqrt m)) cost resulting from q invocations of the algorithm by Eden and Rosenbaum )) cost, which then allows an O(x/\epsilon) per-sample cost, where d_{avg} denotes the average degree of the graph} .
R
considered
raised
D
more costly
R
of
that is sublinear in q, namely,
D
. More generally, for an input parameter x>1, our algorithm has a preprocessing phase with O^*(n/(x\cdot d_{avg